Реферат: Графы

Содержание

Введение

1.  Графы, орграфы, деревья

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

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

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

5.  Построение максимальногопотока. Примеры разбираемых задач

Литература


Введение

В коммерческой деятельности большинство возникающих задач удобнопредставлять для восприятия и анализа в виде сетей, которые позволяют ответитьна два главных вопроса: до какого места необходимо дойти (цель) и какой путьследует избрать (как). Коммерческую деятельность можно рассматривать каксовокупность задач, предназначенных для передвижения, складирования ираспределения товаров, денег, документов, информации о поставках и покупателяхводы, нефти, газа, электроэнергии, теле- и радиосистем. Наглядность илогическая обоснованность методов сетевого анализа позволяет выбрать довольноестественный подход к решению задач коммерческой деятельности. Сетевые моделидля людей, не занимающихся научной работой, являются более понятными, чемдругие модели, поскольку для них все же лучше один раз увидеть, чем сто разуслышать. В значительной степени методы сетевого анализа основаны на теорииграфов – области математики, началом развития которой явилась задача окенигсбергских мостах, сформулированная швейцарским ученым Л. Эйлером в1736 г. Через реку Прегель, на которой стоял город Кенигсберг, построеносемь мостов (рис. 1), которые связывали с берегами и друг с другом два острова.Задача заключалась в том, чтобы пройти по всем мостам только один раз ивернуться обратно к началу маршрута. Эйлер доказал неразрешимость этой задачи.

Позже Д.К. Максвелли Г.Р. Кирхгоф на основе исследования электрических цепей сформулировалинекоторые принципы сетевого анализа. Были разработаны методы расчета наибольшейпропускной способности телефонных линий. В 40-х годах в результате развитиятеории исследования операций был разработан ряд математических методов,необходимых для анализа больших систем. В 50–60-х годах проводились работы попостроению новых сетевых моделей и разработке алгоритмов их решения на основеэлементов теории графов.


Графы, орграфы, деревья

/>

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

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

Эйлер доказал, что такая задача решения не имеет.

/>

Эйлер Леонард (1707–1783) швейцарский математик, механик, физик, астроном.Автор более 800 работ по различным разделам математики и другим наукам.

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

Пусть на плоскости задано некоторое множество вершин Xи множество Uсоединяющих их дуг. Графомназывают бинарное отношение множества Xи множеств U: G= = (X; U), или, иначе ƒ: X→ К Здесь ƒ – отображениеинциденций.

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

Граф называется петлей, если его начало и конец совпадают.

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

Ребро ujназывается инцидентнымвершине хj, если оно выходит или входит в вершину.

Степенью (валентностью) вершины называется число инцидентных ей ребер. Кратностьюпары вершин называется число соединяющих их ребер или дуг.

Подграфом Gaграфа Gназывается граф, вкоторый входит лишь часть вершин графа Gвместе с дугами ихсоединяющими.

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

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

Контур – это конечный путь, у которого начальная и конечная вершинысовпадают. Контур называется элементарным, если все его вершины различны(кроме начальной и конечной). Контур единичной дуги называется петлей.

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

Ребро – отрезок, соединяющий две вершины, цепь – последовательностьребер.

Цикл – конечная цепь, у которой начальная и конечная вершина совпадают.

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

Граф, который не является связанным, может быть разбит на конечноечисло связных графов, называемых компонентами, или частями.

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

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

На рисунке 3 ребро к – мост, а на рисунке 4 вершина 1 – точкасочленения.

/> /> /> /> />

/>

  <td/>

/>

  />

Неразделимым называется связный граф, не имеющий точек сочленения.

Блоком графа называют максимальный неразделимый подграф.

На рисунке 5 приведен граф G и его блоки А, В, С и D.

/>

 

Дерево это конечный, связный, неориентированный граф, не имеющий циклов.

Характеристическое свойство деревьев состоит в том, что любые две вершиныдерева соединены единственной цепью.

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

Кирхгоф Густав (1824–1887) немецкий физик, механик, математик.

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

Совокупность деревьев называется лесом.

