ГРА́ФОВ ТЕО́РИЯ
-
Рубрика: Математика
-
-
Скопировать библиографическую ссылку:
Книжная версия:
Электронная версия:
ГРА́ФОВ ТЕО́РИЯ, раздел дискретной математики, в котором изучаются свойства графов и их обобщений. Графом называется пара (V,E), где V – множество точек, называемых вершинами, и E – множество пар вершин, причём если порядок, в котором перечислены вершины в паре, не важен, то эта пара вершин графа называется ребром, а если важен – дугой. Граф, содержащий только рёбра, называется неориентированным графом, или просто графом, а граф, содержащий только дуги, – ориентированным графом. На рис. 1 – неориентированный граф с вершинами a,b,c,d и рёбрами (a,b),(b,c),(c,d),(a,d),(a,c),(b,d), на рис. 2 – ориентированный граф с вершинами a,b,c,d,e,f и дугами (a,b),(b,c),(c,d),(d,e),(e,f),(f,a).
Исторический очерк
Первые задачи Г. т. были связаны с решением математич. задач развлекательного характера и головоломок (см. Комбинаторные задачи классические). Одним из первых результатов Г. т. был критерий существования обхода всех рёбер графа без повторений, полученный Л. Эйлером (1736) при решении задачи о Кёнигсбергских мостах (см. Гамильтонов цикл). С сер. 19 в. появляются относящиеся к Г. т. работы, содержащие результаты, связанные с разл. приложениями математики. Так, Г. Кирхгоф (1847) для составления полной системы уравнений для токов и напряжений в электрич. сетях (см. Кирхгофа правила) предложил представлять такую сеть графом и находить в этом графе остовные деревья, что приводит к решению задачи выделения независимых систем уравнений. Деревом называется связный граф, не содержащий циклов (рис. 3), остовное дерево графа – это его подграф, представляющий собой дерево, множество вершин которого совпадает с множеством вершин графа. А. Кэли (1854) для подсчёта числа изомеров предельных углеводородов пришёл к задачам описания и перечисления деревьев, обладающих заданными свойствами. Термин «граф» утвердился в математике после выхода монографии нем. математика Д. Кёнига (1936). Начиная со 2-й пол. 20 в. значительно расширились исследования в Г. т., в осн. в силу развития дискретной математики и вычислит. техники. Задание графа равносильно заданию на элементах множества вершин V некоторого бинарного отношения. По этой причине, а также ввиду возможности наглядного представления графа в виде чертежа на плоскости, графовые модели используются при построении алгоритмов решения разнообразных задач как в математике и естествознании, так и в гуманитарных науках.
Методы исследования в теории графов
Прежде всего выделяются комбинаторные методы теоретико-множественного анализа заданного бинарного отношения на множестве вершин. Весьма существенны (особенно в перечислительных задачах) алгебраические методы, в первую очередь методы теории групп (в частности, групп подстановок). При изучении укладок графа на плоскость привлекаются результаты топологич. характера. Случайные графы изучаются с помощью теоретико-вероятностных методов.
Особую роль при изучении графов играют матричные методы. Для графа G матрицей смежности A=A(G)=||aij|| называется матрица, в которой aij=1, если в графе G вершина i связана с вершиной j ребром (или дугой в ориентированном графе) и aij=0 в противном случае. В первом случае говорят, что вершины i и j смежны, во втором случае – что они несмежны. Маршрутом в графе G называется последовательность v_0e_1v_1…v_{n–1}e_nv_n, состоящая попеременно из вершин и рёбер графа, в которой ребро e_i соединяет вершины v_{i–1} и v_i, i=1, …, n; говорят, что этот маршрут связывает вершины v_0 и v_n. Маршрут, в котором v_0=v_n, называется циклом. Маршрут называется цепью (соответственно, простой цепью), если все его рёбра (все его вершины) различны. При n⩾1 элемент на месте (i, j) в матрице A^n равен числу маршрутов длины n из вершины v_i в вершину v_j. Граф называется связным, если для любых его двух вершин существует маршрут, связывающий эти вершины. Для графа G с p вершинами и q рёбрами, в котором занумерованы как вершины, так и рёбра, рассматривается матрица инцидентности B(G), представляющая собой матрицу, состоящую из нулей и единиц с двумя единицами в каждом столбце; в столбце, соответствующем ребру, соединяющему вершины i и j, единица стоит в строках с номерами i и j. Говорят, что каждая из вершин i и j и соединяющее их ребро инцидентны, два ребра смежны, если они имеют общую инцидентную им вершину. Ранг матрицы инцидентности B(G) равен p-1, если граф G является связным графом.
Множество собств. значений матрицы смежности графа или ориентированного графа (при этом каждое значение берётся столько раз, какова его кратность) называется спектром графа. Спектр графа с n вершинами состоит из n действительных чисел. Изучение спектра графа позволяет выяснить мн. особенности его строения.
Задачи теории графов
Центральным в Г. т. является раздел, изучающий структурные свойства графов. Одной из характеристик структуры графа является последовательность степеней его вершин. Степенью вершины неориентированного графа называется число инцидентных ей рёбер. Графич. разбиением чётного натурального числа n называется представление его в виде суммы p слагаемых n=\sum_{i=1}^d d_i такое, что существует граф с p вершинами, степени которых равны d_1,…,d_p. В Г. т. известен эффективный алгоритм, позволяющий для данного упорядоченного набора чисел (d_1,…,d_p) определить, существует ли граф с p вершинами v_1,…,v_p, для которых последовательность степеней (d(v_1),…,d(v_p)) совпадает с этим набором. Подробно изучено др. важное структурное свойство – связность графа, а также вопросы, относящиеся к существованию в связном графе маршрутов определённого вида.
Спец. разделом структурной Г. т. является факторизация графа, т. е. разложение графа G= (V, E) на сумму факторов (подграфов) G_1, …, G_m с некоторым заданным свойством, где G_i=(V, E_i) и E=E_1\cup …\cup E_m – разбиение множества рёбер на непустые непересекающиеся подмножества. Наиболее распространённые виды факторизации: n-факторизация, где G_i – однородные графы степени n (графы, степени всех вершин которых одинаковы и равны n), и древесная факторизация, где каждая компонента любого G_i, i=1,…,m, является деревом. Любой полный граф K_{2n}, т. е. граф, в котором любые две вершины смежны, 1-факторизуем, но не 2-факторизуем; любой полный граф K_{2n+1} не является 1-факторизуемым, но представляется в виде суммы n факторов, являющихся циклами. Если при 1-факторизации речь идёт о возможности разбиения множества рёбер на подмножества, состоящие из попарно несмежных рёбер (при этом каждое из подмножеств есть 1-фактор), то всякое разбиение множества вершин графа на n подмножеств таких, что вершины из любых двух разных подмножеств попарно несмежны, определяет правильную раскраску графа в n цветов. Теория раскрасок графа возникла и развивалась в связи с четырёх красок задачей, которая получила решение лишь на рубеже 1970–80-х гг.
С графом G=(V, E) естественно связывается целый ряд графов, напр. его подграфы, дополнительный граф, рёберный граф L(G). Рёберным для графа G с p вершинами и q рёбрами называется граф с множеством вершин E, в котором две вершины соединены ребром тогда и только тогда, когда соответствующие рёбра смежны в G. Критерий того, что данный граф является рёберным графом, заключается в отсутствии у него подграфов, принадлежащих множеству из 9 конкретно указанных графов (с 4, 5 или 6 вершинами). Изучение спец. классов графов, выделяемых к.-л. определяющим признаком или структурным свойством, составляет одно из направлений теории графов.
Если граф задан бинарным отношением на множестве, то часто возникает вопрос о том или ином его конкретном представлении. Такого рода задачей является задача о планарности графа, т. е. о возможности представить его на плоскости рисунком, в котором нет пересечения рёбер. Наиболее известный критерий планарности даёт теорема Понтрягина – Куратовского: граф является планарным тогда и только тогда, когда он не содержит в качестве подграфа ни полного графа K_5, ни двудольного графа K_{3,3}. Граф G=(V, E) называется двудольным, если допускается разбиение вершин множества V на два подмножества V_1 и V_2, состоящие из попарно несмежных вершин, такой граф обозначается , где n_i – число вершин в подмножестве V_i, i=1, 2.
Значит. часть исследований в Г. т. составляют перечислительные и экстремальные задачи. Отд. класс экстремальных задач – задачи о покрытии. Осн. объектами исследования в задачах о покрытии являются четыре важнейшие теоретико-графовые константы: число вершинного покрытия α_0, число рёберного покрытия α_1, вершинное число независимости β_0 и рёберное число независимости β_1. Число вершинного покрытия графа G есть миним. число вершин в покрывающем множестве, т. е. в таком множестве вершин, для которого каждое ребро графа G инцидентно хотя бы одной вершине этого множества. Вершинное число независимости графа G есть наибольшее возможное число элементов в независимом множестве, т. е. в таком множестве вершин, в котором любые две вершины несмежны. Аналогично определяются число рёберного покрытия и рёберное число независимости. Для любого связного графа G с p>1 вершинами α_0+β_0=α_1+β_1=p, а для двудольного графа β_1=α_0. Значения этих констант известны лишь для некоторых графов частного вида. К задачам о покрытии тесно примыкает теория доминирования. В ней рассматриваются доминирующие множества графа G=(V, E), т. е. такие подмножества D \subset V, что любая вершина из V\setminus D смежна хотя бы с одной из вершин D. Важнейшей константой графа является число доминирования – наименьшее возможное число вершин в его доминирующем множестве.
