Различные способы задания графов

1. Графическое изображение графов.

2. Задание графа перечислением множества вершин и множества ребёр и (или) дуг.

3. Матричное представление графов.

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

 

Рис.6.2 Рис.6.3

Рис.6.4 Рис.6.5

Задание графа перечислением множества вершин и множества ребёр и (или) дуг состоит в том, что задают множество вершин V и множество линий P (множества ребёр и (или) дуг), которое показывает, как между собой связаны вершины.

Задание графа перечислением множества вершин и
множества ребёр и (или) дуг и его графическое изображение рассматриваются в примерах 6.1− 6.3.

Пример 6.1. Рассмотрим неориентированный граф G =(V, E), где множества V ={ v ₁, v ₂, v ₃}, E ={ e ₁={ v ₁, v ₂}, e ₂={ v ₁, v ₃}}. Его графическое изображение:

 

 

Рис.6.6

Пример 6.2. D =(V, X) – орграф, где V ={ v ₁, v ₂, v ₃}, X ={ x ₁=(v₂, v ₁), x ₂=(v ₁, v ₂), x ₃=(v ₂, v ₃)}. Изображение этого графа:

 

Рис.6.7

Пример 6.3. Граф G =(V, P), где V ={ v ₁, v ₂, v ₃}, P ={{ v ₁, v ₃}, (v ₁, v ₂), (v ₂, v ₃)} – смешанный и может быть изображен следующим образом:

 

Рис.6.8

Матричное представление графов удобно для обработки графов на ЭВМ.

Матрица смежности

Пусть G =(V, E) – неориентированный граф, где V ={ v ₁, v ₂,…, v_n } – множество вершин, E ={ e ₁, e ₂, …, e_k } – множество ребёр.

Определение. Матрицей смежности неориентированного графа G =(V, E) называется симметричная матрица A (G)=(a_ij) размерности n x n, где

Заметим, что петля (ребро из i -й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента a_ii в этом случае равно удвоенному числу петель вокруг i -й вершины. В зависимости от конкретных приложений, элемент a_ii может считаться равным либо 1, либо 2.

Из определения непосредственно вытекают основные свойства матриц этого вида:

1) матрица смежностей вершин неориентированного графа A (G) является квадратной и симметричной относительно главной диагонали;

2) элементами матрицы A (G) являются целые положительные числа и число ноль;

3) сумма элементов матрицы A (G) по i -й строке (или по i- му столбцу) равна степени соответствующей вершины d(v_i).

1. Пусть D =(V, X) – орграф, где V ={ v ₁, v ₂,…, v_n } – множество вершин, X ={ x ₁, x ₂, …, x_k } – множество дуг.

Определение. Матрицей смежности орграфа D =(V, X) называется матрица A (D)=(a_ij) размерности n x n, где

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

Пример 6.4. Рассмотримграф G =(V, E), изображенный на рисунке:

Рис.6.9

М атрица смежности для этого графа: .

Матрица инцидентности.

Пусть G =(V, E) – неориентированный граф, где V ={ v ₁, v ₂,…, v_n } – множество вершин, E ={ e ₁, e ₂, …, e_k } – множество ребёр.

Определение. Матрицей инцидентности неориентированного графа G =(V, E) называется матрица B (G)=(b_ij) размерности n x k, где

Пусть D =(V, X) – орграф, где V ={ v ₁, v ₂,…, v_n } – множество вершин, X ={ x ₁, x ₂, …, x_k } – множество дуг.

Определение. Матрицей инцидентности орграфа D =(V, X) называется матрица B (D)=(b_ij) размерности n x k, где

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

Пример 6.5. Рассмотрим простой неориентированный граф

 

Рис.6.10

Его матрица инцидентности

Маршруты, пути, деревья

Определение. Путь из v ₁ в v_t+1 ворграфе D= (V, X) - последовательность вершин и дуг v ₁, x ₁, v ₂, x ₂,..., v_t, x_t, v_t+1, где t >0, причем каждая вершина v_i Î V, а каждая дуга x_i Î X, и x_i всегда является дугой (v_i,v_{i +1}).

