АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Пример. В этом примере орграф содержит две вершины, имеющие полустепень захода, равную 0

В этом примере орграф содержит две вершины, имеющие полустепень захода, равную 0. Для данного графа невозможно построить остовное ордерево.

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

Возможно обратное преобразование. Если T=(X,B) – ориентированное дерево, то` T=(X,`B) – неориентированное дерево. ` B здесь – множество дуг дерева Т без учёта их ориентации.

§ 2.13. Сети. Потоки в сетях.

Если в орграфе G=(X,A),полустепень захода некоторой вершины s равно нулю (a_t(s)=0), то такая вершина называется источником. Если в орграфе G=(X,A) полустепень исхода некоторой вершины t равно нулю (a_O(s)=0), то такая вершина называется стоком.

Опр. Орграф с одним источником и с одним стоком называется сетью.

В теории графов встречается задача определения максимального потока, протекающего в орграфе G =(X,A), являющемся сетью, от источника s к стоку t. При этом каждой дуге (х_i,х_j) графа G приписана некоторая пропускная способность q_ij, и эта пропускная способность определяет наибольшее значение потока, который может протекать по данной дуге. Эта задача может возникнуть, например, при определении максимальной интенсивности транспортного потока между двумя пунктами на карте дорог, представляемой графом. Решение этой задачи также укажет ту часть сети дорог, которое образует «узкое место» в отношении потока между двумя концевыми пунктами.

Постановка задачи о максимальном потоке от s к t.

Рассмотрим сеть G =(X,A) с пропускными способностями дуг q_ij, источником s и стоком t, s,tÎX. Множество чисел x_ij, определённых на дугах (х_i,х_j)ÎA, называют потоками в дугах, если выполняется следующие условия:

(1)

(2)

Уравнение (1) является уравнением сохранения потока. Оно утверждает, что поток, втекающий в вершину, равен потоку, вытекающему из вершины, за исключением источника s и стока t, для которых существуют вытекание и приток величины v соответственно. Соотношение (2) указывает на то, что потоки ограничены пропускными способностями для каждой дуги графа G.

Задача состоит в том, чтобы величина

была максимальной.

Дата добавления: 2015-09-27 | Просмотры: 374 | Нарушение авторских прав