Математическая энциклопедия - графов теория

область дискретной математики, особенностью к-рой является геометрич. подход к изучению объектов. Основной объект Г. т.граф и его обобщения. Первые задачи Г. т. были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и др.). Одним из первых результатов в Г. т. явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером (1736) при решении задачи о Кенигсбергских мостах. Сформулированная в сер. 19 в. проблема четырех красок ( см. Четырех красок задача).также выглядит как развлекательная задача, однако попытки ее решения привели к появлению нек-рых исследований графов, имеющих теоретическое и прикладное значение. В сер. 19 в. появились работы, в к-рых при решении практич. задач были получены результаты, относящиеся к Г. т. Так, напр., Г. Кирхгоф [2] при составлении полной системы уравнений для токов и напряжений в электрич. схеме предложил по существу представлять такую схему графом и находить в этом графе остовиые деревья, с помощью к-рых выделяются линейно независимые системы контуров. А. Кэли [3], исходя из задач подсчета числа изомеров предельных углеводородов, пришел к задачам перечисления и описания деревьев, обладающих заданными свойствами, и решил нек-рые из них. В 20 в. задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике, биологии, экономике, социологии и т. д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теория чисел. В нач. 20 в. графы стали использоваться для представления нек-рых математич. объектов и формальной постановки различных дискретных задач; при этом наряду с термином "граф" употреблялись и. другие термины, напр, карта, комплекс, диаграмма, сеть, лабиринт. После выхода в свет в 1936 монографии Д. Кёнига [4] термин "граф" стал более употребительным, чем другие. В этой работе были систематизированы известные к тому времени факты. В 20-30-х гг. 20 в. появились первые результаты, относящиеся к изучению свойств связности, пла-нарности, симметрии графов, к-рые привели к формированию ряда новых направлений в Г. т. Значительно расширились исследования по Г. т. в конце 40-х начале 50-х гг., прежде всего в силу развития кибер нетики и вычислительной техники. Благодаря развитию вычислительной техники, изучению сложных кибернетич. систем, интерес к Г. т. возрос, а проблематика Г. т. существенным образом обогатилась. Кроме того, использование ЭВМ позволило решать возникающие на практике конкретные задачи, связанные с большим объемом вычислений, прежде не поддававшиеся решению. Для ряда экстремальных задач Г. т. были разработаны методы их решения, напр., один из таких методов позволяет решать задачи о построении максимального потока через сеть (см. Поток в сети). Для отдельных классов графов (деревья, плоские графы и т. д.), к-рые изучались и ранее, было показано, что решения нек-рых задач для графов из этих классов находятся проще, чем для произвольных графов (нахождение условий существования графов с заданными свойствами, установление изоморфизма графов и др.). Характеризуя проблематику Г. т., можно отметить, что нек-рые направления носят более комбинаторный характер, другие более геометрический. К первым относятся, напр., задачи о подсчете и перечислении графов с фиксированными свойствами, задачи о построении графов с заданными свойствами. Геометрический (топологический) характер носят многие циклы задач Г. т., напр, графов обходы, графов укладки. Существуют направления, связанные с различными классификациями графов, напр, по свойствам их разложения. Примером результата о существовании графов с фиксированными свойствами может служить критерий реализуемости чисел степенями вершин нек-рого графа: набор целых чисел сумма к-рых четна, можно реализовать степенями вершин графа без петель и кратных ребер тогда и только тогда, когда для любого выполняется условие

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

где Для числа неизоморфных графов без петель и кратных ребер с вершинами было показано, что

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

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

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