Часть II. Графы

Часть II. Графы

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

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

Мы должны изучить основные понятия теории графов и некоторые задачи, связанные с ними. Терминология этого раздела дискретной математики не является общеупотребительной, она своя у разных авторов. Мы будем придерживаться определений из [6]. Если вы пользуетесь другими пособиями, сравнивайте, какие понятия совпадают с [6], а какие отличаются. Рассмотрим эти понятия на примерах.

Пример. Дан граф G:

1. Определить степени всех вершин графа.

2. Записать матрицу смежности вершин .

3. Записать матрицу инцидентности .

4. Указать мосты и точки сочленения, если они есть.

5. Проверить, является ли граф эйлеровым.

6. Проверить, является ли граф гамильтоновым.

7. Проверить, является ли граф двудольным. Если да, указать подмножества V₁ и V₂.

8. Записать какой-нибудь маршрут от до .

9. Указать какой-нибудь простой цикл.

10. Построить дерево, покрывающее граф.

Решение. 1.Степенью вершины графа называется количество рёбер, инцидентных ей. Вершине инцидентно лишь одно ребро e₁, значит, , а вершине инцидентны ребра , , , значит, и т.д. Составим таблицу.

2.Матрица смежности вершин.

, где — число вершин, равно количеству рёбер, соединяющих вершины и .

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

В нашем примере , так как нет петель, , так как вершина смежна , и т.д.

3.Матрица инцидентности имеет m строк (m-количество рёбер) и n столбцов, , если ребро инцидентно вершине , и в противном случае.

Так для графа G , так как ребро инцидентно вершине , , а .

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

Ребро с таким свойством называется мостом.

В графе G точками сочленения являются вершины Действительно, при удалении вершины связный граф G превращается в две компоненты,

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

При удалении получим

Мостами являются рёбра и .

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

6. Критерия гамильтоновости графа не существует. Однако при наличии висячих вершин (вершин степени 1), мостов или точек сочленения граф гамильтоновым не будет. В графе G есть и висячие вершины, и мосты, и точки сочленения. Следовательно, граф не является гамильтоновым.

7. Необходимым и достаточным условием двудольности графа является отсутствие в нём циклов нечётной длины. В графе G есть циклы длины 3: и . Следовательно, граф G не является двудольным.

Если бы нам был дан граф G₁,
полученный из G удалением ребра e₈, то он был бы двудольным. В G₁ ко множеству V₁ отнесём вершину обведём её кружочком, смежную с ней вершину отнесём ко множеству V₂, смежные вершины и , отнесём к V₁ и обведём кружочком и т.д. Данный двудольный граф удобно изобразить иначе, выделяя множества V₁ и V₂.

8. Маршрутом от v₁ до v₉ в графе G может служить последовательность рёбер: ( , , , , , , ).

9. Простым циклом может служить ( , , , ), или ( , , ) или ( , , , ).

10. Граф G содержит n=9 вершин и m=11 рёбер. Чтобы получить дерево, покрывающее граф (а дерево содержит рёбер на единицу меньше чем вершин, т.е. 8), удалим 11—8=3 ребра, входящие в циклы так, чтобы граф оставался связным, например: , , .

Получим дерево, покрывающее граф:

Можно получить и другие деревья, покрывающие граф G.

Пример. Дан орграф G.

1. Построить матрицу смежности вершин .

2. Построить матрицу инцидентности .

3. Проверить, является ли граф эйлеровым. Если да, построить эйлеров цикл

Решение. 1. В матрице смежности для ориентированного графа элемент равен количеству дуг с началом в вершине и концом в вершине . В частности, для графа G для i=1, 2, 4, , так как в вершине имеется петля . Элементы , так как вершины и соединены двумя противоположно направленными дугами. В остальных случаях .

2. В матрице инцидентности ориентированного графа G

В частности для матрицы инцидентности графа G , так как петля, инцидентная , , так как дуга не инцидентна , , так как -начало , а , так как — конец и так далее.

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

Здесь -количество дуг инцидентных , для которых является началом, а - количество дуг, инцидентных , для которых является концом.

Для графа G , а , поэтому орграф не является эйлеровым.

Пример. Дан граф G

1. Построить минимальное соединение графа и найти его вес.

2. Используя алгоритм, найти кратчайший путь от до .

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

І) Выбираем ребро с наименьшим весом, например:

1) .

ІІ) Из оставшихся ребер выбираем ребро с наименьшим весом так, чтобы с уже отобранным оно не образовала цикл.

Выбираем ребра 2) ;

3) ;

4) ;

5) .

Ребер с весом 1 больше нет. Выбираем ребра с весом 2 так, чтобы не получилось цикла:

6) ;

теперь взять уже нельзя – получается цикл.

7) .

Ребра с весом 2 также закончились. Выбираем ребра с весом 3 так, чтобы не получалось цикла.

8) ;

9) .

ІІІ) Как только количество отобранных ребер будет на одно меньше числа вершин, отбор прекращается. Полученное дерево является минимальным соединением.

