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


             

Обычно несколько ребер, соединяющих одну


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

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

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

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

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

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

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

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

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

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

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

Лемма 1.1.Если в графе
имеется путь из вершины
в вершину
, то в нем имеется и простой путь из
в
.


Содержание  Назад  Вперед