Ярусно-параллельная форма графов

Граф, не имеющий контуров, может быть представлен в ярусно-параллельной форме. Ярусно-параллельная форма – это такой вид графа, у которого в верхний нулевой ярус помещены вершины, имеющие только исходящие дуги; в нижний ярус помещены вершины, имеющие только входящие дуги. На k-том ярусе помещены вершины, которые имеют входящие дуги из предыдущих ярусов, среди которых хотя бы одна дуга из (k-1)-того яруса.

Количество вершин в ярусе определяет ширину яруса. Наибольшая ширина яруса определяет ширину графа в ярусно-параллельной форме. Количество ярусов определяет высоту графа в ярусно-параллельной форме.

Алгоритм приведения графа к ярусно-параллельной форме.

1. Составляется матрица смежности графа.

2. Матрица смежности просматривается в поисках нулевых столбцов. Вершины, которым соответствуют нулевые столбцы, помещаются в нулевой ярус.

3. Из матрицы смежности столбцы и строки, соответствующие вершинам нулевого яруса.

4. Повторяется п.2 данного алгоритма до тех пор, пока не будут охвачены все вершины.

5. По исходной матрице смежности восстанавливаются дуги между вершинами.

Отделенными называются вершины, для которых не существует соединяющего эти вершины пути.

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

Подграфом графа называется граф вида:

(3.19)

Компонентой связности называется подграф, порождаемый множество неотделенных вершин.

ПРИМЕР

На рис. 3.10 представлен граф, имеющий две компоненты связности {1,2,3,4} и {5.6}

Рис. 3.10 Граф

Связанным графом называется граф, имеющий одну компоненту связности.

Дерево– связный неориентированный граф, в котором отсутствует цикл.

На рис. 3.11 представлены графы- деревья.

Рис. 3.11 Граф

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

Цикломатическим числом (g)графа называется минимальное количество ребер, которое необходимо изъять из графа, чтобы он стал деревом. Цикломатическое число определяется по формуле:

, (3.20)

где N – количество ребер,

k – количество вершин.

Алгоритм получения дерева из графа

1. Выбирается любая вершина. Счетчик i принимаем равным 1 (i=1).

2. Если i = k, то дерево построено.

3. Если i ¹ k, то выбирается любая незадействованная вершина и ребро, соединяющее данную вершину с любой из выбранных.

4. Счетчик увеличивается на единицу.(i= i+1).

5. Переход на пункт 2.

Задание №1.

Найти Эйлерову цепь в неориентированном графе.

а)	б)	в)

Задание №2.Для графа G=(V,E), с заданными мощностями |V|=n, |E|=m составьте матрицы смежности и инцидентности, определите локальные степени вершин, а также постройте его подграф. Является ли граф, соответствующий Вашему варианту эйлеровым, и почему?

Технология работы

Задание №1

Проверь возможность наличия Эйлеровой цепи, используя теорему Эйлера.

Указать Эйлеровую цепь.(при помощи вершин)

Задание№2

Построить граф (форма, вид графа выбирается на усмотрение студента).

Составить матрица инцидентности и смежности. Используя данные матрицы определить степени и полустепени вершин. По теоремы Эйлера определить является ли он Эйлеровым.

Задание №3

Для этого задания использовать алгоритм фронта волны. Обратить внимание на порядок применения пунктов алфовита.

Задание №4н

Определить цикломатическое число для графа. Поэтапно применить алгоритм построения дерева.

1. Контрольные вопросы:
Что называется графом? ориентированным графом?

2. Что называется вершинами графа? ребрами?

3. Какие ребра и какие вершины графа называются смежными?

4. Какой граф называется мультиграфом?

5. Какой граф называется полным? дополнением?

6. Что называется петлей? цепью? циклом? путем в графе?

7. Какой граф называется деревом?

8. Что называется суммой графов? пересечением? композицией?

9. Что называется транзитивным замыканием графа? декартовым произведением графов?

11. Что называется степенью графа? Что называется полустепенями исхода и захода графа?
Что такое цикломатическое число графа?

12. Что называется хроматическим числом графа?

13. C помощью каких матриц можно задать граф?

14. Какой граф называется эйлеровым?

Список рекомендуемой литературы

1. Дискретная математика: Учебное пособие / С.А. Канцедал. - М.: ИД ФОРУМ, НИЦ ИНФРА-М, 2014. - 224 c.

2. Дискретная математика: Учебник для студ. учреждений сред. проф. образования / М. С. Спирина, П. А. Спирин. — М.: Издательский центр «Академия», 2013. — 368 с.