Пути в графе Связные графы
Открываем новые знания
Цепи
Как в графе по рёбрам можно «пройти» из вершины А в вершину В?
Как в графе по рёбрам можно «пройти» из вершины А в вершину В? Из вершины А в вершину В можно «пройти» разными способами: АСВ;
Как в графе по рёбрам можно «пройти» из вершины А в вершину В? Из вершины А в вершину В можно «пройти» разными способами: АСВ; А 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 На рисунке изображён граф. Является ли граф связным?
Вопросы
Что такое путь в графе? Что такое цепь в графе (простой путь)? Какой граф называется связным? Что такое цикл в графе?
Спасибо за внимание!
