Графов теория

ГРАФОВ ТЕОРИЯ, раздел дискретной математики, в котором изучаются свойства графов и их обобщений. Графом называется пара (V, Е), где V - множество точек, называемых вершинами, и Е - множество пар вершин, причём если порядок, в котором перечислены вершины в паре, не важен, то эта пара вершин графа называется ребром, а если важен - дугой. Граф, содержащий только рёбра, называется неориентированным графом, или просто графом, а граф, содержащий только дуги, - ориентированным графом. На рисунке 1 - неориентированный граф с вершинами а, b, с, d и рёбрами (а, b), (b, с), (с, d), (а, d), (а, с), (b, d), на рисунке 2 - ориентированный граф с вершинами а, b, с, d, е, f и дугами (а, b), (b, с), (с, d), (d, е), (е, f), (f, а).

Исторический очерк. Первые задачи графов теории были связаны с решением математических задач развлекательного характера и головоломок (смотри Комбинаторные задачи классические). Одним из первых результатов графов теории был критерий существования обхода всех рёбер графа без повторений, полученный Л. Эйлером (1736) при решении задачи о Кёнигсбергских мостах (смотри Гамильтонов цикл). С середины 19 века появляются относящиеся к графов теории работы, содержащие результаты, связанные с различными приложениями математики. Так, Г. Кирхгоф (1847) для составления полной системы уравнений для токов и напряжений в электрических сетях (смотри Кирхгофа правила) предложил представлять такую сеть графом и находить в этом графе остовные деревья, что приводит к решению задачи выделения независимых систем уравнений. Деревом называется связный граф, не содержащий циклов (рис. 3), остовное дерево графа - это его подграф, представляющий собой дерево, множество вершин которого совпадает с множеством вершин графа.

А.Кэли (1854) для подсчёта числа изомеров предельных углеводородов пришёл к задачам описания и перечисления деревьев, обладающих заданными свойствами. Термин «граф» утвердился в математике после выхода монографии немецкого математика Д. Кёнига (1936). Начиная со 2-й половины 20 века значительно расширились исследования в графов теории, в основном в силу развития дискретной математики и вычислительной техники. Задание графа равносильно заданию на элементах множества вершин V некоторого бинарного отношения. По этой причине, а также ввиду возможности наглядного представления графа в виде чертежа на плоскости, графовые модели используются при построении алгоритмов решения разнообразных задач как в математике и естествознании, так и в гуманитарных науках.

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

Особую роль при изучении графов играют матричные методы. Для графа G матрицей смежности А = A(G) = ||a_ij|| называется матрица, в которой a_ij= 1, если в графе G вершина i связана с вершиной j ребром (или дугой в ориентированном графе) и a_ij = 0 в противном случае. В первом случае говорят, что вершины i и j смежны, во втором случае - что они несмежны. Маршрутом в графе G называется последовательность ν₀e₁ν₁...ν_n-1e_nν_n, состоящая попеременно из вершин и рёбер графа, в которой ребро е_i соединяет вершины v_i-1  и  v_i, i= l, ..., n; говорят, что этот маршрут связывает вершины v₀ и v_n. Маршрут, в котором v₀ = v_n, называется циклом. Маршрут называется цепью (соответственно, простой цепью), если все его рёбра (все его вершины) различны. При n≥ 1 элемент на месте (i, j) в матрице А_n равен числу маршрутов длины n из вершины v_i в вершину v_j. Граф называется связным, если для любых его двух вершин существует маршрут, связывающий эти вершины. Для графа G с р вершинами и q рёбрами, в котором занумерованы как вершины, так и рёбра, рассматривается матрица инцидентности В(G), представляющая собой матрицу, состоящую из нулей и единиц с двумя единицами в каждом столбце; в столбце, соответствующем ребру, соединяющему вершины i и j, единица стоит в строках с номерами i и j. Говорят, что каждая из вершин i и j и соединяющее их ребро инцидентны, два ребра смежны, если они имеют общую инцидентную им вершину. Ранг матрицы инцидентности В(G) равен р₁, если граф G является связным графом.

Множество собственных значений матрицы смежности графа или ориентированного графа (при этом каждое значение берётся столько раз, какова его кратность) называется спектром графа. Спектр графа с и вершинами состоит из n действительных чисел. Изучение спектра графа позволяет выяснить многие особенности его строения.

Задачи теории графов. Центральным в графов теории является раздел, изучающий структурные свойства графов. Одной из характеристик структуры графа является последовательность степеней его вершин. Степенью вершины неориентированного графа называется число инцидентных ей рёбер. Графическим разбиением чётного натурального числа n называется представление его в виде суммы р слагаемых n = ∑^p_i=1d_i такое, что существует граф с р вершинами, степени которых равны d₁,...,d_p. В графов теории известен эффективный алгоритм, позволяющий для данного упорядоченного набора чисел (d₁,...,d_p) определить, существует ли граф с р вершинами v₁,...,v_p, для которых последовательность степеней (d(v₁), ..., d(v_p)) совпадает с этим набором. Подробно изучено другое важное структурное свойство - связность графа, а также вопросы, относящиеся к существованию в связном графе маршрутов определённого вида.

