X

Скопируйте код и вставьте его на свой сайт.

Ширина px

Вы можете уменьшить размер презентации, указав свой размер!

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

Графы Степень вершины Подсчет числа ребер графа
Разминка… Вставьте недостающие слова в предложения (граф, титул, ребро, верши...
Если пара вершин соединена несколькими ребрами, то говорят, что задан мультиг...
Если ребро соединяет вершину саму с собой, то такое ребро называют ________. ...
В стране Знак есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешест...
Постройте граф, обозначив вершины графа цифрами (названия городов). Соедините...
Поставим в соответствие каждому городу точку и соединим те точки линиями, сум...
Количество ребер, выходящих из одной вершины, называют степенью этой вершины....
Вершина, имеющая четную степень, называется четной вершиной, соответственно, ...
Количество ребер графа равно половине суммы степеней его вершин. Пусть граф и...
Рассмотрим утверждение о количестве ребер на примере: Задача: в государстве 1...
Теорема. Количество вершин нечетной степени любого графа всегда четно. Степен...
Домашнее задание У короля 19 вассалов. Может ли оказаться так, что у каждого ...
Класс
Автор

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

Описание презентации по отдельным слайдам:

1 слайд

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

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 дорог? Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.