PPt4Web Хостинг презентаций

Главная / Геометрия / Графы. Степень вершины. Подсчет числа ребер графа
X Код для использования на сайте:

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

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

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


Скачать эту презентацию

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


Скачать эту презентацию

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

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

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

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

№ слайда 3 Разминка… Вставьте недостающие слова в предложения( мультиграф, кратный, вершина
Описание слайда:

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

№ слайда 4 Разминка… Вставьте недостающие слова в предложения( смежный, петля) Если ребро с
Описание слайда:

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

№ слайда 5 Домашняя задачкаУсловие В стране Знак есть 9 городов с названиями 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 вассалов. Может ли оказаться так, что у каждого вас
Описание слайда:

Домашнее задание У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ? Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог? Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

Скачать эту презентацию

Презентации по предмету
Презентации из категории
Лучшее на fresher.ru