44977 (Нахождение кратчайшего пути), страница 2

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

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

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

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

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

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

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

1.2. Основные термины и теоремы теории графов.

1. Граф - Пара объектов G = ( X , Г ) ,где Х - конечное множество ,а Г –конечное подмножество прямого произведения Х*Х . При этом Х называется множеством вершин , а Г - множеством дуг графа G .

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

3. Если в множестве Г все пары упорядочены, то такой граф называют ориентированным .

4. Дуга- ребро ориентированного графа.

5. Граф называется вырожденным, если у него нет рёбер.

6. Вершина Х называется инцидентной ребру G , если ребро соединяет эту вершину с какой-либо другой вершиной.

7. Подграфом G(V₁, E₁) графа G(V, E) называется граф с множеством вершин V₁ V и множеством ребер (дуг) E_ E, - такими, что каждое ребро (дуга) из E₁ инцидентно (инцидентна) только вершинам из V₁ . Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

8. Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого – U, содержащий те и только те рёбра, оба конца которых входят в U.

9. Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

10. Вершины называются смежными , если существует ребро , их соединяющее.

11. Два ребра G₁ и G₂ называются смежными, если существует вершина, инцидентная одновременно G₁ и G₂.

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

13. Доказано, что в 3-мерном пространстве любой граф можно представить в виде укладки таким образом, что линии, соответствующие ребрам (дугам) не будут пересекаться во внутренних точках. Для 2-мерного пространства это, вообще говоря, неверно. Допускающие представление в виде укладки в 2-мерном пространстве графы называют плоскими (планарным).
    Другими словами, планарным называется граф, который может быть изображен на плоскости так, что его рёбра не будут пересекаться.

14. Гранью графа, изображенного на некоторой поверхности, называется часть поверхности, ограниченная рёбрами графа.

Данное понятие грани, по - существу, совпадает с понятием грани многогранника. В качестве поверхности в этом случае выступает поверхность многогранника. Если многогранник выпуклый, его можно изобразить на плоскости, сохранив все грани. Это можно наглядно представить следующим образом: одну из граней многогранника растягиваем, а сам многогранник «расплющиваем» так, чтобы он весь поместился внутри этой грани. В результате получим плоский граф. Грань, которую мы растягивали «исчезнет», но ей будет соответствовать грань, состоящая из части плоскости, ограничивающей граф.

Таким образом, можно говорить о вершинах, рёбрах и гранях многогранника, а оперировать соответствующими понятиями для плоского графа.

1. Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные.

2. Конечная последовательность необязательно различных рёбер E₁,E₂,...E_n называется маршрутом длины n, если существует последовательность V₁, V₂, ... V_n необязательно различных вершин, таких, что E_i = (V_i-1,V_i ).

3. Если совпадают, то маршрут замкнутый.

4. Маршрут, в котором все рёбра попарно различны, называется цепью.

5. Замкнутый маршрут, все рёбра которого различны, называется циклом. Если все вершины цепи или цикла различны, то такая цепь или цикл называются простыми.

6. Маршрут, в котором все вершины попарно различны, называется простой цепью.

7. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.

8. Граф называется связным, если для любых двух вершин существует путь, соединяющий эти вершины.

9. Любой максимальный связный подграф (то есть, не содержащийся в других связных подграфах) графа G называется компонентой связности. Несвязный граф имеет, по крайней мере, две компоненты связности.

10. Граф называется k - связным (k - реберно - связным), если удаление не менее k вершин (ребер) приводит к потере свойства связности.

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

12. Длина маршрута (цепи, простой цепи) равна количеству ребер а порядке их прохождения. Длина кратчайшей простой цепи, соединяющей вершины v_i и v_j в графе G, называется расстоянием d (v_i, v_j) между v_i и v_j.

13. Степень вершины - число ребер, которым инцидентна вершина V, обозначается D(V).

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

Среди одноместных операций наиболее употребительны: удаление и добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин), подразбиение ребра (т.е. замена ребра (u, v) на пару (u, w), (w, v), где w - новая вершина) и др.

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

1. Два графа G₁=(V₁;E₁), G₂=(V₂;E₂),называются изоморфными, если существует взаимнооднозначное соответствие между множествами вершин V₁ и V₂ и между множествами рёбер Е₁ и Е₂, такое, чтобы сохранялось отношение инцидентности.

  Понятие изоморфизма для графов имеет наглядное толкование. Представим рёбра графов эластичными нитями, связывающими узлы – вершины. Тогда, изоморфизм можно представить как перемещение узлов и растяжение нитей.

Теорема 1.

Пусть задан граф G=(V;E),где V - множество вершин, E - множество рёбер, тогда 2[E]=Σ(V), т.е. удвоенное количество рёбер равно сумме степеней вершин.

Теорема 2. (Лемма о рукопожатиях)

В конечном графе число вершин нечетной степени чётно.

Теорема 3.

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

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

Свойства связных графов.

1. Связный граф остается связным после удаления ребра тогда и только тогда, когда это ребро содержится в цикле.

2. Связный граф , имеющий К вершин , содержит по крайней мере К-1 ребро.

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

4. В графе с N вершинами и К компонентами связности число рёбер не превышает 1/2(N-K)(N-K+1).

5. Пусть у графа G есть N вершин . Пусть D(G)- минимальная из степеней вершин этого графа . Тогда D(G) > 1/2 (N-1).

1. Связный граф без циклов называется деревом.

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