Три следующие фигуры — это три разных представления одного и того же графа. Согласитесь, увидеть это не так-то просто!
На рисунках ниже изображены четыре графа — (а), (Ь), (с) и (d). Граф (а) является исходным, остальные три — его подграфы. Это означает, что в них были выбраны лишь некоторые ребра и вершины исходного графа. Подграфы позволяют изучать графы по частям.
Обычно различают три типа графов: обыкновенные графы, мультиграфы и псевдографы. На рисунках ниже слева направо представлены все три типа графов.
В обыкновенном графе две вершины могут соединяться только одним ребром. Если они соединены более чем одним ребром, то такой граф называется мультиграфом. Если вершина мультиграфа может соединяться сама с собой, то такой граф называется псевдографом. Ребро, начало и конец которого находятся в одной вершине, называется петлей. В этой книге все три типа графов мы будем называть просто графами, уточняя возможные ограничения в каждом конкретном случае.
Применительно к различным вариантам обхода графа используются следующие обозначения. Пусть G — помеченный граф с вершинами V0, V1, V2,. и ребрами X1, Х2, Х3, … Тогда маршрутом в графе G будет называться конечная последовательность вида V0, X1, V1,., Vn-1, Xn, Vn, в которой чередуются ребра и вершины. Запись вида (V0, V1, …, Vn) подразумевает, что любые две вершины соединяются только одним ребром, и маршрут определяется указанной последовательностью вершин. Если V0 = Vn, то есть исходная и конечная вершина маршрута совпадают, то маршрут является замкнутым, иначе — открытым. Путь — это маршрут, в котором каждое ребро проходится только один раз. Замкнутый маршрут, содержащий п разных вершин, называется циклом. Обратите внимание, что любой цикл можно представить графически в виде многоугольника, что будет показано позже.
* * *
ГРАФЫ И ГРАФИКИ
Граф. Это слово может означать «пишу» («графология», «графомания», «телеграф»), а в случае теории графов обозначает множество точек и линий между ними. Не следует путать графы и графики. Да, можно заметить, что в графиках линейных функций, образованных прямыми линиями или последовательностью отрезков, соединяющих точки, фактически каждой точке х оси ОХ сопоставлена точка (х, f(x)) на графике функции. Это выполняется и в классических графиках функций, построенных в декартовых координатах с двумя осями X и Y, на которых отмечаются точки (х, f(x)), образующие график функции у = f(х). Тем не менее это множество точек и линий нельзя назвать графом.
Графы обычно используются для представления отношений между элементами конечного множества. Например, чтобы представить отношения эквивалентности, позволяющие разделить элементы множества на классы, «точками» графа изображают элементы множества и соединяют «линиями» связанные или эквивалентные элементы (если элемент связан сам с собой, то на графе образуется петля). Отношения порядка изображаются с помощью ориентированных графов. Дуги со стрелками означают отношение «меньше, чем». Связь теории графов и теории множеств более подробно объясняется в Приложении.
* * *
Если между любыми двумя вершинами графа можно провести маршрут, то говорят, что граф является связным, как в случаях, представленных на рисунках выше. Для связных графов имеет смысл определить расстояние между вершинами u и v как минимальное количество ребер, образующих маршрут между u и v.
В приведенных выше двух примерах на рисунке слева изображен связный граф, на рисунке справа — несвязный.
* * *
ГРАФЫ И ЧИСЛА