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

Графы


Мы часто сталкиваемся с задачами, в условиях которых заданы некоторые объекты и между некоторыми их парами имеются определенные связи. Если объекты изобразить точками (вершинами), а связи - линиями (ребрами), соединяющими соответствующие пары точек, то получится рисунок, называемый графом. Приведем основные определения.

Граф (ориентированный) - это пара

, где
- конечное множество вершин (узлов, точек) графа, а
- некоторое множество пар вершин, т.е. подмножество множества
или бинарное отношение на
. Элементы
называют ребрами (дугами, стрелками, связями). Для ребра
вершина
называется началом
, а вершина
- концом
, говорят, что ребро
ведет из
в
.

В графе полустепень исхода вершины - это число исходящих из нее ребер, а полустепень захода - это число входящих в данную вершину ребер.

Заметим, что в графе может быть ребро вида

, называемое петлей.

Пример 1.3. На рис. 1.1 приведен пример графа

. Здесь
, В графе
ребро
является петлей, полустепень исхода вершины
равна 2, а полустепень захода для нее равна 1.


Рис. 1.1.  Граф G1

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

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

Размеченный граф - это граф

, снабженный одной или двумя функциями разметки вида:
и
, где
и
- множества меток вершин и ребер, соответственно.

Упорядоченный граф - это размеченный граф

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

Упорядоченный граф с полустепенью исхода вершин

называется бинарным.

В качестве множества меток ребер

часто выступают числа, задающие "веса", "длины", "стоимости" ребер. Графы с такой разметкой часто называют взвешенными.

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

Определение 1.7. Мультиграф

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




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

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

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

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

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

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

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

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

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

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

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

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


Содержание раздела