Предположим, что в некотором графе можно по рёбрам «пройти» из вершины А в вершину В, то есть существует последовательность рёбер, соединяющих вершины А и В. Такую последовательность называют путём из вершины А в вершину В. В графе, показанном на рисунке 28, есть несколько путей из вершины А в вершину В. Например, есть путь, состоящий из рёбер АС и СВ. Этот путь можно обозначить тремя буквами АСВ. Есть более длинный путь ADFEB. Можно придумать более сложный путь, который заставит нас немного «покружить», — ADCADCв. В путях АСВ и ADFEB вершины не повторяются. Такие пути называют простыми путями или цепями. Путь ADCADCB идёт «по кругу», проходя дважды через вершины А, Д и С. Цепь (простой путь) — это путь в графе из одной вершины в другую, в котором вершины и рёбра не повторяются.

Фото задания

×