Введение

Определение графа и орграфа. Связь с отношениями. Вершины и ребра (дуги). Изображение и представления графов. Подграфы. Остовные подграфы. Порожденные подграфы. Отноше- ние порядка на подграфах и максимальные подграфы. Связность и компоненты связности. Гомоморфизм и изоморфизм графов. Инварианты. Степени вершин. Группа автоморфизмов графов.

Графом (неориентированным графом) называют пару множеств (V, E), где произвольное (конечное) множество, элементы которого называются вершинами графа, а E — множество неупорядоченных пар (т.е. двухэлементных подмножеств) в множестве V . Элементы множества V называются ребрами. Ориентированный граф — это пара множеств (V, E), где V — множество вершин, а E — множество упорядоченных пар, называемых дугами графа.

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

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

Для представления графов используют разные подходы. Например, каждый граф можно описать матрицей, в которой каждая строка соответствует одной вершине, а каждый столбец — одному ребру. Элемент c_ij этой матрицы равен 1, если i-я вершина является концом j-го ребра (инцидентна ребру), и 0 в остальных случаях. Аналогично для ориентированного графа c_ij принимает значение 1, если i-я вершина является начальной для j-й дуги, значение −1, если i-я вершина является конечной для j-й дуги, и 0 в остальных случаях. Если j-я дуга является петлей, то в этом столбце все элементы равны нулю. Указанная матрица называется матрицей инциденций.

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

Обычно матрица инциденций имеет большие размеры и на практике используется редко. Чаще используют другой вариант матричного представления графа. Для неориентированного графа с n вершинами составим квадратную матрицу порядка n, элемент cij которой равен 1, если i-я и j-я вершины связаны ребром, и 0 в остальных случаях. Для орграфа составляется аналогичная матрица, в которой c_ij = 1, если есть дуга из i-й вершины в j-ю, и c_ij = 0 в остальных случаях. Указанная матрица называется матрицей смежности.

В информационных системах представление графа напрямую зависит от поддерживаемых типов данных и способов их представления в электронной памяти. Один из распространенных способов опирается на структуры данных, называемые списками. Список представляет собой массив произвольно расположенных в памяти элементов, связанных друг с другом посредством ссылок. Различают однонаправленные списки, в которых i-й элемент списка содержит ссылку (адрес) на следующий (i + 1)-й элемент списка, и двунаправленные списки, в которых каждый элемент содержит ссылки на следующий и предыдущий элементы. Чаще всего элементы списка одинаковы по структуре, но это необязательно.

На основе списков можно использовать следующий подход к представлению орграфа из n вершин. Составляется массив из n элементов, описывающих вершины орграфа. Этот массив называют массивом лидеров, хотя в действительности он может быть списком, а не массивом. Каждый элемент массива лидеров содержит ссылку на список, называемый списком смежности. Каждый элемент списка смежности i-го элемента массива лидеров отражает вершину орграфа, в которую из i-й вершины ведет дуга. Этот способ может использоваться и для описания неориентированных графов.

Пусть G = (V, E) — граф (орграф). Граф (орграф) G₁ = (V₁, E₁) называется подграфом графа G, если V₁ ⊂ V и E₁ ⊂ E. Подграф собственный, если одно из включений строгое. Если V = V₁ (множество вершин одно и то же), то G₁ называется остовным подграфом графа G.

Пусть G = (V, E) — граф (орграф) и V₁ ⊂ V . В множестве E выберем множество E_{1 всех тех ребер (дуг), оба конца которых попадают в V1. Пара (V1, E1) составляет подграф графа (орграфа) G, который называют подграфом, порожденным множеством V1.}

Пусть G₁ — подграф графа (орграфа) G, а G₂ — подграф G₁. Тогда G₂ будет подграфом и G. В этой ситуации мы называем G₂ подчиненным G₁ и пишем G₂ ⊂ G₁. В результате на множестве всех подграфов G возникает отношение порядка. Имея в виду это отношение, мы для любой совокупности подграфов графа (орграфа) G можем говорить о максимальном подграфе, как о подграфе, который не содержится ни в каком подграфе той же совокупности (кроме самого себя). В ряде случаев понятия ”наибольший подграф“ и ”максимальный подграф“ совпадают.

