ГРАФОВ ТЕОРИЯ это:

ГРАФОВ ТЕОРИЯ

- область дискретной математики, особенностью к-рой является геометрич. подход к изучению объектов. Основной объект Г. т.- граф и его обобщения. Первые задачи Г. т. были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и др.). Одним из первых результатов в Г. т. явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером (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.

В. В. Алексеев, В. П. Козырев, А. А. Сапоженко.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ГРАФОВ ТЕОРИЯ" в других словарях:

  • ГРАФОВ ТЕОРИЯ — раздел математики, особенность которого геометрический подход к изучению объектов. Основное понятие теории граф задается множеством вершин (точек) и множеством ребер (связей), соединяющих некоторые пары вершин. Пример графа схема метрополитена:… …   Большой Энциклопедический словарь

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

  • Графов теория —         раздел конечной математики (См. Конечная математика), особенностью которого является геометрический подход к изучению объектов. Основное понятие теории граф. Граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих …   Большая советская энциклопедия

  • графов теория — раздел математики, особенность которого  геометрический подход к изучению объектов. Основное понятие теории  граф  задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих некоторые пары вершин. Пример графа  схема… …   Энциклопедический словарь

  • ГРАФОВ ТЕОРИЯ — в химии, область конечной математики, изучающая дискретные структуры, наз. графами; применяется для решения различных теоретич. и прикладных задач. Некоторые основные понятия. Граф совокупность точек (вершин) и совокупность пар этих точек (не… …   Химическая энциклопедия

  • ГРАФОВ ТЕОРИЯ — (THEORY OF GRAPHS) раздел математики, изучающий свойства разл. графов. Наиболее раннее упоминание о графах встречается в работе Л.Эйлера (1736). Окончательно как матем. дисциплина Г.т. оформилась в 1936 г. после выхода монографии Д. Кенига Теория …   Глоссарий терминов по грузоперевозкам, логистике, таможенному оформлению

  • ГРАФОВ ТЕОРИЯ — раздел математики, особенность к рого геом. подход к изучению объектов. Осн. понятие теории граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих нек рые пары вершин. Пример графа схема метрополитена: множество станций… …   Большой энциклопедический политехнический словарь

  • ГРАФОВ ТЕОРИЯ — раздел математики, особенность к рого геом. подход к изучению объектов. Осн. понятие теории граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих нек рые пары вершин. Пример графа схема метрополитена: множество станций… …   Естествознание. Энциклопедический словарь

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

  • Теория надёжности — Теория надёжности  наука, изучающая закономерности распределения отказов технических устройств, причины и модели их возникновения. Теория надёжности изучает методы обеспечения стабильности работы объектов (изделий, устройств, систем и т …   Википедия

Книги

  • Теория графов, Харари Ф.. В последнее время теория графов привлекает все более пристальное внимание специалистов различных областей знания. Наряду с традиционными применениями ее в такихнауках, как физика,… Подробнее  Купить за 663 руб
  • Теория графов, Ф. Харари. В последнее время теория графов привлекает все более пристальное внимание специалистов различных областей знания. Наряду с традиционными применениями ее в такихнауках, как физика,… Подробнее  Купить за 626 грн (только Украина)
  • Теория графов, О. Оре. Настоящая книга, написанная известным норвежским математиком Ойстином Оре, является одним из классических трудов по теории графов, имеющихся в мировой литературе. По сравнению со многими… Подробнее  Купить за 539 руб
Другие книги по запросу «ГРАФОВ ТЕОРИЯ» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»