metod_15.03.04_atppp_moas_2016 (1016590), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

графы стали использоваться для представления некоторыхматематических объектов и формальной постановки различных дискретных задач; при этом наряду с термином «граф» употреблялись и другие термины,например, карта, комплекс, диаграмма, сеть, лабиринт. После выхода в свет в1936 году монографии Д. Кёнига термин «граф» стал более употребительным,чем другие. В этой работе были систематизированы известные к тому временифакты.

В 1936 году вышла небольшая брошюра Ойстена Оре, содержащая блестящее элементарное введение в теорию графов. В 1962 году в Англии была издана книга французского математика Клода Бержа “Теория графов и её прило-жение”. Обе книги, безусловно, представляют интерес для любителей занимательной математики. Сотни известных головоломок, на первый взгляд не имеющих ничего общего друг с другом, легко решаются с помощью теории графов.В 20-30-х годах 20 в.

появились первые результаты, относящиеся к изучению свойств связности, планарности, симметрии графов, которые привели к формированию ряда новых направлений в теории графов.Значительно расширились исследования по теории графов в конце 40-х начале 50-х годов, прежде всего в силу развития кибернетики и вычислительнойтехники. Благодаря развитию вычислительной техники, изучению сложных кибернетических систем, интерес к теории графов возрос, а проблематика теорииграфов существенным образом обогатилась. Кроме того, использование ЭВМпозволило решать возникающие на практике конкретные задачи, связанные сбольшим объемом вычислений, прежде не поддававшиеся решению.

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

Существуютнаправления, связанные с различными классификациями графов, например, посвойствам их разложения.Примером результата о существовании графов с фиксированными свойствами может служить критерий реализуемости чисел степенями вершин некоторого графа: набор целых чисел, 0  d 1  d 2  ...  dn сумма которых четна, можнореализовать степенями вершин графа без петель и кратных ребер тогда и толькотогда,когдадлялюбогоrвыполняетсяусловиеri1di  r (r 1)  in r 1min( r, di)Примерами задач о подсчете графов с заданными свойствами являютсязадачи о нахождении количеств неизоморфных графов с одинаковым числомвершин и (или) ребер.

Для числа неизоморфных деревьев с n вершинами былаполучена асимптотическая формула Tn  Cenn5 / 2 en , где C== 0,534948..., e== O n7 / 2 2,95576...Для числа Gn неизоморфных графов без петель и кратных ребер с n верn 5 1  2n(n  1)  8(3n  7)  O n  .n2n 5n / 2  n! 3(n  3)! 222шинами было показано, что Gn  2Наряду с проблемами, носящими общий характер, в теории графов имеются специфические циклы задач.

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

Известен простой критерий существования маршрута, содержащего все ребра графа: в связном графе цикл, содержащий все ребра и проходящий по каждому ребру один раз, существует тогдаи только тогда, когда все вершины графа имеют четные степени. В случае обходамножества вершин графа имеется только ряд достаточных условий существования цикла, проходящего по всем вершинам графа по одному разу. Характернымспецифическим направлением теории графов является цикл задач, связанный сраскрасками графов, в котором изучаются разбиения множества вершин (ребер),обладающие определенными свойствами, например, смежные вершины (ребра)должны принадлежать различным множествам (вершины или ребра из одногомножества окрашиваются одним цветом). Было доказано, что наименьшее числоцветов, достаточное для раскраски ребер любого графа без петель с максимальной степенью a, равно Зa/2, а для раскраски вершин любого графа без петель икратных ребер достаточно a+1 цветов.Существуют и другие циклы задач, некоторые из них сложились под влиянием различных разделов математики.

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

В частности, было доказано, что каждая конечная группа изоморфна группе автоморфизмов некоторого графа. Влияние теории вероятностейсказалось на исследовании графов случайных. Многие свойства были изученыдля «почти всех» графов; например, было показано, что почти все графы с n вершинами связаны, имеют диаметр 2, обладают гамильтоновым циклом (циклом,проходящим через все вершины графа по одному разу).В теории графов существуют специфические методы решения экстремальных задач. Один из них основан на теореме о максимальном потоке и минимальном разрезе, утверждающей, что максимальный поток, который можно пропустить через сеть из вершины U в вершину V, равен минимальной пропускнойспособности разрезов, разделяющих вершины U и V.

Были построены различныеэффективные алгоритмы нахождения максимального потока.Большое значение в теории графов имеют алгоритмические вопросы. Дляконечных графов, т. е. для графов с конечным множеством вершин и ребер, какправило, проблема существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение многих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допустимых вариантов.

Однако таким способом удается решить задачу только дляграфов с небольшим числом вершин и ребер. Поэтому существенное значениедля теории графов имеет построение эффективных алгоритмов, находящих точное или приближенное решение. Для некоторых задач такие алгоритмы построены, например, для установления планарности графов, определения изоморфизма деревьев, нахождения максимального потока.Результаты и методы теории графов применяются при решении транспортных задач о перевозках, для нахождения оптимальных решений задачи оназначениях, для выделения «узких мест» при планировании и управлении разработок проектов, при составлении оптимальных маршрутов доставки грузов, атакже при моделировании сложных технология, процессов, в построении различных дискретных устройств, в программировании и т.

д.Основные термины и теоремы теории графов.1.Граф - Пара объектов G = ( X , Г ) ,где Х - конечное множество ,а Г–конечное подмножество прямого произведения Х*Х . При этом Х называетсямножеством вершин, а Г - множеством дуг графа G .2.Любое конечное множество точек (вершин), некоторые из которыхпопарно соединены стрелками , (в теории графов эти стрелки называются дугами), можно рассматривать как граф.3.Если в множестве Г все пары упорядочены, то такой граф называюториентированным.4.Дуга- ребро ориентированного графа.5.Граф называется вырожденным, если у него нет рёбер.6.Вершина Х называется инцидентной ребру G , если ребро соеди-няет эту вершину с какой-либо другой вершиной.7.вершин V1Подграфом G(V1, E1) графа G(V, E) называется граф с множеством- такими, что каждое ребро(дуга) из E1 инцидентно (инцидентна) только вершинам из V1 .

Иначе говоря,подграф содержит некоторые вершины исходного графа и некоторые рёбра(только те, оба конца которых входят в подграф).Подграфом, порождённым множеством вершин U называется8.подграф, множество вершин которого – U, содержащий те и только те рёбра, обаконца которых входят в U.Подграф называется остовным подграфом, если множество его вер-9.шин совпадает с множеством вершин самого графа.10.Вершины называются смежными , если существует ребро , ихсоединяющее.11.Два ребра G1 и G2 называются смежными, если существует вер-шина, инцидентная одновременно G1 и G2.12.Каждый граф можно представить в пространстве множеством точек,соответствующих вершинам, которые соединены линиями, соответствующимиребрам (или дугам - в последнем случае направление обычно указывается стрелочками).

Характеристики

Список файлов учебной работы