Презентация, доклад по Дискретной математике на тему Цикломатическое число. Деревья

Деревья. Цикломатическое число. Остов

Дискретная математика

План:

Циклические и ацеклические ребра
Понятие дерева и его элементов
Представление деревьев
Лес, остов, бинарное дерево

Циклические и ацеклические ребра

Ребро произвольного графа называется циклическим, если оно принадлежит хотя бы одному элементарному циклу в графе.
В противном случае – ацеклическим.

А

D

B

C

E

F

K

H

I

FE, FH, HK, KE - циклические

Цикломатическое число -

Если неориентированный граф связный, то c(G)=1.
Если граф не связный, то разбить его на связные компоненты и посчитать их.

Деревом называется конечный связный граф, с выделенной вершиной (корневой) и не имеющий циклов.

Понятие дерева и его элементов

Дерево – это граф, предназначенный для отображения таких связей между объектами как вложенность, подчинённость, наследование.

Вершины в дереве называют узлами.
Расстояние до корневой вершины называют ярусом.

Теорема: Дерево с n – вершинами содержит (n-1) - ребро

Цикломатическое число любого дерева равно 0. Цикломатическое число леса равно сумме цикломатических чисел деревьев, то есть равно 0.

Для всех остальных графов цикломатическое число всегда положительное.

Принцип построения: 1. Рисуем «главную» вершину, которая не зависит ни от одной другой вершины (корень дерева или вершина «0 яруса») 2. Добавляем вершины второго яруса (их может быть сколько угодно, все связаны с вершиной 0-го яруса, но не связаны между собой. 3. И.т.д.

Представление деревьев

Каждая вершина дерева принадлежит ровно одному ярусу.

Номер яруса совпадает с расстоянием между его вершинами и корнем дерева.

Каждая вершина i–го яруса связана ребром ровно с одной вершиной (i-1)-го яруса и не связана ребром ни с какой вершиной i-го яруса.

В дереве любые две вершины соединены единственной цепью (единственный маршрут)

Представление деревьев

Рюрик
(879)

Игорь
( 945)

Святослав
(972)

Ярополк (980)

Владимир Св (1014)

Олег (977)

Изяслав Полоцкий(1001)

Святополк
(1018)

Борис (1015)

Ярослав (1054)

Глеб (1015)

ПРЕДОК

ПОТОМКИ

КОРЕНЬ

Рюрик
(879)

Игорь
( 945)

Дерево

География: население и народное хозяйство России
Введение
Часть1. Общий обзор России
Россия на карте мира
Заселение территории
Сфера влияния России
Экономическое влияние России
Человек и природа
Природные условия и человек
Часть 2. Районы России
Подходы к районированию
Заключение

Иерархическая структура разделов книги

Дерево

Признак «дерева».
Потомки связаны только с предком, но не связаны между собой

ЗАДАНИЯ для самостоятельной работы

Отразите в виде графа структуру следующего объекта, рассматривая его как систему:
Плоские фигуры, круг, эллипс, трапеция, параллелограмм, прямоугольник, ромб, квадрат

Плоская фигура

Круг

Эллипс

Трапеция

Параллелограмм

Прямоугольник

Ромб

Квадрат

Творческое домашнее задание

А) Представьте в виде графа свою родословную по отцовской линии

Б) Представьте в виде графа свою родословную по материнской линии

УДАЧИ!!!

Упорядоченное объединение непересекающихся деревьев D1, D2, … , Dn представляет собой несвязный граф, называемый ЛЕСом.

Лес, остов, бинарное дерево

Лес, остов, бинарное дерево

Рассмотрим граф G.
1. Будем последовательно удалять циклические ребра до тех пор, пока это будет возможно.
2. В результате получим связный подграф с тем же множеством вершин, но без циклов, то есть получим граф, который называется ОСТОВ данного графа.

ОСТОВ – это любой подграф связного графа, содержащий все вершины графа и являющийся деревом (покрывающим деревом). Ребра остова называются хордами

Остов оформляется в виде таблицы:

Спасибо за внимание