Пути в графе. Связные графы. Вероятность и статистика. 7 класс

Пути в графе Связные графы

Открываем новые знания

Цепи

Как в графе по рёбрам можно «пройти» из вершины А в вершину В?

Как в графе по рёбрам можно «пройти» из вершины А в вершину В? Из вершины А в вершину В можно «пройти» разными способами: АСВ;

Как в графе по рёбрам можно «пройти» из вершины А в вершину В? Из вершины А в вершину В можно «пройти» разными способами: АСВ; АDFEB;

Как в графе по рёбрам можно «пройти» из вершины А в вершину В? Из вершины А в вершину В можно «пройти» разными способами: АСВ; АDFEB; ADCADCB; …

Как можно назвать последовательность рёбер графа, соединяющих вершины А и В?

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

Чем отличается путь ADCADCB от путей АСВ и АDFEB?

Чем отличается путь ADCADCB от путей АСВ и АDFEB? В путях АСВ и АDFEB вершины и рёбра не повторяются.

Как можно назвать путь, в котором вершины и рёбра не повторяются?

Как можно назвать путь, в котором вершины и рёбра не повторяются? Путь, в котором вершины и рёбра не повторяются, называется простым путём или цепью.

Граф, состоящий из одной − единственной цепи, − цепь. Граф, состоящий из одной вершины, − цепь.

Циклы

Какими путями можно пройти без повторения рёбер из вершины А в ту же вершину А?

Какими путями можно пройти без повторения рёбер из вершины А в ту же вершину А? Из вершины А в вершину А можно пройти без повторения рёбер разными путями: ADCA,

Какими путями можно пройти без повторения рёбер из вершины А в ту же вершину А? Из вершины А в вершину А можно пройти без повторения рёбер разными путями: ADCA, ADFEBCA,…

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

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

Граф, состоящий из одного − единственного цикла, − цикл. Граф, состоящий из одной вершины и одного ребра, − цикл.

Связные графы

Какой граф называется связным?

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

Упражнения

да нет Упражнение №1 На рисунке изображён граф. Является ли граф цепью?

да Упражнение №1 На рисунке изображён граф. Является ли граф цепью?

да Упражнение №1 На рисунке изображён граф. Является ли граф цепью?

да Упражнение №1 На рисунке изображён граф. Является ли граф цепью?

да Упражнение №1 На рисунке изображён граф. Является ли граф цепью?

да Упражнение №1 На рисунке изображён граф. Является ли граф цепью?

Упражнение №2 На рисунке изображён граф. Является ли граф цепью? да нет

Упражнение №2 На рисунке изображён граф. Является ли граф цепью? нет

да нет Упражнение №3 На рисунке изображён граф. Является ли граф цепью?

да Упражнение №3 На рисунке изображён граф. Является ли граф цепью?

Упражнение №4 На рисунке изображён граф. Является ли граф цепью? да нет

Упражнение №4 На рисунке изображён граф. Является ли граф цепью? нет

да нет Упражнение №5 На рисунке изображён граф. Является ли граф циклом?

да Упражнение №5 На рисунке изображён граф. Является ли граф циклом?

да Упражнение №5 На рисунке изображён граф. Является ли граф циклом?

да Упражнение №5 На рисунке изображён граф. Является ли граф циклом?

да Упражнение №5 На рисунке изображён граф. Является ли граф циклом?

да Упражнение №5 На рисунке изображён граф. Является ли граф циклом?

да Упражнение №5 На рисунке изображён граф. Является ли граф циклом?

да Упражнение №5 На рисунке изображён граф. Является ли граф циклом?

да Упражнение №5 На рисунке изображён граф. Является ли граф циклом?

Упражнение №6 На рисунке изображён граф. Является ли граф циклом? да нет

Упражнение №6 На рисунке изображён граф. Является ли граф циклом? да

да нет Упражнение №7 На рисунке изображён граф. Является ли граф циклом?

нет Упражнение №7 На рисунке изображён граф. Является ли граф циклом?

да нет Упражнение №8 На рисунке изображён граф. Является ли граф циклом?

нет Упражнение №8 На рисунке изображён граф. Является ли граф циклом?

Упражнение №9 На рисунке изображён граф. Является ли граф связным? да нет

Упражнение №9 На рисунке изображён граф. Является ли граф связным? нет

да нет Упражнение №10 На рисунке изображён граф. Является ли граф связным?

да Упражнение №10 На рисунке изображён граф. Является ли граф связным?

Вопросы

Что такое путь в графе? Что такое цепь в графе (простой путь)? Какой граф называется связным? Что такое цикл в графе?