Графы - часть 2

Обычно несколько ребер, соединяющих одну и ту же пару вершин, различаются метками - именами соответствующих бинарных отношений. В лекциях 4-6 мультиграфы будут использоваться для представления диаграмм конечных автоматов.

Во многих случаях естественно не различать графы, отличающиеся лишь именами (порядком) вершин.

Определение 1.8. Изоморфизм графов. Два графа

$G_1= (V_1, E_1)$

$G_2= (V_2, E_2)$

называются изоморфными, если между их вершинами существует взаимно однозначное соответствие

$\varphi: V_1 \rightarrow V_2$

такое, что для любой пары вершин

$u, v$

из

$V_1$

ребро

$(u,v) \in E_1 \ \Leftrightarrow\$

ребро

$(\varphi(u), \varphi(v)) \in E_2$

Для изоморфизма размеченных графов требуется также совпадение меток соответствующих вершин :

$l_1(v) = l_2(\varphi(v))$

и/или ребер:

$c_1((u,v)) = c_2((\varphi(u), \varphi(v)) )$

Многие приложения графов связаны с изучением путей между их вершинами.

Определение 1.9.

Путь в (мульти)графе - это последовательность ребер вида

$e_1=(v_1,v_2),e_2=(v_2,v_3), \ldots , e_{n-1}=(v_{n-1},v_n)$

. Этот путь ведет из начальной вершины

$v_1$

в конечную вершину

$v_n$

и имеет длину

$n-1$

. В этом случае будем говорить, что

$v_n$

достижима из

$v_1$

. Будем считать, что каждая вершина достижима сама из себя путем длины 0. Путь в графе (не мультиграфе!) можно также определять как соответствующую последовательность вершин:

$(v_1,v_2,v_3, \ldots , v_{n-1},v_n),$