- Главная
- Разное
- Бизнес и предпринимательство
- Образование
- Развлечения
- Государство
- Спорт
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Религиоведение
- Черчение
- Физкультура
- ИЗО
- Психология
- Социология
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Что такое findslide.org?
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Обратная связь
Email: Нажмите что бы посмотреть
Презентация на тему по Дискретной математике на тему Цикломатическое число. Деревья
Содержание
- 2. План:Циклические и ацеклические ребраПонятие дерева и его элементовПредставление деревьевЛес, остов, бинарное дерево
- 3. Циклические и ацеклические ребраРебро произвольного графа называется
- 4. Цикломатическое число - Если неориентированный граф связный,
- 5. Деревом называется конечный связный граф, с выделенной
- 6. Цикломатическое число любого дерева равно 0.
- 7. Принцип построения: 1. Рисуем «главную» вершину,
- 8. Представление деревьевРюрик(879)Игорь( 945)Святослав (972)Ярополк (980)Владимир Св (1014)Олег (977)Изяслав Полоцкий(1001)Святополк(1018)Борис (1015)Ярослав (1054)Глеб (1015)ПРЕДОКПОТОМКИКОРЕНЬРюрик(879)Игорь( 945)
- 9. ДеревоГеография: население и народное хозяйство России
- 10. ДеревоПризнак «дерева». Потомки связаны только с предком, но не связаны между собой
- 11. ЗАДАНИЯ для самостоятельной работыОтразите в виде
- 12. Творческое домашнее заданиеА) Представьте в виде графа
- 13. Упорядоченное объединение непересекающихся деревьев D1, D2,
- 14. Лес, остов, бинарное деревоРассмотрим граф G. 1.
- 15. Скачать презентацию
- 16. Похожие презентации
План:Циклические и ацеклические ребраПонятие дерева и его элементовПредставление деревьевЛес, остов, бинарное дерево
Слайд 3
Циклические и ацеклические ребра
Ребро произвольного графа называется циклическим,
если оно принадлежит хотя бы одному элементарному циклу в
графе.В противном случае – ацеклическим.
А
D
B
C
E
F
K
H
I
FE, FH, HK, KE - циклические
Слайд 4
Цикломатическое число -
Если неориентированный граф связный, то
c(G)=1.
Если граф не связный, то разбить его на связные
компоненты и посчитать их.Слайд 5 Деревом называется конечный связный граф, с выделенной вершиной
(корневой) и не имеющий циклов.
Понятие дерева и его элементов
Дерево
– это граф, предназначенный для отображения таких связей между объектами как вложенность, подчинённость, наследование.Вершины в дереве называют узлами.
Расстояние до корневой вершины называют ярусом.
Теорема: Дерево с n – вершинами содержит (n-1) - ребро
Слайд 6 Цикломатическое число любого дерева равно 0. Цикломатическое число леса
равно сумме цикломатических чисел деревьев, то есть равно 0.
Для
всех остальных графов цикломатическое число всегда положительное.Слайд 7 Принцип построения: 1. Рисуем «главную» вершину, которая не зависит
ни от одной другой вершины (корень дерева или вершина
«0 яруса») 2. Добавляем вершины второго яруса (их может быть сколько угодно, все связаны с вершиной 0-го яруса, но не связаны между собой. 3. И.т.д.Представление деревьев
Каждая вершина дерева принадлежит ровно одному ярусу.
Номер яруса совпадает с расстоянием между его вершинами и корнем дерева.
Каждая вершина i–го яруса связана ребром ровно с одной вершиной (i-1)-го яруса и не связана ребром ни с какой вершиной i-го яруса.
В дереве любые две вершины соединены единственной цепью (единственный маршрут)
Слайд 8
Представление деревьев
Рюрик
(879)
Игорь
( 945)
Святослав
(972)
Ярополк (980)
Владимир Св (1014)
Олег (977)
Изяслав
Полоцкий(1001)
Святополк
(1018)
Борис (1015)
Ярослав (1054)
Глеб (1015)
ПРЕДОК
ПОТОМКИ
КОРЕНЬ
Рюрик
(879)
Игорь
( 945)
Слайд 9
Дерево
География: население и народное хозяйство России
Введение
Часть1. Общий обзор России
Россия на карте мираЗаселение территории
Сфера влияния России
Экономическое влияние России
Человек и природа
Природные условия и человек
Часть 2. Районы России
Подходы к районированию
Заключение
Иерархическая структура разделов книги
Слайд 11
ЗАДАНИЯ
для самостоятельной работы
Отразите в виде графа структуру
следующего объекта, рассматривая его как систему:
Плоские фигуры, круг, эллипс,
трапеция, параллелограмм, прямоугольник, ромб, квадратПлоская фигура
Круг
Эллипс
Трапеция
Параллелограмм
Прямоугольник
Ромб
Квадрат
Слайд 12
Творческое домашнее задание
А) Представьте в виде графа свою
родословную по отцовской линии
Б) Представьте в виде графа свою
родословную по материнской линииУДАЧИ!!!
Слайд 13 Упорядоченное объединение непересекающихся деревьев D1, D2, … ,
Dn представляет собой несвязный граф,
называемый ЛЕСом.
Лес, остов, бинарное
дерево
Слайд 14
Лес, остов, бинарное дерево
Рассмотрим граф G.
1. Будем
последовательно удалять циклические ребра до тех пор, пока это
будет возможно.2. В результате получим связный подграф с тем же множеством вершин, но без циклов, то есть получим граф, который называется ОСТОВ данного графа.
ОСТОВ – это любой подграф связного графа, содержащий все вершины графа и являющийся деревом (покрывающим деревом). Ребра остова называются хордами
Остов оформляется в виде таблицы:
