Графы (стр. 2 из 3)

Суммой графов G₁ и G₂ называется граф, определяемый как объединение графов, причем каждая вершина, не вошедшая в объединение, соединяется с другими вершинами (рис. 9).

Будем говорить, что вершина и_jконусирует граф G, если она смежная со всеми вершинами графа.

Произведением двух графов называется граф

G₁ * G₂= {(X_j₁; X_j₂) Є G₁* G₂}.

Вершина представляет собой бинарное отношение, т.е. вершин у нас будет 6.

Рассмотрим подробно решение задачи о Кенигсбергских мостах. В городе Кенигсберге имеется остров Кнайпхоф, который охвачен двумя рукавами реки Пречель.

Через два рукава перекинуты семь мостов: а, Ь, с, d, e, ƒ, g. Можно ли спланировать прогулку таким образом, чтобы по каждому мосту пройти только один раз и вернуться в начальное положение? Поставим в соответствие каждому мосту ребро графа, а суше вершину (рис. 11).

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

Если граф содержит точно две вершины нечетной степени, то в эйлеровом пути эти вершины должны быть конечными.

Если вершин нечетной степени нет, то граф имеет замкнутый эйлеров путь.

На рисунке 12, а нет замкнутого эйлерова пути; на рисунке 12, б эйлеров путь замкнут.

Теорема 4. (теорема Эйлера). В любом конечном графе сумма степеней вершин равна удвоенному числу его ребер. В XIX в. Гамильтон придумал игру, состоящую в том, что на доске располагались города в виде додекаэдра (рис. 13).

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

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

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

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

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

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

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

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

Хранение графов в ЭВМ

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

Известно несколько типов матриц, позволяющих задавать граф.

Матрицей смежности графа, содержащего n-вершин, называется квадратная матрица А_nxn, каждый элемент которой а_ij определяется следующим образом:

1, если вершины i и j соединены ребром или дугой;

a_ij=

0, в противном случае.

Для графа с кратными ребрами (дугами) вместо 1 записывается число ребер (дуг) между вершинами i и j.

Для неориентированного графа, матрица смежности имеет размерность (7 х 7) и записывается в виде

1 2 3 4 5 6 7

А=

Слева и сверху проставлены номера вершин.

Для ориентированного графа, матрица смежности имеет размерность (4 х 4) и записывается в виде

1 2 3 4

А=

Матрицу смежности чаще применяют для задания неориентированного графа. Для задания ориентированного графа лучше использовать матрицу инцидентности.

Матрицей инцидентности ориентированного графа с n вершинами и m ребрами называется матрица В с n строками и m столбцами, элемент которой b_ij определяется следующим образом:

1, если вершина является началом ребра (i, j);

-1,если вершина является концом ребра (i, j);

b_ij= 2, если вершина и начало, и конец ребра (i, j);

0, если вершина и ребро не инцидентны.

Для ориентированного графа, матрица инцидентности В_4х5 имеет следующий вид:

1 2 3 4 5

В=

Взвешенный ориентированный граф без петель, в котором выделено k-вершин, называемых полюсами, является k-полюсной цепью. Среди сетей особо выделяется двухполюсная транспортная сеть (рис. 14) S=(N, U) с множеством вершин N и множеством дуг U, для которых выполняется следующее условие:

1) существует только одна вершина сети s є N, в которую не заходит ни одна дуга. Эта вершина называется входом, или истоком сети;

2) существует только одна вершина сети tє N, из которой не выходит ни одной дуги сети. Эта вершина называется выходом, или стоком сети;

3) каждой дуге сети u є U поставлено в соответствие неотрицательное число с(u), называемое пропускной способностью дуги.

Рис. 14

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

Примерами дуг сети могут быть дороги, линии электропередачи, телефонные линии, авиалинии, водные магистрали, нефте- и газопроводы.

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

Задача о максимальном потоке

Рассмотрим двухполюсную сеть S=(N, U) с одним входом (источником) s є N и выходом (стоком) t є N, дуги сети (i, j) є U имеют ограниченную пропускную способность с_ij. Задача о максимальном потоке заключается в поиске таких потоков j_ij по дугам (i, j) если, что результирующий поток из источника в сток является максимальным.

Математическая модель задачи о максимальном потоке выглядит следующим образом:

найти такие значения j_ij_, при которых

V=åj_sj =åj_sjÞmax;

при ограничениях:

0<= j_ij<=c_ij

åj_ij -åj_ij=0 i є N i¹s i¹t.

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

Построение максимального потока

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

Пусть задана сеть S=(N, U) с множеством вершин N и множеством дуг U.

Определение. Дуга u є U, соединяющая вершины i є N, j є N сети S, называется допустимой дугой, если она обладает одним из следующих свойств:

1) направление дуги совпадает с направлением потока, и значение потока по этой дуге меньше ее пропускной способности:

u=(i, j), j(u)<c(u);

2) направление дуги противоположного направлению потока, и величина потока отлична от нуля:

u=(j, i), j(u)>0.

Дуги, обладающие первым свойством, называют увеличивающими; дуги, обладающие вторым свойством, – уменьшающими.