Введение в схемы, автоматы и алгоритмы


Графы - часть 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),
где
(v_i,v_{i+1})\in E
при
i=1,2,\ldots, n-1
.

Путь назывется простым, если все ребра и все вершины на нем, кроме, быть может, первой и последней, различны.

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

(v_1,v_2, \ldots , v_{n-1},v_n=v_1)
называется простым, если в нем нет одинаковых вершин, кроме первой и последней, т.е. если все вершины
v_2, \ldots , v_{n-1}
различны.

Если в графе нет циклов, то он называется ациклическим.

Следующее утверждение непосредственно следует из определений.

Лемма 1.1.Если в графе

G
имеется путь из вершины
u
в вершину
v
, то в нем имеется и простой путь из
u
в
v
.




Начало  Назад  Вперед



Книжный магазин