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

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