Вес минимального соединения графа G

2. Найдем кратчайший путь от до , используя следующий алгоритм:

I) Присвоим вершине метку , а всем остальным метку ∞ (под ∞ понимаем наибольшее из предлагаемых на используемом компьютере целых чисел).

ІІ) Находим ребро , для которого . (Полагаем ∞-∞=0). Здесь – вес (длина) ребра . У вершины меняем метку на новую .

III) Правило II применяем до тех пор, пока для каждого ребра

не станет справедливым неравенство

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

На множестве вершин, смежных с , найдем такую , что

. (1)

Аналогично, на множестве вершин, смежных с , найдем такую , что , и так далее.

После некоторого числа шагов вершина совпадает с вершиной , путь — кратчайший, а его длина .

Переходим к решению задачи.

После I шага получаем метки при .

II. Просматриваем ребра и изменяем метки вершин:

1. ;

2. ;

3. оставляем метки;

4. ;

5. оставляем метки;

6. ;

7. ;

8. оставляем метки;

9. , оставляем метки;

10. , оставляем метки;

11. ;

12. оставляем метки;

13. ;

14. ;

15. ;

16. оставляем метки;

17. ;

18. оставляем метки.

III. Еще раз просматриваем все ребра и убеждаемся, что метки больше не меняются.

Итак, вершинам присвоены метки

IV. Из вершин и , смежных с , выбираем ту, для которой выполняется равенство (1):

для :

9=8+1 верно;

для :

9=6+4 неверно.

Значит, выбираем вершину .

Из вершин, смежных с выбираем ту, для которой выполняется равенство (1). Это будет вершина .

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

а длина его (вес) равна метке вершины , то есть 9.

Применение указанного алгоритма требует неоднократного просмотра всех ребер графа. Поэтому бывает удобнее использовать алгоритм Дейкстры [3], также основанный на присвоении меток вершинам и пересчете меток; получаемые при этом постоянные метки и есть длины кратчайших путей.

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

II. Для всех вершин меняем метки по правилу:

III. Среди вершин с временными метками находим , метка которой минимальна и делаем ее постоянной; .

IV. Возвращаемся к II до тех пор, пока вершина (конечная) не получит постоянной метки. Постоянные метки вершин и дают длины кратчайших путей от до этих вершин.

V. Сам путь строим, как и в предыдущем алгоритме, по вершинам с постоянными метками.

Решим задачу по алгоритму Дейкстры (каждый шаг — присвоение одной постоянной метки).

1 шаг. . —постоянная метка.

— временные метки.

2 шаг.

Метка — наименьшая из временных меток, делаем ее постоянной. —постоянная метка.

3 шаг.

Наименьшие из временных меток имеют вершины и . Выбираем, например, . —постоянная метка.

4 шаг.

Метки не изменились, наименьшей из временных осталась метка 3, принадлежащая вершине .

—постоянная метка.

5 шаг.

—постоянная метка.

6 шаг.

—постоянная метка.

7 шаг.

—постоянная метка.

8 шаг.

—постоянная метка.

9 шаг.

—постоянная метка.

10 шаг. Последняя вершина получает последнюю постоянную метку

—постоянная метка.

Путь строится так же как и раньше, т.е.

или

Рассмотренные вопросы можно изучить по указанной литературе, точнее: [1, гл. 2, § 1, 2], [3, гл. 7, § 7.1—7.5, § 7.7], [4, гл. 4, § 1 — 9], [5, гл. 6, § 6.1—6.2], [6, гл. 4, § 4.1—4.4], [7, разд. 3], [8, гл. 4, § 4.1—4.2], [9, гл. 7 —10], [11, гл. 4, § 4.1—4.8].

Библиографический список

1.Белов В.В., Воробьёв Е.М., Шаталов В.Е. — Теория графов. М.: Высшая школа, 1976, 392 с.

2. Горбатов В.А. Фундаментальные основы дискретной математики. — М.: Наука. Физматлит, 1999. 544 с.

3. Ерусалимский Я.М. Дискретная математика. — М.: Вузовская книга, 2002. 268 с.

4. Зарецкая М.А., Файнштейн А.С. Введение в дискретную математику. — Магнитогорск: МГТУ, 1999. 167 с.

5. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. — М.: Лаборатория базовых знаний, 2003. 288 с.

6. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988. 480 с.

7. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях. — М.: Логос, 2000. 240 с.

8. Нефедов В.Н., Осипова В.А. Курс дискретной математики. — М.: МАИ, 1992. 264 с.

9. Новиков Ф.А. Дискретная математика для программистов. — СПб.: Питер, 2000. 304 с.

10. Романовский И.В. Дискретный анализ. — СПб.: Невский Диалект, БХВ — Петербург, 2003. 320 с.

11. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. — М.: ИНФРА — М, Новосибирск: НГТУ, 2002. 280 с.

12. Яблонский С.В. Введение в дискретную математику. — М.: Наука, 1979. 272 с.