Вопросы к пункту 3 «Пути, цепи и циклы» на странице 55, ГДЗ по алгебре за 10 класс к учебнику Бунимовича вероятность и статистика

Вопросы к пункту 3 «Пути, цепи и циклы».

Путём (маршрутом) в графе или мультиграфе называется такая последовательность вершин, в которой каждая вершина соединена со следующей за ней вершиной ребром. Чтобы задать путь, достаточно перечислить по порядку его вершины.

Длиной пути называется количество пройденных рёбер; оно на 1 меньше количества вершин в записи пути.

Вершины и даже рёбра в пути могут повторяться. Например, если в графе есть рёбра \(ab\), \(bc\) и \(cd\), то \(abcd\) — путь длины 3, и \(abab\) — тоже путь длины 3, хотя ребро \(ab\) пройдено в нём трижды.

Ответ: путь (маршрут) в графе — это последовательность вершин, в которой каждая соединена со следующей ребром; длина пути равна числу пройденных рёбер и на 1 меньше числа вершин в записи, а вершины и рёбра в пути повторяться могут.

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

Например, если в графе есть рёбра \(ab\), \(bc\) и \(ca\), то путь \(abca\) — цепь, а путь \(aba\) цепью не является: ребро \(ab\) пройдено в нём дважды.

Ответ: цепь — это путь без повторяющихся рёбер; вершины в цепи повторяться могут.

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

Вершины внутри цикла повторяться могут, и не только начальная: например, в цикле \(bcdgcfb\) вершина \(c\) встречается два раза. А замкнутый путь \(aba\) циклом не является — ребро \(ab\) пройдено в нём дважды, и цепью он не будет.

Если все вершины цикла различны (кроме совпадающих начальной и конечной), то такой цикл называется простым.

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

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

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

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

Теорема Эйлера: эйлеров цикл в связном графе (или мультиграфе) существует тогда и только тогда, когда все вершины графа (или мультиграфа) имеют чётные степени.

Оба требования теоремы важны. Так, у мультиграфа, составленного из двух отдельных треугольников, все степени равны 2, но эйлерова цикла нет: из одного треугольника в другой не попасть, потому что граф не связен.

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

Ответ: эйлеров цикл в связном графе (или мультиграфе) существует тогда и только тогда, когда все его вершины имеют чётные степени.