Определение. Цепь в неориентированном графе G= (V, E) - последовательность вершин и ребер v ₁, e ₁, v ₂, e ₂,..., v_t, e_t, v_{t +1}, где t >0, причем каждая вершина v_i Î V, а каждое ребро e_i Î E, и e_i всегда является ребром { v_i, v_i+1 }.

Иногда, когда кратности дуг (рёбер) равны 1, то путь (цепь) записывают просто последовательностью вершин v ₁, v ₂,..., v_t, v_{t +1}.

Возвратимся к рисункам 6.2-6.5 Маршрутом (путем) в графе, соединяющим вершины А и В, называется такая последовательность его ребер, в которой каждые два ребра имеют общую концевую точку, причем первое ребро выходит из вершины А, а последнее входит в вершину В (рис. 6.3). При этом маршрутами от точки А до точки В могут быть АDB или FCEDB и т.д.

Граф называется связанным, если для любых двух его вершин может быть указан маршрут, по которому из одной вершины можно попасть в другую. Графы на рис.6.2 и 6.3 – связанные, на рис.6.4 представлен несвязанный граф.

Цепью называется маршрут, не содержащий повторяющихся ребер. Вершины в цепи могут повторяться несколько раз. Например, маршрут ADCEDB на рис.6.5 является цепью, а маршрут ACDECDB цепью не является. Цепь, начальная и конечная вершины которой совпадают, называется циклом, например цепь ADECA на рис. 2.

Вершина называется четной, если в ней сходится четное число ребер, и нечетной, если сходящееся в ней число ребер нечетно. На рис.4 вершина С - четна, вершина D – нечетна.

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

Конечнымграфом называется граф с конечным числом ребер.

Граф, все вершины которого четны, называется эйлеровым графом.

Теорема Эйлера. В любом конечном связанном графе, все вершины которого четны, существует цикл, в котором каждое ребро графа участвует ровно один раз. Такой цикл называют эйлеровым циклом.

Метод определения эйлерова цикла рассмотрим на примере.

Пример 6.6. Определить эйлеров цикл для графа, представленного на рис.6.11. За начальную вершину принять вершину А.

Решение.

Прежде всего убедимся, что данный граф – эйлеров. В вершину А можно вернуться пройдя, например, по ребрам 1, 2, 3, 4, 5, 6. В построенный нами цикл входят не все ребра. Поэтому продолжим исследования. В полученном нами цикле обязательно есть вершина, из которой выходят еще не пройденные ребра. Этих ребер будет четное число. Пусть это вершина В. Построим вторую цепь из вершины В, привлекая только не пройденные ранее ребра.

Теперь, совместив первый и второй циклы, получим суммарный цикл.

Этот цикл можно пройти следующим образом. Из вершины А, проходя по ребрам 1, 2, 3, доходим до вершины В. Затем проходим по второму циклу 7, 8, 9 и возвращаемся в вершину В. Далее по ребрам 4, 5, 6 возвращаемся в вершину А.

Наконец, из вершины С строим третий цикл. Совместив его с двумя предыдущими, построим цикл 1, 2, 3, 7, 10, 11, 12, 8, 9, 4, 5, 6, в который входят все ребра графа (см. рис.6.11)

Рис.6.11

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

Если заданный граф допускает гамильтонов цикл, то он называется гамильтоновым графом.

Важный класс графов составляют так называемые деревья. Деревом называется связанный граф, который не имеет циклов (рис. 17).

Рис. 6.12

Число В вершин дерева и число Р его ребер различаются на единицу:

В = Р +1.

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

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

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

1. Если он останавливает свой выбор на университете штата и бизнесе, то вероятность успеха (получение диплома) считается равной 0,60.

2. Если он останавливает свой выбор на университете штата и инжиниринге, то вероятность успеха считается равной 0,70.

3. Если он останавливает свой выбор на университете г. А и бизнесе, то вероятность успеха считается равной 0,90.

4. Если он останавливает свой выбор на университете г. А и инжиниринге, то вероятность успеха считается равной 0,95.

