![]()
|
|||||||||||||||||||||||||||||||
Часть II. ГрафыЧасть II. Графы
Теория графов — удобный аппарат для формализации и решения задач из самых разных областей. К ним, в частности, относятся: проектирование и исследование сетей связи, анализ электрических сетей, анализ печатных схем, задачи проектирования электрических и монтажных схем, блок-схемы программ, исследование автоматов, задачи календарного планирования, планирование и обеспечение материально-технического снабжения, поиск информации, теория информации, размещение предприятий коммунального обслуживания, теория игр, биология, генеалогия, головоломки, определение химического состава и многое другое. Говоря нестрого, граф — это множество точек (вершин) и соединяющих их отрезков линий (ребер). Основной пример — схемы коммуникаций: дороги, авиалинии, трубопроводы и т.п. Мы должны изучить основные понятия теории графов и некоторые задачи, связанные с ними. Терминология этого раздела дискретной математики не является общеупотребительной, она своя у разных авторов. Мы будем придерживаться определений из [6]. Если вы пользуетесь другими пособиями, сравнивайте, какие понятия совпадают с [6], а какие отличаются. Рассмотрим эти понятия на примерах. Пример. Дан граф G:
1. Определить степени всех вершин графа. 2. Записать матрицу смежности вершин 3. Записать матрицу инцидентности 4. Указать мосты и точки сочленения, если они есть. 5. Проверить, является ли граф эйлеровым. 6. Проверить, является ли граф гамильтоновым. 7. Проверить, является ли граф двудольным. Если да, указать подмножества V1 и V2. 8. Записать какой-нибудь маршрут от 9. Указать какой-нибудь простой цикл. 10. Построить дерево, покрывающее граф.
Решение. 1.Степенью
2.Матрица смежности вершин.
Если граф не содержит кратных рёбер и петель, то В нашем примере
3.Матрица инцидентности Так для графа G
4. В графе можно удалять рёбра и вершины. Если удаляется ребро, то все вершины сохраняются, если же удаляется вершина, то удаляются все инцидентные ей рёбра. Вершина, при удалении которой число компонент связности увеличивается, называется точкой сочленения. Ребро с таким свойством называется мостом. В графе G точками сочленения являются вершины
При удалении
Мостами являются рёбра
5. Необходимым и достаточным условием эйлеровости графа является его связность и четность степеней всех вершин. Так как в графе G есть вершины степени 3 и 1, то он не является эйлеровым.
6. Критерия гамильтоновости графа не существует. Однако при наличии висячих вершин (вершин степени 1), мостов или точек сочленения граф гамильтоновым не будет. В графе G есть и висячие вершины, и мосты, и точки сочленения. Следовательно, граф не является гамильтоновым. 7. Необходимым и достаточным условием двудольности графа является отсутствие в нём циклов нечётной длины. В графе G есть циклы длины 3:
Если бы нам был дан граф G1,
8. Маршрутом от v1 до v9 в графе G может служить последовательность рёбер: ( 9. Простым циклом может служить (
10. Граф G содержит n=9 вершин и m=11 рёбер. Чтобы получить дерево, покрывающее граф (а дерево содержит рёбер на единицу меньше чем вершин, т.е. 8), удалим 11—8=3 ребра, входящие в циклы так, чтобы граф оставался связным, например:
Получим дерево, покрывающее граф:
Можно получить и другие деревья, покрывающие граф G.
Пример. Дан орграф G. 1. Построить матрицу смежности вершин 2. Построить матрицу инцидентности
.
Решение. 1. В матрице смежности
2. В матрице инцидентности
В частности для матрицы инцидентности
3. Необходимым и достаточным условием эйлеровости орграфа является его связность и равенство степеней Здесь Для графа G
Пример. Дан граф G
1. Построить минимальное соединение графа и найти его вес. 2. Используя алгоритм, найти кратчайший путь от Решение. 1. Для построения минимального соединения, то есть дерева, покрывающего граф и имеющего наименьший вес, используем правило экономичности или алгоритм Крускала. І) Выбираем ребро с наименьшим весом, например: 1) ІІ) Из оставшихся ребер выбираем ребро с наименьшим весом так, чтобы с уже отобранным оно не образовала цикл.
3) 4) 5) Ребер с весом 1 больше нет. Выбираем ребра с весом 2 так, чтобы не получилось цикла: 6) теперь взять 7) Ребра с весом 2 также закончились. Выбираем ребра с весом 3 так, чтобы не получалось цикла. 8) 9) ІІІ) Как только количество отобранных ребер будет на одно меньше числа вершин, отбор прекращается. Полученное дерево является минимальным соединением. Вес минимального соединения графа G
2. Найдем кратчайший путь от I) Присвоим вершине ІІ) Находим ребро
III) Правило II применяем до тех пор, пока для каждого ребра ![]() IV) Для построения самого пути движемся в обратном направлении от конечной вершины к начальной по убыванию меток так, чтобы разница между метками смежных вершин равнялась длине ребра. На множестве вершин, смежных с
Аналогично, на множестве вершин, смежных с После некоторого числа шагов вершина Переходим к решению задачи. После I шага получаем метки II. Просматриваем ребра и изменяем метки вершин: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. III. Еще раз просматриваем все ребра и убеждаемся, что метки больше не меняются. Итак, вершинам присвоены метки IV. Из вершин для 9=8+1 верно; для 9=6+4 неверно. Значит, выбираем вершину Из вершин, смежных с Из вершин, смежных с а длина его (вес) равна метке вершины
Применение указанного алгоритма требует неоднократного просмотра всех ребер графа. Поэтому бывает удобнее использовать алгоритм Дейкстры [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 с.
|
|||||||||||||||||||||||||||||||
|