слово «граф» означает дворянский титул, например, граф Лев Николаевич Толстой.
А вот в математике …Граф – это конечная совокупность вершин,
некоторые из которых соединены ребрами.
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Графы. Степень вершины. Подсчет числа ребер графа
Содержание
- 1. Графы. Степень вершины. Подсчет числа ребер графа
- 2. Разминка…Вставьте недостающие слова в предложения(граф, титул, ребро,
- 3. Если пара вершин соединена несколькими ребрами, то
- 4. Если ребро соединяет вершину саму с собой,
- 5. Слайд 5
- 6. Постройте граф, обозначив вершины графа цифрами (названия
- 7. Поставим в соответствие каждому городу точку и
- 8. Количество ребер, выходящих из одной вершины, называют
- 9. Вершина, имеющая четную степень, называется четной вершиной,
- 10. Количество ребер графа равно половине суммы степеней
- 11. Рассмотрим утверждение о количестве ребер на примере:Задача:
- 12. Теорема. Количество вершин нечетной степени любого графа
- 13. Домашнее задание У короля 19 вассалов.
- 14. Скачать презентанцию
Разминка…Вставьте недостающие слова в предложения(граф, титул, ребро, вершина)Всем известно, что слово «граф» означает дворянский титул, например, граф Лев Николаевич Толстой. А вот в математике …Граф – это конечная совокупность вершин, некоторые
Слайды и текст этой презентации
Слайд 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
городов, из каждого выходит 2 дороги, кроме столицы, откуда выходит
6 дорог. Сколько всего дорог в государстве?Решение: сложим количества дорог, выходящих из всех городов: 99*2+6=204. Это число - количество концов всех дорог. Поскольку каждая дорога имеет 2 конца, то количество дорог будет вдвое меньше, а именно 102.
Подсчет числа ребер графа
Слайд 12Теорема. Количество вершин нечетной степени любого графа всегда четно.
Степень вершины
графа
Доказательство: Количество ребер графа равно половине суммы степеней его вершин.
Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной.
А это возможно только в том случае, если граф содержит четное число нечетных вершин.
Слайд 13Домашнее задание
У короля 19 вассалов. Может ли оказаться
так, что у каждого вассала 1, 5 или 9 соседей
?Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?
Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.
Теги
