10. Графы. (Определения. Примеры) Подграфы. Операции над графами

Опр: Пусть V – некоторое конечное множество: V={1,2,..,n} – называется множеством вершин (Обозначение: V⁽²⁾ – множество всех двухэлементных сочетаний из множества V

V⁽²⁾ = {(i,j) = (j,i) | ij, i,j=1,..,n} и EV⁽²⁾).

Тогда пара (V,E)=G – называется граф

V – множество вершин графа

E – множество ребер графа

Порядком графа G называется количество вершин этого графа: |G|=|VG|

Чаще всего вершины графа изображают точками плоскости, а ребра изображают отрезками или кусками кривых.

Пр:

Карты авто(железных)дорог (V – множество нас. пунктов, а каждое ребро – пара вершин, соед. дорогой)

Генеалогическое древо человека (V – множество родственников, которые входят в генеалогическое древо, E – пара, которая состоит из «1-го родства» (отец-сын…)

Две вершины графа G=(VG,EG) i, j  VG – смежные <­=> когда (i, j)  EG (те они соединены ребром), в противном случае они не смежные

Аналог: Два ребра ei, ej  EG – смежные <=> когда ei = (, n); ej = (, m) (те у них есть общие вершины)

Вершина  и ребро у – инцидентные <=> e = (, u) = (u, )

Граф G называется полным если любые его две вершины соединены ребром:

u, υ  VG => (u,υ) EG. Обозначается Kn=(VG,EG) (нарисовать пару #, )

Подграфы

Пусть G=(VG,EG) – граф, тогда H=(VH,EH) – подграф графа G, если VHVG, EHEG

В любом графе порядка n есть так называемый пустой подграф On

On=(Vn,)

Подграф H графа G называется остовным, если VH=VG

Для любого произвольного графа G  дополнительный граф G

G G => VG=VG, EG =EG (V⁽²⁾\EG) – те в дополнительном графеG вершины те же самые, но если (u,υ) – соединены ребром в EG, то они не соединены ребром в EG ((u,υ) не  EG). Если G G, то G – самодополнительный граф

Класс п/графов G – множество графов, которые получаются из G удалением 1-й вершины и всех инцидентных с ней рёбер.

Гипотеза реконструирования: Пусть G и H – графы-конечные

Предположим {Gυ | υG} совпадает с {Hu | uH}, те Gυ  Hu

GH-? 3≤n≤107

Операции над графами

G=(VG,EG)

=> по опр. GH=(VGVH, EGEH)

H=(VH,EH)

K3UK2 (нарис)

11. Помеченные и непомеченные графы. Изоморфизм графов. Матрицы, ассоциированные с помеченными графами.

Непомеченные графы – вершины которых не снабжены метками (не пронумерованы) и наоборот (привести примеры)

Изоморфизм графов

О: G и H – называются изоморфными (GH), если

1. ! VGVH, -биекция

2. (υ,u)EG  ((υ), (u))EH

Пр:

Доказать что GH



GH, т.к. существует биекция, удовлетворяющая определению изоморфизма

(υ1)=u1

(υ2)=u3

(υ3)=u5

(υ4)=u2

(υ5)=u4



Матрица помеченного графа

G=(VG,EG) – считаем помеченным и конечным

VG={υ1,υ2,..,υn}

Тогда по определению матрицей смежности графа G – будем называть матрицу

AG=(aij)nxn, где aij={1,(υi,uj)EG; 0, (υi,uj)EG }

; Элемент aij равен 1, если вершины υi и υj соединены ребром и равен 0, если не соединены ребром.

Т.к. мы рассматриваем графы не ориентируемые, то (υi,uj)=(υj,ui)EG => aij=aji =>

A – симметричная матрица. Заметим, что aii = 0, i

(примеры: построить м.с. по графу и наоборот (4*4-хотя бы))