Презентация по вероятности и статистике "Пути в графе. Связные графы"

Слайд #1

Пути в графе. Связные графы
Цепи и циклы

Слайд #2

Граф — это изображение объектов и связей между ними с помощью точек
и линий.
Точки в графе называются вершинами графа. Некоторые (не обязательно все) вершины соединены линиями.
Эти линии называются рёбрами графа.

Слайд #3

Предположим, что в некотором графе можно по рёбрам «пройти» из вершины А в вершину В, то есть существует последовательность рёбер, соединяющих вершины А и В.
Такую последовательность называют путём из вершины А в вершину В.

Слайд #4

Путь между двумя вершинами последовательность рёбер, которая
их соединяет.
В графе, показанном на рисунке 28,
есть несколько путей из вершины А в вершину В.

Слайд #5

Например, есть путь, состоящий из рёбер АС и СВ.
Этот путь можно обозначить тремя буквами — АСВ.
Есть более длинный путь АDFЕВ.
Можно придумать более сложный путь, который заставит нас немного «покружить», — АDСАDСВ.

Слайд #6

В путях АСВ и АDFЕВ вершины не повторяются.
Такие пути называют простыми путями или цепями.
Цепь (простой путь) — это путь в графе из одной вершины в другую, в котором вершины и рёбра не повторяются.
Если граф состоит из одной-единственной цепи, то такой граф также называют цепью.
Граф без рёбер, состоящий из единственной вершины, также считают цепью.

Слайд #7

Путь АDСАDСВ идёт «по кругу», проходя дважды через вершины
А, D и С.
Путь, не являющийся простым.

Слайд #8

Иногда возникает необходимость выйти из вершины и вернуться в неё же.
Такие возвращающиеся в начальную точку пути называют циклами.
Цикл в графе — это замкнутый путь, у которого начало и конец в одной вершине, а рёбра и промежуточные вершины не повторяются.

Слайд #9

Простейший цикл — петля, которая состоит из одной вершины и одного ребра (см. рис. 25).

Слайд #10

Начальной вершиной цикла можно считать любую вершину.

Граф на рисунке имеет цикл АDСА.
Этот же цикл можно обозначить DСАD, или САDС, или просто АDС, как мы обычно обозначаем треугольники в геометрии.
Если граф состоит из одного-единственного цикла, то такой граф также называют циклом.

Слайд #11

Граф называется связным, если две любые вершины в этом графе соединены путём.
На рисунке 29 показаны два графа — слева связный, а справа — несвязный, который можно представить как два отдельных связных графа.

Слайд #12

Вопросы:
1. Своими словами объясните, что такое путь в графе.
2. Объясните, что такое цепь.
3. Может ли в цепи рёбер быть больше, чем вершин?
4. Объясните, что такое цикл.
5. Может ли в цикле рёбер быть меньше, чем вершин?
6. Какой граф называют связным?

Слайд #13

№ 131
Граф называется связным, если две любые вершины в этом графе соединены путём.
а) связной граф;
б) несвязной граф.

Слайд #14

Цепь (простой путь) – путь, в котором не повторяются ни вершины, ни ребра.
№ 132
ADEB, AFB, ADFEB

Слайд #15

№ 134
а)1, 5, 8;
б) 2, 4;
в) 3

Слайд #16

№ 136
а)
б)

Слайд #17

№ 139
Земля
Марс
Меркурий
Венера
Юпитер
Плутон
Нептун
Сатурн
Уран
Ответ: нет, нельзя. Вершины не связаны.