5. Средний доход за год в течение первых пяти лет у окончившего бизнес-школу университета штата при условии полной занятости равен 35 тыс. долл.

6. Средний доход за год в течение первых пяти лет у окончившего школу инжиниринга университета штата при условии полной занятости равен 30 тыс. долл.

7. Средний доход за год в течение первых пяти лет у окончившего бизнес-школу университета г. А при условии полной занятости равен 24 тыс. долл.

8. Средний доход за год в течение первых пяти лет у окончившего школу инжиниринга университета г. А при условии полной занятости равен 25 тыс. долл.

9. Если по каким-либо причинам выпускник не поступает ни в один из этих университетов, то его средний доход в течение этих пяти лет при условии полной занятости будет равен 18 тыс. долл.

Предположим, что единственным критерием при принятии выпускником окончательного решения является величина ожидаемого среднего дохода в первые пять лет его трудовой деятельности. Сделав это предположение, попробуем решить проблему выпускника, используя дерево решений (рис. 6.13).

Рис. 6.13

Поясним некоторые обозначения на рисунке:

S ₁ - окончание бизнес-школы университета штата,

S ₂ - либо неудача при поступлении в бизнес-школу университета штата, либо невозможность завершения обучения,

S ₃ - окончание школы инжиниринга университета штата,

S ₄ - либо неудача при поступлении в школу инжиниринга университета штата, либо невозможность завершения обучения,

S ₅ - окончание бизнес-школы университета города А,

S ₆ - либо неудача при поступлении в бизнес-школу университета города А, либо невозможность завершения обучения,

S ₇ - окончание школы инжиниринга университета города А,

S ₈ - либо неудача при поступлении в школу инжиниринга университета города А, либо невозможность завершения обучения,

d ₁ - выбор университета штата,

d ₂ - выбор университета города А,

d ₃ - предпочтение отдано бизнесу,

d ₄ - предпочтение отдано инжинирингу.

Узлы дерева, в которых делается выбор, обозначены квадратиками; узлы дерева, которые принимающий решение не контролирует, - кружками.

Эти два типа узлов рассчитываются по-разному.

При расчете узлов 4-7 определяются ожидаемые значения:

значение в узле 7

N ₇ = (0,95)(25000) + (0,05) (18000) = 24650 долл.,

значение в узле 6

N ₆ = (0,90)(24000) + (0,10)(18000) = 23400 долл.,

значение в узле 5

N ₅ = (0,70) (30000) + (0,30)(18000) = 26400 долл.,

значение в узле 4

N ₄ = (0,60) (35000) + (0:40) (18000) = 28200 долл.

Значение N ₃ в узле 3 определяется так:

вследствие того что N ₇ > N ₆, полагаем N ₃ = N ₇. И считаем, что выбор d ₄ предпочтительнее d ₃.

Тем самым, N ₃ = 24650 долл.

Рис. 6.14

Значение N₂ в узле 2 определяется так:

вследствие того что N ₄ > N ₅, полагаем N ₂ = N ₄ и считаем, что выбор d ₃ предпочтительнее выбора d ₄.

Тем самым, N ₂ = 28200 долл.

Значение N ₁ в узле 1 определяется так:

вследствие того что N ₂ > N ₃, полагаем N ₁ = N ₂ и считаем, что выбор d ₁ предпочтительнее выбора d ₂.

Тем самым, N ₁ = 28200 долл.

Наносим результаты расчетов на рис. 6.13 и принимаем окончательное решение (рис. 6.14).

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

Глава 7. Элементы сетевого планирования и управления

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

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

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

Первый вариант этого метода был разработан в 1957 г. американскими учеными Дж. Е. Келли и М. Р. Уокером и был назван СРМ (от начальных букв выражения «Critical Path Method», означающего «Метод критического пути»). Примерно в то же время независимо от СРМ появилась система РЕRT («Program Evaluation and Review Technique», что означает «Техника обзора и оценки программ»). В результате дальнейшего развития эти системы превратились в совокупную методику построения графиков – сетевое планирование и управление.