Основные понятия теории графов

Баранов Виктор Павлович. Дискретная математика. Раздел 3. Графы, сети, коды.

Лекция 7. Основные понятия теории графов

Лекция 7. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ

План лекции:

Введение.
Теоретико-множественное определение графа.
Геометрическая интерпретация и реализация графов.
Степени вершин.
Матрицы смежности и инциденций.
Подграфы.
Изоморфизм графов.

Введение

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

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

Теоретико-множественное определение графа

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

Пусть задано непустое множество . Обозначим через множество всех пар (упорядоченных или неупорядоченных) его различных элементов.

Графом называется пара , где . Элементы из называются вершинами графа, а элементы из – его ребрами. Если – множество упорядоченных пар, то граф называется ориентированным (орграфом) (рис. 1, а), в противном случае – неориентированным (рис. 1, б). Элементы множества , то есть пары вершин, для неориентированного графа, называются ребрами, а для ориентированного – дугами. В случае когда в орграфе необходимо пренебречь направленностью дуг, то неориентированный граф, соответствующий , обозначается как и называется неориентированным дупликатом (или неориентированным двойником).

В ряде случаев естественно рассматривать смешанные графы (рис. 1, в), имеющие как ориентированные, так и неориентированные ребра. Например, план города можно рассматривать как граф, в котором ребра представляют улицы, а вершины – перекрестки; при этом по одним улицам может допускаться лишь одностороннее движение, и тогда на соответствующих ребрах вводится ориентация; по другим улицам движение двустороннее, и на соответствующих ребрах ориентация не вводится.

Граф, не имеющий ребер (), называется пустым или нуль-графом. Все вершины пустого графа изолированные. Граф, в котором каждая пара вершин соединена ребром, называется полным. Полный -вершинный неориентированный граф обозначается ; для каждой его вершины имеем (рис. 2). Для полного графа , а число ребер равно .

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

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

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

Для графа на рис. 1, а имеем , т. е. вершины и являются конечными вершинами дуг, у которых начальной вершиной является ; ; ; ; .

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

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

Очевидно, что для неориентированного графа .

Когда отображение действует на множество вершин , то под понимают объединение . Для графа на рис. 1, а , .

Отображение записывается как . Аналогично «тройное» отображение записывается как и т. д. Для графа на рис.1, а имеем:

и т. д. Аналогично понимаются обозначения , и т. д.

Геометрическая интерпретация и реализация графов

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

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

Теорема1. Каждый конечный граф можно реализовать в трехмерном евклидовом пространстве.

Степени вершины

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

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

Если ребро (дуга) инцидентно только одной вершине, то его называют петлей. Ребра называют кратными, если они инцидентны одним и тем же вершинам.

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

Теорема 2. Сумма степеней вершин -графа равна удвоенному числу его ребер:

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

Следствие. В любом графе число вершин нечетной степени четно.

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

Первое слагаемое четно (как сумма четных чисел). Значит второе слагаемое также должно быть четным, а это при суммировании нечетных чисел возможно, если только их количество четно.

Для орграфов вместо степени вершины вводят понятие полустепеней: полустепень исхода – это число дуг, выходящих из вершины ; полустепень захода – это число дуг, входящих в вершину . Очевидно, что

Матрицы смежности и инциденций

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

Для графа, изображенного на рис. 4, матрица смежности имеет вид:

Матрица смежности полностью определяет структуру графа. Например,

, ,

Множество столбцов, имеющих 1 в -ой строке, есть множество , а множество строк, которые имеют 1 в -ом столбце, совпадает с множеством .

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

Возведем матрицу смежности в квадрат. Элемент матрицы определяется по формуле

Слагаемое в этом уравнении равно 1 тогда и только тогда, когда оба числа равны 1, в противном случае оно равно 0. Поскольку из равенства следует существование пути длины 2 из вершины в вершину , проходящего через вершину , то равно числу путей длины 2, идущих из в .

Аналогично если является элементом матрицы , то равно числу путей длины , идущих от к .

Матрицей инциденций -графа называется прямоугольная матрица размерности , определяемая следующим образом:

Для графа, приведенного на рис. 4, матрица инциденций имеет вид:

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

Если в матрице инциденций нет нулевых элементов, то имеем полный орграф, который называется турниром.

Подграфы

Пусть , – два графа, для которых , ; тогда говорят, что является подграфом графа . В свою очередь, граф по отношению к своему подграфу является надграфом. Если и , то такой подграф называется остовным. Любой остовный подграф графа может быть получен путем удаления подмножества ребер надграфа.

Подграфы другого типа получаются, если выбрать подмножество вершин надграфа и присоединить к ним все ребра, концы которых принадлежат . Это вершинно-порожденные подграфы. Любой вершинно-порожденный подграф графа можно получить путем удаления подмножества вершин и всех инцидентных им ребер надграфа.

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

Изоморфизм графов

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

Изоморфизмом называют взаимно однозначное соответствие между множествами вершин двух графов и , сохраняющее отношение смежности, а сами графы называются изоморфными. Автоморфизмом называется изоморфное отображение графа на себя. Примеры изоморфных графов показаны на рис. 3. Для установления изоморфности достаточно составить списки вершин всех графов, указав для каждой из них все ее соседние вершины. В данном случае все эквивалентные вершины пронумерованы одинаково, что упрощает решение задачи. Задача усложняется, если эквивалентные вершины имеют разные номера. В этом случае процедуру работы со списками придется повторять неоднократно, каждый раз меняя нумерацию вершин одного из графов, пока не будет обнаружен изоморфизм, т. е. получены идентичные списки вершин. В худшем случае потребуется проверить вариантов нумерации вершин. Доказать неизоморфизм графов можно, только выполнив все проверки. Существенно сократить их количество можно, если использовать инварианты.

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

Понятие изоморфизма графов имеет следующее наглядное представление. Представим ребра графа эластичными нитями, связывающими узлы – вершины графа. Тогда изоморфизм можно представить как перемещение узлов и растяжение нитей.

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

Теорема 2. .

Доказательство. Очевидно, что число вершин в каждом из рассматриваемых графов не превосходит .Занумеруем их числами 1, 2, …, . Каждое ребро определяется двумя вершинами (концами), не обязательно различными, так что для каждого ребра имеется не более возможностей выбора концов, а для ребер – не более, чем . Следовательно, . Используя неравенство , получаем Теорема доказана.

Основные понятия теории графов