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

Область дискретной математики, особенностью к-рой является геометрич. подход к изучению объектов. Основной объект Г. т.- граф и его обобщения. Первые задачи Г. т. были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и др.). Одним из первых результатов в Г. т. явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером (1736) при решении задачи о Кенигсбергских мостах. Сформулированная в сер. 19 в. проблема четырех красок ( см. Четырех красок задача).также выглядит как развлекательная задача, однако попытки ее решения привели к появлению нек-рых исследований графов, имеющих теоретическое и прикладное значение. В сер. 19 в. появились работы, в к-рых при решении практич. задач были получены результаты, относящиеся к Г. т. Так, напр., Г. Кирхгоф [2] при составлении полной системы уравнений для токов и напряжений в электрич. схеме предложил по существу представлять такую схему графом и находить в этом графе остовиые деревья, с помощью к-рых выделяются линейно независимые системы контуров. А. Кэли [3], исходя из задач подсчета числа изомеров предельных углеводородов, пришел к задачам перечисления и описания деревьев, обладающих заданными свойствами, и решил нек-рые из них. В 20 в. задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике, биологии, экономике, социологии и т. д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теория чисел. В нач. 20 в. графы стали использоваться для представления нек-рых математич. объектов и формальной постановки различных дискретных задач; при этом наряду с термином "граф" употреблялись и. другие термины, напр, карта, комплекс, диаграмма, сеть, лабиринт. После выхода в свет в 1936 монографии Д. Кёнига [4] термин "граф" стал более употребительным, чем другие. В этой работе были систематизированы известные к тому времени факты. В 20-30-х гг. 20 в. появились первые результаты, относящиеся к изучению свойств связности, пла-нарности, симметрии графов, к-рые привели к формированию ряда новых направлений в Г. т. Значительно расширились исследования по Г. т. в конце 40-х — начале 50-х гг., прежде всего в силу развития кибер нетики и вычислительной техники. Благодаря развитию вычислительной техники, изучению сложных кибернетич. систем, интерес к Г. т. возрос, а проблематика Г. т. существенным образом обогатилась. Кроме того, использование ЭВМ позволило решать возникающие на практике конкретные задачи, связанные с большим объемом вычислений, прежде не поддававшиеся решению. Для ряда экстремальных задач Г. т. были разработаны методы их решения, напр., один из таких методов позволяет решать задачи о построении максимального потока через сеть (см. Поток в сети). Для отдельных классов графов (деревья, плоские графы и т. д.), к-рые изучались и ранее, было показано, что решения нек-рых задач для графов из этих классов находятся проще, чем для произвольных графов (нахождение условий существования графов с заданными свойствами, установление изоморфизма графов и др.). Характеризуя проблематику Г. т., можно отметить, что нек-рые направления носят более комбинаторный характер, другие — более геометрический. К первым относятся, напр., задачи о подсчете и перечислении графов с фиксированными свойствами, задачи о построении графов с заданными свойствами. Геометрический (топологический) характер носят многие циклы задач Г. т., напр, графов обходы, графов укладки. Существуют направления, связанные с различными классификациями графов, напр, по свойствам их разложения. Примером результата о существовании графов с фиксированными свойствами может служить критерий реализуемости чисел степенями вершин нек-рого графа: набор целых чисел сумма к-рых четна, можно реализовать степенями вершин графа без петель и кратных ребер тогда и только тогда, когда для любого выполняется условие Примерами задач о подсчете графов с заданными свойствами являются задачи о нахождении количеств неизоморфных графов с одинаковым числом вершин и (или) ребер. Для числа неизоморфных деревьев с п. вершинами была получена асимптотич. формула где Для числа неизоморфных графов без петель и кратных ребер с вершинами было показано, что Наряду с проблемами, носящими общий характер, в Г. т. имеются специфич. циклы задач. В одном из них изучаются различные свойства связности графов, исследуется строение графов по свойствам связности (см. Графа связность). При анализе надежности сетей связи, электронных схем, коммуникационных сетей возникает задача о нахождении количеств непересекающихся цепей, соединяющих различные вершины графа. Здесь получен ряд результатов. Напр., наименьшее число вершин, разделяющих две несмежные вершины графа, равно наибольшему числу непересекающихся (по вершинам) простых цепей, соединяющих эту пару вершин. Найдены критерии и построены эффективные алгоритмы установления меры связности графа (наименьшего числа вершин или ребер, удаление к-рых нарушает связность графа). В другом направлении исследований Г. т. изучаются маршруты, содержащие все вершины пли ребра графа (см. Графа обход). Известен простой критерий существования маршрута, содержащего все ребра графа: в связном графе цикл, содержащий все ребра и проходящий по каждому ребру один раз, существует тогда и только тогда, когда все вершины графа имеют четные степени. В случае обхода множества вершин графа имеется только ряд достаточных условий существования цикла, проходящего по всем вершинам графа по одному разу. Характерным специфическим направлением Г. т. является цикл задач, связанный с раскрасками графов, в к-ром изучаются разбиения множества вершин (ребер), обладающие определенными свойствами, напр, смежные вершины (ребра) должны принадлежать различным множествам (вершины или ребра из одного множества окрашиваются одним цветом; см. Графа раскраска). Было доказано, что наименьшее число цветов, достаточное для раскраски ребер любого графа без петель с максимальной степенью , равно а для раскраски вершин любого графа без петель и кратных ребер достаточно цветов. Существуют п другие циклы задач (см. Покрытия и упаковки, Графа укладка. Графов числовые характеристики);нек-рые из них сложились под влиянием различных разделов математики. Так, под влиянием топологии производится изучение вложений графов в различные поверхности. Напр., было получено необходимое и достаточное условие вложения графа в плоскость (критерий Понтрягина- Куратовского): граф является плоским тогда и только тогда, когда он не содержит подграфов, получаемых с помощью подразбиения ребер из полного 5-вершинного графа и полного двудольного графа с тремя вершинами в каждой доле. Под влиянием алгебры стали изучаться группы автоморфизмов графов (см. Графа автоморфизм). В частности, было доказано, что каждая конечная группа изоморфна группе автоморфизмов нек-рого графа. Влияние теории вероятностей сказалось на исследовании графов случайных. Многие свойства были изучены для "почти всех" графов; напр, было показано, что почти все графы с n вершинами связаны, имеют диаметр 2, обладают гамильтоновым циклом (циклом, проходящим через все вершины графа по одному разу). В Г. т. существуют специфич. методы решения экстремальных задач. Один лз них основан на теореме о максимальном потоке и минимальном разрезе, утверждающей, что максимальный поток, к-рый можно пропустить через сеть из вершины ив вершину v, равен минимальной пропускной способности разрезов, разделяющих вершины ии v(см. Поток в сети). Были построены различные эффективные алгоритмы нахождения максимального потока. Большое значение в Г. т. имеют алгоритмические вопросы. Для конечных графов, т. е. для графов с конечным множеством вершин и ребер, как правило, проблема существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение многих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допустимых вариантов. Однако таким способом удается решить задачу только для графов с небольшим числом вершин и ребер. Поэтому существенное значение для Г. т. имеет построение эффективных алгоритмов, находящих точное или приближенное решение. Для нек-рых задач такие алгоритмы построены, напр., для установления планарности графов, определения изоморфизма деревьев, нахождения максимального потока. Результаты и методы Г. т. применяются при решении транспортных задач о перевозках, для нахождения оптимальных решений задачи о назначениях, для выделения "узких мест" при планировании и управлении разработок проектов, при составлении оптимальных маршрутов доставки грузов, а также при моделировании сложных технологич. процессов, в построении различных дискретных устройств, в программировании и т. д. Лит.; [1] Euler L., в кн.: Commentationes Arithmetical Collectae, St. Peterburg, 1766, с. 66-70; [2] Kirchhoff G., "Poggendorf Annalen", 1847, Bd 72, S. 497-508; [3] Cayley A., "Collected Mathematical papers", Camb. 1854 v. 3, p. 242; [4] КonigD., Theorie der endlichen und unendhchen Graphen, 2 ed., N. Y., 1950; [5] Верж К., Теория графов и ее применение, пер. с франц., М., 1962; [6] 3ыков А. А., Теория конечных графов, [в.1], Новосиб., 1969 [7] Xарари Ф., Теория графов, пер. с англ., М., 1973; [8] Козырев В. П., в кн.: Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика, т. 10, 1972, с. 25-74; [9] Наrary F., Palmer Е., Graphical enumeration, N. Y. — L., 1973. В. В. Алексеев, В. П. Козырев, А. А. Сапоженко.