Презентация по слайдам:
Слайд #1
Обход графа (эйлеров путь). Представление об ориентированных графах.
Подготовила:
учитель математики
МБОУ Г.ГОРЛОВКИ «ШКОЛА № 42»
Рыбина М.В.
Слайд #2
Повторим!
Графом называется конечное множество точек, некоторые из которых соединены линиями. При этом точки называются вершинами графа, а линии — рёбрами.
Если из вершины не выходит ни одно ребро, то её называют изолированной.
Степень вершины в графе – это количество исходящих из неё ребер.
Теорема у сумме степеней вершин. В любом графе сумма степеней всех вершин является четным числом.
В любом графе количество вершин нечетной степени четно.
Граф, у которого каждая вершина соединена ребром с любой другой вершиной, называется полным.
Чтобы найти количество рёбер в полном графе, у которого n - вершин, нужно воспользоваться формулой: 𝑛(𝑛−1) 2
Слайд #3
Повторим!
Последовательность ребер, соединяющих вершины А и В, называют путем из вершины А в вершину В.
Пути, где вершины не повторяются, называются простыми путями или цепями (АСВ, АDCB , АDFEB).
Длина пути — это количество рёбер в этом пути. (АСВ – длина 2, АDCB – длина 3, АDFEB – длина 4).
Цикл в графе – это замкнутый путь, у которого начало и конец в одной вершине, а ребра и промежуточные вершины не повторяются.
Граф называется связным, если две любые вершины в этом графе соединены путем.
Слайд #4
Рассмотрим ещё один вид пути в графе и связанный с ним вид графа.
Эйлеровым путём в графе называется путь, который обходит все рёбра связного графа по одному разу.
Граф, в котором существует эйлеров путь, называется эйлеровым графом.
Другими словами, граф, который можно нарисовать, не отрывая карандаша от бумаги и проводя каждое ребро один раз, называется эйлеровым.
Граф на рисунке можно нарисовать, проводя карандашом по пути: С – К – М – В – С – А – В. Это не единственный возможный путь.
Слайд #5
Теорема Эйлера
Важное условие существования эйлерова графа связано с наличием определённого количества нечётных вершин.
Леонард Эйлер в процессе решения задачи о Кёнигсберских мостах сформулировал и доказал теорему.
Теорема. Если в графе существует путь, проходящий через все рёбра ровно по одному разу, то в этом графе не больше двух вершин нечётной степени.
Вспомним следствие: Число нечётных вершин графа всегда чётно.
ВЫВОД: Эйлеров граф может иметь либо две нечётные вершины, либо не иметь их совсем.
Слайд #6
Леонард Эйлер, решая знаменитую задачу о семи Кёнигсбергских мостах, доказал свою теорему.
В старинном городе Кёнигсберге (ныне Калининград) семь мостов через реку Преголя , которую во времена Эйлера называли Прегель. Древняя городская легенда гласила, что тот, кто сумеет обойти весь город, ровно по разу побывав на каждом из семи мостов , обретёт счастье и богатство. Кто только ни пытался это сделать, но никому не удавалось.
Слайд #7
Теперь мы тоже можем решить задачу о мостах. Участки суши изобразим вершинами, мосты рёбрами графа. Посмотрите ещё раз на план города и убедитесь, что мосты на графе показаны верно.
В получившемся графе все четыре вершины имеют нечётную степень: вершины А, В и Г имеют степень 3, а вершина Б - степень 5. Значит, обойти такой граф эйлеровым путём невозможно.
Слайд #8
В прошлый раз мы говорили про пути в графе. Но иногда важную роль играет и направление этого пути.
Граф называется ориентированным, если указано направление каждого ребра.
Число рёбер, входящих в вершину, называют входящей степенью вершины, а число рёбер исходящих — исходящей степенью вершины.
Входящая степень вершины B равна 2, исходящая степень вершины A равна 2.
Для вершины C входящая степень вершины равна исходящей степени вершины и равна 1.
Слайд #9
Свойство. В ориентированном графе сумма исходящих степеней всех вершин равна сумме входящих степеней всех вершин и равна числу рёбер.
Пример:
Сумма исходящих степеней всех вершин, начиная с вершины A, равна:
2+1+1+1+ 0 = 5.
Сумма входящих степеней всех вершин, начиная с вершины A, равна:
0+1+1+1+ 2 = 5.
Количество рёбер тоже равно 5.
Слайд #10
Задание 1
ОТВЕТ: да
Слайд #11
Задание 2
нет
Слайд #12
Задание 3
Слайд #13
Задание 4
нет
Слайд #14
Задание 5
В компьютерной игре главный герой перемещается по государству, состоящему из нескольких островов. Острова соединены мостами так, что из каждого можно добраться до любого другого. Герой обошёл все острова в поисках карты, пройдя по каждому мосту ровно один раз. Но на острове Древнем он побывал целых 11 раз. Сколько мостов ведёт с острова Древнего, если герой не с него начал и не на нём закончил свой поход?
ОТВЕТ: 22
Слайд #15
Задание 6
57
57
Слайд #16
Задание 7
У Саши с Таней вышел спор. Саша утверждает, что из проволоки длиной 54 см нельзя сложить каркас куба при условии, что нельзя резать проволоку и делать рёбра разной толщины, а Таня говорит, что можно. Кто из ребят прав?
ОТВЕТ: Саша
Слайд #17
Задание 8
Слайд #18
Задание 9
Какими цифрами обозначены Эйлеровы графы?
ОТВЕТ: 1,2,4
Слайд #19
Домашнее задание:
Какими цифрами обозначены Эйлеровы графы?
Пять участков отделены друг от друга заборами (см. план). Можно ли побывать на каждом участке, но при этом перелезть через каждый забор ровно один раз? Почему?
3. В Изумрудном городе шесть площадей. Каждая площадь соединена улицами ровно с тремя другими площадями. Никакие две улицы в городе не пересекаются.
a) Начертите возможный план Изумрудного города.
б) Можно ли устроить экскурсию по всем улицам и площадям Изумрудного города, не проходя ни по одной улице дважды?
Слайд #20
Использованные источники:
https://www.yaklass.ru/p/veroyatnost-i-statistika/7-klass/teoriia-grafov-7271003/poniatie-eilerova-grafa-orientirovannye-grafy-7279169/re-728ccf38-e8f6-4252-ad48-751ccb8ce658
