12. Метрика (на связных графах). Расстояние между точками графа. Планарность графа

Маршрутом соединяющим вершины υ, u  VG, называется последовательность

υ = υ1e1, υ2e2,.., υ (n-1)e(n-1), υn = u, где υiVG, ei = (υi, υ(i+1))EG

Маршрут называется простой цепью, если все вершины, встречающиеся в этом маршруте, кроме начальной и конечной, различны. (υi ≠ υj (i≠j?i,j {2,..,n-1}))

(нарисовать W, показать v и e)

Eсли υ1= υ = υn= u - то маршрут простой цикл (нарисовать треугольник)

Граф G=(VG,EG) называется связным, если для любых двух вершин графа  маршрут, соединяющий эти вершины (υ = υ1,e1, υ2,e2,…, en-1, υn = u)

Т: Любой граф G=(VG,EG) – можно представить в виде дизъюнктивного объединения связанных компонент => G=G1G2..Gk, Gi – связанный граф и GiGj = , i≠j

Т:  G=(VG,EG) – либо сам этот граф, либо его дополнение будет связанным графом (# N­)

О: Пусть G=(VG,EG) – связный граф, тогда определим расстояние (u,v),  u, v  G => (u,v) – длинна кратчайшего маршрута (кол-во ребер входящих в маршрут)

Свойства расстояния:

Т: Граф G=(VG,EG) – связанный граф, тогда  u, v  G:

1) (u,v) = (v,u)

2) (u,v) = 0  u=v

3) (u,v) ≥ 0

4) (u,v) + (v,w)  (u,w) (нарис. треугольник)

; Дерево – связный граф без циклов (нарисовать)

Т: G – граф, n – кол-во вершин, m – кол-во рёбер

Тогда следующие условия эквивалентны:

1. G – дерево

2. G – связный граф и m=n-1

3. G – ациклический граф и m=n-1 (без циклов)

4. v,u  VG  и ! простая цепь, соединяющая эти вершины

Планарность графов

Опр.: Граф G называется плоским, если его вершины VG можно изобразить точками плоскости так, что рёбра не имеют пересечений (в противном случае граф не плоский)

Опр.: Граф G называется планарным, если существует H – плоский граф такой, что GH

Пр: G1(пентагон) – плоский и планарный; G2(звезда) – не плоский (рёбра пересекаются), но планарный, тк G2G1; K3,3 = G3 – не плоский и не планарный (доказано); K5 – тоже.

13. Высказывание. Операции над высказываниями. Булева алгебра высказываний

Высказывание – это повествовательное предложение, о котором можно сказать истинно оно или ложно (одно из двух). (Примеры, про Москву там и т.п.)

Сами высказывания обычно обозначаются первыми малыми латинскими буквами (a,b,c…).

Множество высказываний обозначим буквой А

Определим отображение  из А в множество E2 (: A=E2={0,1})

 a  A: a = {1 – если a истинное высказывание, 0 – если a ложное высказывание};

0 и 1 часто рассматриваются как высказывания (0 – ложь, 1 – истина)

Равносильность ab^a=^b

По этому отношению эквивалентности всё множество высказываний разбивается на 2 класса эквивалентности (мн-во всех истинных высказываний и мн-во всех ложных высказываний)

Т.К. нас не интересует содержательная часть высказываний, то можно считать 2 истинных высказывания одинаковыми, также как и 2 ложных

Операции над множествами на множестве высказываний:

a) унарная – отрицание aА aА;

Свойства: 0≡1; 1≡0; ≡ a

бинарные операции:

б) конъюнкция - a,bA  ab предлог («и»)

в) дизъюнкция - a,bА  ab; предлог («или»)

Кроме основных операций, которые называются булевыми ( ,,), вводятся дополнительные бинарные операции:

1) импликация - a,bA  ab; («из a следует b»); (ab)≡ ab

2) эквиваленция - a,bA  a~b; (a~b)≡(ab)(ba);

(A, ,,) – образует Булеву алгебру высказываний.

Т.к. введены операции удовлетворяющие основным 19-булевым равносильностям.

доказательства таблицей истинности