Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Обратная связь

Презентация на тему Графы. Степень вершины. Подсчет числа ребер графа

Содержание

2. Разминка…Вставьте недостающие слова в предложения(граф, титул, ребро,
3. Если пара вершин соединена несколькими ребрами, то
4. Если ребро соединяет вершину саму с собой,
6. Постройте граф, обозначив вершины графа цифрами (названия
7. Поставим в соответствие каждому городу точку и
8. Количество ребер, выходящих из одной вершины, называют
9. Вершина, имеющая четную степень, называется четной вершиной,
10. Количество ребер графа равно половине суммы степеней
11. Рассмотрим утверждение о количестве ребер на примере:Задача:
12. Теорема. Количество вершин нечетной степени любого графа
13. Скачать презентацию
14. Похожие презентации

Разминка…Вставьте недостающие слова в предложения(граф, титул, ребро, вершина)Всем известно, что слово «граф» означает дворянский титул, например, граф Лев Николаевич Толстой. А вот в математике …Граф – это конечная совокупность вершин, некоторые из которых соединены ребрами.

Главная
Математика
Графы. Степень вершины. Подсчет числа ребер графа

ГрафыСтепень вершиныПодсчет числа ребер графа

Разминка…Вставьте недостающие слова в предложения(граф, титул, ребро, вершина)Всем известно, что слово «граф»

Если пара вершин соединена несколькими ребрами, то говорят, что задан мультиграф, а

Если ребро соединяет вершину саму с собой, то такое ребро называют ________.Если

Постройте граф, обозначив вершины графа цифрами (названия городов). Соедините ребрами те вершины,

Поставим в соответствие каждому городу точку и соединим те точки линиями, сумма

Количество ребер, выходящих из одной вершины, называют степенью этой вершины. Для петли

Вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень,

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

Рассмотрим утверждение о количестве ребер на примере:Задача: в государстве 100 городов, из

Теорема. Количество вершин нечетной степени любого графа всегда четно. Степень вершины графаДоказательство:

Домашнее задание У короля 19 вассалов. Может ли оказаться так, что

Слайды презентации

Слайд 2 Разминка…
Вставьте недостающие слова в предложения
(граф, титул, ребро, вершина)

Всем

Разминка…Вставьте недостающие слова в предложения(граф, титул, ребро, вершина)Всем известно, что слово

известно, что слово «граф» означает дворянский титул, например, граф

Лев Николаевич Толстой. А вот в математике …

Граф – это конечная совокупность вершин,
некоторые из которых соединены ребрами.

Слайд 3 Если пара вершин соединена несколькими ребрами,
то говорят,

Если пара вершин соединена несколькими ребрами, то говорят, что задан мультиграф,

что задан мультиграф, а ребра,
соединяющие одну и ту

же пару вершин,
называют кратными.

Вставьте недостающие слова в предложения
( мультиграф, кратный, вершина)

Разминка…

Слайд 4 Если ребро соединяет вершину саму с собой,
то

Если ребро соединяет вершину саму с собой, то такое ребро называют

такое ребро называют ________.

Если две вершины графа соединены ребром,

то такие вершины называются смежными.

Разминка…

Вставьте недостающие слова в предложения
( смежный, петля)

Слайд 5 В стране Знак есть 9 городов с названиями

1, 2, 3, 4, 5, 6, 7, 8, 9.

Путешественник обнаружил, что два города соединены дорогой в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3.

Домашняя задачка
Условие

Слайд 6 Постройте граф, обозначив вершины графа цифрами (названия городов).

Постройте граф, обозначив вершины графа цифрами (названия городов). Соедините ребрами те

Соедините ребрами те вершины, которые удовлетворяют условию задачи.

Посчитайте

количество ребер.

Можно ли долететь по воздуху из города 1 в город 9 ?

Домашняя задачка
Задания

Слайд 7 Поставим в соответствие каждому городу точку и соединим

Поставим в соответствие каждому городу точку и соединим те точки линиями,

те точки линиями, сумма цифр которых делится на 3.

Получим граф.

Обратим внимание, что 3, 6, 9
связаны между собой,
но не связаны с остальными.

Число ребер: 12.

Значит
долететь из города 1 в город 9 нельзя.

Домашняя задачка
Решение

Слайд 8
Количество ребер, выходящих из одной вершины,
называют степенью

Количество ребер, выходящих из одной вершины, называют степенью этой вершины. Для

этой вершины.

Для петли будем считать, что это ребро

выходит из вершины дважды.

Степень вершины графа

Слайд 9 Вершина, имеющая четную степень, называется четной вершиной, соответственно,

Вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную

вершина, имеющая нечетную степень, называется нечетной вершиной.
Граф называется связным,

если из любой
его вершины в любую другую можно
пройти по ребрам графа.

Степень вершины графа

Слайд 10 Количество ребер графа равно половине суммы степеней его

вершин.

Пусть граф имеет n вершин, тогда число ребер

равно:

Подсчет числа ребер графа

Слайд 11 Рассмотрим утверждение о количестве ребер на примере:

Задача: в

Рассмотрим утверждение о количестве ребер на примере:Задача: в государстве 100 городов,

государстве 100 городов, из каждого выходит 2 дороги, кроме

столицы, откуда выходит 6 дорог. Сколько всего дорог в государстве?
Решение: сложим количества дорог, выходящих из всех городов: 99*2+6=204. Это число - количество концов всех дорог. Поскольку каждая дорога имеет 2 конца, то количество дорог будет вдвое меньше, а именно 102.

Подсчет числа ребер графа

Слайд 12 Теорема. Количество вершин нечетной степени любого графа всегда

Теорема. Количество вершин нечетной степени любого графа всегда четно. Степень вершины

четно.
Степень вершины графа
Доказательство: Количество ребер графа равно половине суммы

степеней его вершин.

Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной.

А это возможно только в том случае, если граф содержит четное число нечетных вершин.