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

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

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

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

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

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

из

ребро

.

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

и/или ребер:

.

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

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

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

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

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

и имеет длину

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

достижима из

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

где

при

.

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

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

называется простым, если в нем нет одинаковых вершин, кроме первой и последней, т.е. если все вершины

различны.

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

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

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

имеется путь из вершины

в вершину

, то в нем имеется и простой путь из

.

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