Специальным разделом структурной графов теории является факторизация графа, т. е. разложение графа G = (V, Е) на сумму факторов (подграфов) G₁, ..., G_m с некоторым заданным свойством, где G_i = ( V, Е_i) и Е = Е₁u...uЕ_m - разбиение множества рёбер на непустые непересекающиеся подмножества. Наиболее распространённые виды факторизации: n-факторизация, где G_i - однородные графы степени n (графы, степени всех вершин которых одинаковы и равны n), и древесная факторизация, где каждая компонента любого G_i, i=1, ...,m, является деревом. Любой полный граф К_2n, т. е. граф, в котором любые две вершины смежны, 1-факторизуем, но не 2-факторизуем; любой полный граф К_2n+1 не является 1-факторизуемым, но представляется в виде суммы n факторов, являющихся циклами. Если при 1-факторизации речь идёт о возможности разбиения множества рёбер на подмножества, состоящие из попарно несмежных рёбер (при этом каждое из подмножеств есть 1-фактор), то всякое разбиение множества вершин графа на n подмножеств таких, что вершины из любых двух разных подмножеств попарно несмежны, определяет правильную раскраску графа в n цветов. Теория раскрасок графа возникла и развивалась в связи с четырёх красок задачей, которая получила решение лишь на рубеже 1970-80-х годов.

С графом G = (V, Е) естественно связывается целый ряд графов, например его подграфы, дополнительный граф, рёберный граф L(G). Рёберным для графа G с р вершинами и q рёбрами называется граф с множеством вершин Е, в котором две вершины соединены ребром тогда и только тогда, когда соответствующие рёбра смежны в G. Критерий того, что данный граф является рёберным графом, заключается в отсутствии у него подграфов, принадлежащих множеству из 9 конкретно указанных графов (с 4, 5 или 6 вершинами). Изучение специальных классов графов, выделяемых каким-либо определяющим признаком или структурным свойством, составляет одно из направлений теории графов.

Если граф задан бинарным отношением на множестве, то часто возникает вопрос о том или ином его конкретном представлении. Такого рода задачей является задача о планарности графа, т. е. о возможности представить его на плоскости рисунком, в котором нет пересечения рёбер. Наиболее известный критерий планарности даёт теорема Понтрягина - Куратовского: граф является планарным тогда и только тогда, когда он не содержит в качестве подграфа ни полного графа К₅, ни двудольного графа К_3,3. Граф G = (V, Е) называется двудольным, если допускается разбиение вершин множества V на два подмножества V₁ и V₂, состоящие из попарно несмежных вершин, такой граф обозначается K_n1,_n2, где n_i - число вершин в подмножестве V_i, i = 1, 2.

Значительная часть исследований в графов теории составляют перечислительные и экстремальные задачи. Отдельный класс экстремальных задач - задачи о покрытии. Основными объектами исследования в задачах о покрытии являются четыре важнейшие теоретико-графовые константы: число вершинного покрытия α₀, число рёберного покрытия α₁, вершинное число независимости β₀ и рёберное число независимости ß₁. Число вершинного покрытия графа G есть минимальное число вершин в покрывающем множестве, т. е. в таком множестве вершин, для которого каждое ребро графа G инцидентно хотя бы одной вершине этого множества. Вершинное число независимости графа G есть наибольшее возможное число элементов в независимом множестве, т. е. в таком множестве вершин, в котором любые две вершины несмежны. Аналогично определяются число рёберного покрытия и рёберное число независимости. Для любого связного графа G с р > 1 вершинами α₀ + ß₀ = α₁ + ß₁ = р, а для двудольного графа ß₁ = α₀. Значения этих констант известны лишь для некоторых графов частного вида. К задачам о покрытии тесно примыкает теория доминирования. В ней рассматриваются доминирующие множества графа G = (V, Е), то есть такие подмножества D с V, что любая вершина из VD смежна хотя бы с одной из вершин D. Важнейшей константой графа является число доминирования - наименьшее возможное число вершин в его доминирующем множестве.

Лит.: Кönig D. Theorie der endlichen und unendlichen Graphen. N. Y., 1950; Берж К. Теория графов и ее применение. М., 1962; Зыков А. А. Теория конечных графов. Новосиб., 1969; Харари Ф. Теория графов. М., 1973; Басакер Р., Саати Т. Конечные графы и сети. М., 1974; Камерон П., Линт Д. Теория графов, теория кодирования и блок-схемы. М., 1980; Оре О. Теория графов. 2-е изд. М., 1980; Цветкович Д., Дуб М., Закс Х. Спектры графов. Теория и применение. К., 1984; Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М., 2000; Колчин В. Ф. Случайные графы. 2-е изд. М., 2004; Сачков В. Н. Введение в комбинаторные методы дискретной математики. 2-е изд. М., 2004.