Лабораторная работа № 7

ЦЕПИ И ЦИКЛЫ В ГРАФАХ

Цель работы — исследование цепей и циклов в ориентированных и неориентированных графах.

Основные понятия и определения

Чередующаяся последовательность вершин и ребер графа  называется маршрутом, соединяющим вершины v_i и v_{i +1}. Маршрут ( v_i, v_{i +1}) является цепью, все его вершины кроме, возможно, крайних, различны. Маршрут ( v_i, v_{i +1}) называется циклическим, если v_i = v_{i +1}. Циклическая цепь называется циклом, циклическая простая цепь — простым циклом. Число ребер в маршруте ( v_i, v_{i +1}) определяет его длину. Простой цикл единичной длины называется единичным циклом. Длина всякого цикла в простом графе (без петель кратных ребер) и кратных ребер) минимум равна трем. Минимальная из длин циклов графа называется его обхватом.

Любая цепь графа может рассматриваться как его подграф. В цепи Q графа G, заданной последовательностью вершин v₁, v₂,…,v_n, можно выделить две вершины v_i, v_j. Часть цепи Q, начинающаяся в v_i и заканчивающаяся в v_j ( v_i, v_{i +1},…,v_{j -1}, v_j ), сама является цепью графа G. Цепь ( v_i, v_j ) называется полуцепью цепи Q. На рис. 9 приведен граф G, в котором (1,2) и (1, 2, 3, 5) - простые цепи. Цепь (1, 3, 5, 4, 3, 2) не является простой цепью. Маршрут (1, 2, 3, 5, 4, 3, 2) — не цепь. Цепь (1, 2, 3, 1) — простой цикл. Обхват рассматриваемого графа равен трем.

Рис. 9. Граф с обхватом, равным трем

 В ориентированных графах маршрут ориентированный и является последовательностью вида (1). Аналогом цепи с в ориентированном графе служит путь (ориентированная цепь). Вершина v_j в ориентированном графе называется достижимой из вершины v_i, если существует путь ( v_i, v_j ).

 Произвольный ориентированный маршрут ( v_i, v_j ), не являющийся простой цепью, превращается в простую цепь после устранения ''лишних звеньев''. Поэтому верны утверждения:

1. При i, не равном j, всякий маршрут ( v_i, v_j) содержит простую цепь.

2. Всякий цикл содержит простой цикл.

3. Если C, D - два несовпадающих простых цикла, имеющих общее ребро u_i, то граф также содержит простой цикл.

Лабораторное задание

1. Выполните генерацию матрицы смежности M ( G ) неориентированного помеченного графа G порядка . Метки графа выберите из подмножества натуральных чисел {1,2,…, n }. Отождествляя каждую вершину графа с одним из элементов на рис.6, постройте функциональную схему электронного узла. При этом входы элементов с номерами 1, 2 являются входами, а выходы элементов с номерами n , n - 1 — выходами всего учла.

2. Вычислите остов минимального веса и базисные циклы L_i, i = 1, 2,..., m в графе G. При отсутствии базисных циклов в графе по согласованию с преподавателем осуществите добавление ребра (ребер)

3. Определите через базисные циклы все остальные циклы L_j, j = m +1, m +2,… в графе G. В соответствии с найденными циклами графа укажите на функциональной схеме узла все замкнутые цепи (контуры).

4. Осуществите генерацию матрицы смежности M ( H ) помеченного орграфа H порядка . Определите все вершины, достижимые из вершины v₁. Выберите достижимую вершину v_j, j = 2,3,…, n, определяющую самый длинный маршрут. Определите, является ли самый длинный маршрут простой ориентированной цепью. Если маршрут не является простой ориентированной цепью, то удалите ''лишние звенья''.

Содержание отчета

1. Матричные и графические представления графов G, H, функциональная схема электронного узла.

2. Схема алгоритмов вычисления остова и базисных циклов графа G и достижимых из вершины v₁ вершин графа H .

3. Протоколы вычислений характеристик графа G, Н средствами системы MathCAD.

Контрольные вопросы

1. Как найти остов графа?

2. Найдите остовные деревья в графе Петерсена.

3. Верно ли, что, диаметр связного графа G равен k ( k >2), то в G существует остовное дерево, диаметр которого также равен k?

ЛИТЕРАТУРА

1. Акимов О.Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001 – 352 с.

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

3. Яхо, Альфред, В., Хопкрофт Джон Э., Ульман, Джеффи Д.. // Структуры данных и алгоритмы.: Пер. с англ.: Уч. пособие – М: Издательство дом «Вильямс», 2000-384 с.: ил. – Парал. тит. англ.

4. Романовский И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. – Издание 2-е, исправленное. – СПб.: Невский диалект, 2000 г. – 240 с., ил.

5. Горбатов В.А. Основы дискретной математики: Учеб. Пособие для вузов. - М.: Высш. шк., 1986. - 312 с.

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

7. Лекции по теории графов / Под ред. В.А. Емеличева., О.Н. Мельникова, В.И. Сарванова, Р.И. Тышкевич. - М.: Наука, Гл. ред. физ.-мат. лит., 1990. - 384 с.

8. Зыков А.А. Основы теории графов. - М.: Наука, 1987. - 381 с.

9. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. Учеб. Пособие для вузов. - М.: Высш. шк., 1976. - 392 с.

10. Кристофиедес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978. - 432 с.

11. Татт У. Теория графов. - М.: Мир, 1988. - 308 с.

12. Оре О. Теория графов. - М.: Наука, 1980. - 336 с.

13. Евстигнеев В.А. Применение теории графов в программировании. - М.: Наука, 1985. - 352 с.

14. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. - М.: Мир, 1982. - 416 с.

ПРИЛОЖЕНИЕ