Ви є тут

Часть 4. Способы задания графов

Взвешенные графы

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

Матрицей  весов называется квадратная матрица размерности  p´p ( –  количество вершин), элемент которой стоящий в i строке и  j столбце определяется по правилу:

 

ПРИМЕР 

Найти матрицу весов для графа.

Матрица  весов имеет вид:

 .

 

Тема 4.10. Гамильтоновы графы

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

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

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

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

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

1. Выбрать исходную вершину и включить её в маршрут.

2. Выбрать вершину ближайшую к данной по весу, включить её в маршрут.

3. Выбрать не использованные вершины ближайшую к последней, включить её в маршрут.

4. Вернуться к шагу 2 если не использованы все вершины.

5. Включить в маршрут исходную вершину.

ПРИМЕР 

Найти  Гамильтонов цикл наименьшего веса.

Начнем поиск Гамильтонова цикла с вершины А и будем суммировать веса ребер, получим маршрут АBEDCFA, вес которого 3+3+5+5+1+7=24.

 

Тема 4.11. Эйлеровы графы

В начале главы речь шла о  классической задаче о кенигсбергских мостах, имя математика решившего ее (Леонард Эйлер), дало названия таким понятиям как эйлеров цикл и эйлеров граф.

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

Теорема.  Граф является Эйлером тогда и только тогда, когда степени всех его вершин четные.

Задача о поиске эйлерова цикла в данном графе имеет практическое значение.

ПРИМЕР

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

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

Вершины графа G и цикла Р  имеют четные степени. То же можно сказать и про остающийся подграф G'Так как граф G связен, то и  Р должна найтись вершина аS, инцидентная какому-то ребру из G'. Из аможно построить новый маршрут Р'содержащий ребра только из подграфа G'Такой маршрут может закончиться только при возвращении в вершину аS. Но тогда из Р и Рможно составить новый цикл Р'', который возвращается в а и содержит больше ребер, чем Р. Если Р''  не является эйлеровым циклом, то это построение повторяется. Когда процесс закончится, эйлеров цикл будет построен.

Тема 4.12. Деревья

Граф называется деревом, если он   связан и не имеет циклов.

Свойства деревьев

1.          Любая пара вершин соединена единственным маршрутом.

2.          Количество ребер меньше на одну чем вершин.

3.          Удаление хотя бы одного ребра не нарушает его структуру.

4.          если в дерево добавить хотя бы одно ребро то появиться цикл.

Дерево называется деревом с корнем, если одна вершина выделена и расположена выше остальных.

Вершины, расположенные под одной вершиной, называется  ее сыновьями, а сама вершина отцом.

Вершины, не имеющие сыновей, называются листьями.

Вершины отличные от корня и листьев называют внутренними.

Дерево корнем, которого является одна из вершин данного дерева, называется  поддеревом.

Деревья используются для описания структур организаций, предприятий и др. Такие структуры называются иерархическими. Примером может быть структура управления, где корень дерева - управляющий, с ним связаны непосредственно подчиненные ему руководители - вершины 1-го уровня, которым, в свою очередь непосредственно подчинены другие - вершины 2-го уровня и так вплоть до исполнителей нижнего уровня – листьев. Дерево образует структура предприятия, где корень - само предприятие, под ним - входящие в него цехи и службы, ниже - входящие в цехи участки и т.д.

 

Дерево решений

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

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

 

Минимальное остовное дерево

 Если ребра графа взвешены, то возникает задача выделения остова с минимальной или максимальной оценкой.

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

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

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

Рассмотрим алгоритм решения задачи: жадный алгоритм.

Жадный алгоритм

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

ПРОСМОТР

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

    Алгоритм Прима

1. Включим  любую вершину в остов.

2. Рассмотрим все ребра, исходящие из вершин, включенных в остов к оставшимся вершинам, и из них выберем ребро с минимальным весом. Его концевую вершину включим в остов. Повторяем этот пункт, пока не все вершины включены в остов.

Просмотр

В этом алгоритме не нужно следить за образованием циклов. Алгоритм начинает работу с произвольно выбранной вершины.

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer