Операции над графами
Объединением двух, или более графов G1, U G2 U … U Gn называется граф, у которого множество вершин и множество дуг объединены (рис. 8).
Суммой графов G1 и G2 называется граф, определяемый как объединение графов, причем каждая вершина, не вошедшая в объединение, соединяется с другими вершинами (рис. 9).
Будем говорить, что вершина иj конусирует граф G, если она смежная со всеми вершинами графа.
Произведением двух графов называется граф
G1 * G2 = {(Xj1; Xj2) Є G1 * G2}.
Вершина представляет собой бинарное отношение, т.е. вершин у нас будет 6.
Рассмотрим подробно решение задачи о Кенигсбергских мостах. В городе Кенигсберге имеется остров Кнайпхоф, который охвачен двумя рукавами реки Пречель.
Через два рукава перекинуты семь мостов: а, Ь, с, d, e, ?, g. Можно ли спланировать прогулку таким образом, чтобы по каждому мосту пройти только один раз и вернуться в начальное положение? Поставим в соответствие каждому мосту ребро графа, а суше вершину (рис. 11).
Эйлеровым путем в графе G называется такой путь в котором каждое ребро встречается один раз. Эйлер доказал, что такой путь существует тогда и только тогда, когда граф G содержит не более двух вершин нечетной степени и являются связными. В данной задаче существует четыре вершины нечетной степени (5, 3, 3, 3). Таким образом, задача о Кенигсбергских мостах не содержит Эйлеров путь и не имеет решения.
Если граф содержит точно две вершины нечетной степени, то в эйлеровом пути эти вершины должны быть конечными.
Если вершин нечетной степени нет, то граф имеет замкнутый эйлеров путь.
На рисунке 12, а нет замкнутого эйлерова пути; на рисунке 12, б эйлеров путь замкнут.
Теорема 4. (теорема Эйлера). В любом конечном графе сумма степеней вершин равна удвоенному числу его ребер. В XIX в. Гамильтон придумал игру, состоящую в том, что на доске располагались города в виде додекаэдра (рис. 13).
Играющий (игрок) должен обозначить шнуром замкнутый круг, соединяющий последовательно одну вершину с другой, посетив при этом все города, зайдя в каждый только один раз. Граф G называют Гамильтоновым, если он содержит простейший путь, проходящий через его вершину.
Задача о коммивояжере принадлежит к классу задач математического программирования. Требуется найти такой путь коммивояжера, по которому необходимо посетить и-1 городов, зайдя в каждый город, вернуться домой, причем протяженность пути должна быть минимальной. Таким образом, среди всех гамильтоновых циклов графа с п вершинами нужно найти сумму длин ребер, путь по которым будет минимальным. Математически эта задача решения не имеет.
Дерево игры - это способ описания игры, в которой последовательно, по ходам, фиксируется, какой информацией должны располагать игроки, какие варианты они могут выбрать, а также средний размер платежей в конце игры. Игра, описываемая при помощи такого дерева, называется игрой в развернутой форме или позиционной игрой.
Дерево решений - это система, отражающая структуру оптимизации задачи принятия решений. Ветви - это события, которые имеют место, а вершины - состояния в которых возникает проблема выбора. Узлы выбора различны. В одних решения принимает руководитель, в других выбор производит «природа», т.е. выбор ситуации от руководителя не зависит и он может только оценить вероятность принятия того или иного решения. Дерево решений применяется тогда, когда количество альтернатив и принятых решений конечно.
Построение деревьев решений используют при решении задач динамического распределения памяти ЭВМ. В динамическом программировании решение задачи планирования работ называют проектом. Нужно выбрать наилучший проект за заданное время с использованием выделенных ресурсов. Существуют два способа математического решения этой задачи.
Метод кратчайшего пути.
Проект оценки и пересмотра проекта.
Характерным для этих методов является изображение проекта в виде сети взаимосвязанных работ.
- 18. Полный граф. Пустой граф. Дополнение графа. Двудольный граф. Полный двудольный граф. Планарный граф. Однородный граф. Подграф. Частичный граф. Примеры.
- 9. Графы Определение графа
- 1.1 Граф. Ориентированный граф
- Лекция 20. Графы Графы
- § 4. Полные графы. Двудольные графы. Однородные и реберные графы
- 15. Графы. Представления графов. Пути в графах
- 27. Виды графов: двудольные графы, регулярные графы, полные графы, деревья, планарные графы