Презентация по слайдам:
Слайд #1
Цепь и цикл. Путь в графе. Представление о связности графа.
Подготовила:
учитель математики
МБОУ Г.ГОРЛОВКИ «ШКОЛА № 42»
Рыбина М.В.
Слайд #2
Повторим!
Графом называется конечное множество точек, некоторые из которых соединены линиями. При этом точки называются вершинами графа, а линии — рёбрами.
Если из вершины не выходит ни одно ребро, то её называют изолированной.
Слайд #3
Повторим!
Степень вершины в графе – это количество исходящих из неё ребер.
Теорема у сумме степеней вершин. В любом графе сумма степеней всех вершин является четным числом.
В любом графе количество вершин нечетной степени четно.
Граф, у которого каждая вершина соединена ребром с любой другой вершиной, называется полным.
Чтобы найти количество рёбер в полном графе, у которого n - вершин, нужно воспользоваться формулой: 𝑛(𝑛−1) 2
Слайд #4
Определения
Предположим, что в некотором графе можно по ребрам пройти из вершины А в вершину В. Последовательность ребер, соединяющих вершины А и В, называют путем из вершины А в вершину В.
На рисунке есть несколько путей из вершины А в вершину В.
Например путь, состоящий из ребер АС и СВ. Его можно назвать короче АСВ. Еще есть пути: АDCB и АDFEB.
А можно придумать более сложный путь, который заставит покружить ADCADCB.
Пути, где вершины не повторяются, называются простыми путями или цепями (АСВ, АDCB , АDFEB).
Длина пути — это количество рёбер в этом пути. (АСВ – длина 2, АDCB – длина 3, АDFEB – длина 4).
Если граф состоит из одной единственной цепи, то такой граф также называют цепью.
Граф без ребер, состоящий из единственной вершины, также считают цепь.
Слайд #5
Иногда возникает необходимость выйти из вершины и вернуться в неё же. Такие возвращающиеся в начальную точку пути называются циклами.
Цикл в графе – это замкнутый путь, у которого начало и конец в одной вершине, а ребра и промежуточные вершины не повторяются.
Простейший цикл – петля, которая состоит из одной вершины и одного ребра.
Слайд #6
Начальной вершиной цикла можно считать любую вершину. Граф на рисунке имеет цикл, который можно назвать ADCA, DCAD, CADC.
В этом графе есть еще цикл DCBEFD.
Найдите еще один цикл в этом графе!
Если граф состоит из одного единственного цикла, то такой граф также называют циклом.
Слайд #7
Граф называется связным, если две любые вершины в этом графе соединены путем.
Правый граф несвязный. Но его можно представить как два отдельных связных графа.
Слайд #8
Задание 1
Слайд #9
Задание 2
Слайд #10
Задание 3
Есть ли в графе путь :
А) из А в С; Б) из В в F?
Является ли этот граф связным?
Слайд #11
Задание 4
Выпишите номера графов, которые являются:
а) цепями; б) циклами; в) несвязными графами
Слайд #12
Задание 5
Изобразите какой-нибудь граф, у которого:
a) три цикла длин 3, 4 и 5;
б) два цикла длины 4 и один цикл длины 6.
Слайд #13
Задание 6
В солнечной системе введено космическое сообщение. Корабли осуществляют рейсы в обе стороны по следующим маршрутам: Земля – Меркурий, Марс – Венера, Уран – Нептун, Марс – Меркурий, Юпитер – Плутон, Меркурий – Венера, Нептун – Сатурн, Сатурн – Юпитер, Плутон – Уран. Можно ли добраться с Земли до Плутона?
Земля
Венера
Уран
Нептун
Юпитер
Плутон
Меркурий
Сатурн
Марс
ОТВЕТ: НЕТ
Слайд #14
Задание 7
Архипелаг Числовой состоит из 9 островов, у которых вместо названий номера от 1 до 9. Между двумя островами есть паромная переправа тогда и только тогда, когда сумма номеров этих островов делится на 3. Можно ли перебраться на паромах с острова 3 на остров 4?
1
5
7
2
4
8
3
9
6
ОТВЕТ: НЕТ
Слайд #15
Существует ли полный граф с семью ребрами?
Решение
𝑛(𝑛−1) 2 = 7,
𝑛(𝑛−1) = 14
Но 𝑛 и 𝑛−1 последовательные натуральные числа. Число 14 нельзя представить в виде суммы двух последовательных натуральных чисел. То есть уравнение 𝑛(𝑛−1) = 14 решений не имеет.
Значит, полного графа с семью ребрами не существует.
Задание 8
Слайд #16
Задание 9
Сколько существует различных путей, чтобы попасть из А в М? По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
А
1
А
1
A,K
2
A,B,G
4
B
1
E
4
F,G
6
K
1
C, F, H, L
12
Слайд #17
Домашнее задание:
1. Запишите какие – нибудь три цепи, ведущие из вершины А в вершину В. (смотреть рисунок).
2. Найдите на рисунке три разных цикла.
3. Изобразите два графа с шестью вершинами степени 2: один связный, а другой нет.
Слайд #18
Использованные источники:
https://www.yaklass.ru/p/veroyatnost-i-statistika/7-klass/teoriia-grafov-7271003/tcepi-i-tcikl-puti-v-grafe-7276192/re-3ae2a5c5-5835-4b64-a9e1-e24e8be59997
