ПЕДАГОГИЧЕСКОЕ СООБЩЕСТВО
НАШЕМУ СООБЩЕСТВУ ИСПОЛНИЛОСЬ 9 ЛЕТ!
Материал на проверке
Предварительный просмотр презентации
Тема урока: Степень вершины графа. Виды графов. Представление задач с помощью графа. Вероятность и статистика 7 класс М С В А К
Цели урока: Повторить понятия «граф», «вершина графа», «ребро графа» Познакомиться с понятием «степень вершины» Научиться решать задачи с помощью графов
Графы – Повторение вершины графа ребра графа это рисунки, которые состоят из точек и линий, соединяющих эти точки.
Проверка выполнения домашнего задания Ответить письменно на вопросы п.18
Степень вершины графа - это количество ребер, выходящих из данной вершины A B C D Степень A – 1 Степень B – 3 Степень C – 2 Степень D – 2 Основные понятия Для петли будем считать, что это ребро выходит из вершины дважды.
Вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной. Основные понятия М С В А К
Количество рёбер графа – равно сумме степеней всех его вершин, делённой на 2. A B C D E F (1+3+2+3+2+1):2=6 Основные понятия Если две вершины графа соединены ребром, то такие вершины называются смежными. Смежные вершины: А и В, В и С, В и Е, С и D, D и Е, D и F
Рассмотрим утверждение о количестве ребер на примере: Решение Задача 1. В государстве 100 городов, из каждого выходит 2 дороги, кроме столицы, откуда выходит 6 дорог. Сколько всего дорог в государстве? Ответ: 102 дороги Найдем количество дорог, выходящих из всех городов: 99*2+6=204 Это число - количество концов всех дорог. Поскольку каждая дорога имеет 2 конца, то количество дорог будет вдвое меньше. Значит, всего дорог в государстве: 204 : 2 = 102.
Неориентированный граф На схеме представлены дружеские связи в компании. Отношения являются двухсторонним, поэтому вершины соединены линиями без стрелок. Маша Юра Коля Витя Аня Граф называется неориентированным, если его вершины соединены ребрами. Какие бывают графы?
Ориентированный граф Маша Юра Коля Витя Аня Ориентированный граф - граф, вершины которого соединены дугами. Какие бывают графы? С помощью таких графов могут быть представлены схемы односторонних отношений. На рисунке представлена схема переписки
Алгоритм решения задач при помощи графов - проанализировать условие задачи; - определить, что известно; - составить граф: - проанализировать граф, найти все возможные решения или доказать, что их нет.
Задача 2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9? Решение Построим граф, вершинами которого являются города, а ребрами — существующие авиалинии. 1 2 3 4 5 6 7 8 9 Ответ: из города 1 в город 9 добраться по воздуху нельзя
Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими? Решение В качестве вершин графа возьмем телефоны, а в качестве ребер — телефонные провода. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Степень каждой вершины графа равна 5, значит, сумма степеней всех вершин равна 5·15=75 Это нечетное число, поэтому его половина — число нецелое. То есть в графе нецелое число ребер, и в городе нецелое число проводов, чего быть не может. Ответ: нельзя.
Основные понятия Задача 4. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж? Решение Отметим на рисунке индексами сверху каждого пункта количество путей, с помощью которых в него можно попасть и посчитаем итоговое. Заметим, что количество путей в город Ж является суммой путей в города Д, Г и Е. Количество путей в город Г — сумма путей в город В, Б и Е. Таким образом получаем: Г = Б + В + Е Д = В + Г Ж = Д + Г + Е Заметим, что в пункты Б, В и Е можно попасть единственным способом — из города А. Ответ: 8 1+3=4 1+1+1=3 4+3+1=8 1 1 1