Если все вершины графа принадлежат дереву, то он называется покрывающим.Пусть дано множество вершин графа. Одну из вершин, например х1,примем за начальную, которую назовем корнем дерева. Из этой вершины проводимребра к остальным вершинам х2, х3 и т.д.

Простейшее дерево состоит из двух вершин, соединенных ребром.

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

/>

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

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

Пусть имеется х1, х2,…, хn<sub/>вершин и u1, u2…, umдуг, их содержащих. Матрицейсмежности Sпорядка п называется матрица, состоящая изчисел S., равных сумме чисел ориентированных ребер, идущих из х в х. (иличисел неориентированных ребер, соединяющих эти вершины). Если дуга отсутствует,то Sr= 0.

Матрица смежности для ориентированного и неориентированного графа,вообще говоря, имеет разный вид. Запишем матрицу смежности 5, дляориентированного графа, изображенного на рисунке 7:

/>/>

 

 

 

 


Матрицей инциденции Т размера mxnназывается матрица,состоящая из чисел:

/> /> /> /> /> /> /> /> /> <td/> /> />

tij=

  /> />

Запишем матрицу инциденции для графа, изображенного на рисунке 7:

/>

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

Объединением двух, или более графов G1, U G2U … U Gn<sub/>называется граф, укоторого множество вершин и множество дуг объединены (рис. 8).

/>

/> <td/>

Рис. 8

 

/>


G1, U G2U…U Gn ' = {X1U X2U ...; U1, U U2 U ...).

 

/>

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

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

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

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

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

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

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

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

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

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

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

/>


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

aij=

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

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

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

1 2 3 4 5 6 7

А= />

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

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

1 2 3 4                        

А= />

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

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

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

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

bij= 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. Задача о максимальномпотоке заключается в поиске таких потоков jij по дугам (i, j) если, что результирующийпоток из источника в сток является максимальным.

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

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

V=å jsj =å jsj<sub/>Þ max;

j j

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

/>0<= jij<sub/><=cij

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

j j

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


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

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

Пусть задана сеть 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.

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

Определение. Увеличивающей цепью, соединяющей вход и выход сети,называется простая цепь, все дуги которой являются допустимыми.

Пример 1. Построим увеличивающую цепь для сети S=(N, U), представленной нарисунке 15.

/>


Над каждой дугой указана ее пропускная способность, в скобках – потокпо этой дуге.

Цепь (s, 1, 2, 4, t) является увеличивающей, так как все дуги – допустимые:

·          дуга(s, 1) – увеличивающая, таккак она проходит по направлению потока, и поток по ней меньше ее пропускнойспособности: 6 < 9;

·          дуга(1,2) – также увеличивающая дуга: 3 < 6;

·          дуга(2,4) – уменьшающая, так как она проходит против потока и поток по ней 2 >0;

·          дуга (4,t) – увеличивающая: 4 <7.

Пример 2. Построим максимальный поток для сети, представленной на рис. 4.16.

/>

Рис. 16


Начальное значение потока равно нулю V=0.

Увеличивающие цепи:

1)     (s, 1, 2, t), Dj = min (8, 4, 10) = 4;

2)     (s, 1, 3, 4, t), Dj = min (8–4, 3, 2, 9) =2.

Больше увеличивающих цепей построить нельзя.

Vmax = 6.

Построим теперь максимальный поток для неориентированной сети стой же структурой рис. 17.

/>

Рис. 17

Увеличивающие цепи:

1)       (s, 1, 2, t), Dj = 4;

2)       (s, 1, 3, 5, t), Dj = 3;

3)       (s, 3, 2, t), Dj = 2;

4)       (s, 3, 4, t), Dj = 2.

Больше увеличивающих цепей не существует. Максимальный поток Vmax = 7+4 = 9+2 = 11.Оптимальная ориентация показана на рис. 18.

/>

Рис. 18


Литература

1.  Гончарова Г.А., Молчалин А.А. «Элементыдискретной математики»: Учебное пособие. М.: ФОРУМ: ИНФРА-М, 2005. (Серия«профессиональное образование»).

2.  Фомин Г.П.«Математические методы и модели в коммерческой деятельности»: Учебник. – М.:Финансы и статистика, 2007.

еще рефераты
Еще работы по математике