Последовательность _{v0, v1, . . . , vn} вершин графа называется цепью, если для любого i = 1, n вершины _vi−1 и _viсоединены ребром (являются смежными). Цепь можно интерпретировать и как последовательность ребер, в которой любые два ребра смежные (правда, надо оговорить, что стыковочные вершины данного ребра с левым и правым соседями должны быть разные). Цепь простая, если в ней все вершины разные. Цепь _{v0, v1, . . . , vn}, в которой _{v0 = vn} (концы совпадают) называется циклом. Хотя обычно фиксируется начальная точка цикла, удобно считать, что в качестве таковой может быть любая вершина в последовательности, т.е. мы не различаем, например, циклы _{v0, v1, . . . , vn}, _{v0 и v1, . . . , vn, v0, v1}. Цикл простой, если в нем все вершины разные. Правда, следует исключить из понятия ”простой цикл“ последовательность вида _{v0, v1, v0}, в которой одно и то же ребро проходится дважды.

Для орграфов вводятся аналогичные понятия пути _{v0, v1, ..., vn}, в котором для любого i = 1, n из вершины v_i−1 в вершину v_i ведет дуга, и контура — пути, у которого начало и конец совпадают, а также простого пути и простого контура.

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

Для орграфов используют три варианта понятия связности. Орграф сильно связный, если для любой пары (v, w) вершин есть путь из v в w и есть путь из w в v. Орграф связный, если для любой пары (v, w) его вершин есть путь из v в w или из w в v. Орграф слабо связный, если ассоциированный неориентированный граф, получающийся заменой каждой дуги ребром, является связным. Из сильной связности вытекает связность, а из последней — слабая связность. Для каждого из трех видов связности можно ввести соответствующее отношение: отношение сильной достижимости, отношение достижимости и отношение слабой достижимости. Из трех отношений два являются отношениями эквивалентности. Классы эквивалентности по отношению сильной достижимости называются компонентами сильной связности или бикомпонентами. Понятие компоненты связности также используют, имея в виду максимальный связный подграф орграфа.

Пусть G₁ = (V₁, E₁) и G₂ = (V₂, E₂) — два графа. Отображение φ: V₁ → V₂, удовлетворя- ющее условию {v, w} ∈ E₁ ⇒ {φ(v), φ(w)} ∈ E₂, называется гоморфизмом графов. Если гомоморфизм G₁ на G₂ устанавливает взаимно однозначное соответствие между парами множеств V₁ и V₂, E₁ и E₂, его называют изоморфизмом графов.

Аналогично вводятся понятия гомоморфизма и изоморфизма орграфов. Изоморфные графы (орграфы) рассматриваются как идентичные: их различия связаны со способом реализации, но не с внутренней структурой.

Установить изоморфизм двух графов сложной структуры непросто: эффективного алгоритма решения такой задачи нет. Конечно, существует конечное число отображений из V₁ в V₂, и можно проверить все эти отображения. Однако на практике это неприемлемо: объем вычислений с увеличением размера графа растет как факториал и очень быстро оказывается неподъемным.

Во многих случаях можно установить неизоморфность двух графов, сравнивая их характеристики, определяемые внутренней структурой, а точнее, такие характеристики, которые совпадают у любых двух изоморфных графов. Такие характеристики называют инвариантами. Первыми инвариантами являются количество вершин и количество ребер. Другим важным инвариантом является вектор степеней вершин, который представляет собой упорядоченный список степеней вершин. Можно привести и другие инварианты: количество петель, максимальную длину простой цепи (пути). Некоторые инварианты будут приведены позже в связи с анализом конкретных задач. Здесь же отметим еще один инвариант. автоморфизм графа — это изоморфизм графа на себя. Множество всех автоморфизмов графа непусто, так как включает в себя тождественное отображение множества вершин, и относительно операции композиции отображений образует группу. Она называется группой автоморфизмов. У изоморфных графов группы автоморфизмов изоморфны.