logo
Графы

Операции над графами

Объединением двух, или более графов 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 городов, зайдя в каждый город, вернуться домой, причем протяженность пути должна быть минимальной. Таким образом, среди всех гамильтоновых циклов графа с п вершинами нужно найти сумму длин ребер, путь по которым будет минимальным. Математически эта задача решения не имеет.

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

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

Построение деревьев решений используют при решении задач динамического распределения памяти ЭВМ. В динамическом программировании решение задачи планирования работ называют проектом. Нужно выбрать наилучший проект за заданное время с использованием выделенных ресурсов. Существуют два способа математического решения этой задачи.

Метод кратчайшего пути.

Проект оценки и пересмотра проекта.

Характерным для этих методов является изображение проекта в виде сети взаимосвязанных работ.