Ответы на вопросы стр.55 ГДЗ Бунимович Булычев 10 класс (Алгебра)
1. Дайте определение пути в графе.
Путь в графе —последовательность вершин, в которой каждая вершина соединена со следующим ребром.
2. Что такое цепь?
Цепь (простой путь) в графе — это последовательность вершин и рёбер, где каждое последующее ребро соединяет текущую вершину со следующей в последовательности.
3. Что такое цикл?
Цикл в графе — это путь, у которого начало и конец — в одной вершине, а рёбра и промежуточные вершины не повторяются.
4. Какой цикл называется эйлеровым?
Эйлеров цикл в теории графов — замкнутый путь, проходящий через каждое ребро графа ровно по одному разу.
5. Сформулируйте теорему Эйлера.
Эйлеров цикл в связном графе (или мультиграфе) существует тогда и только тогда, когда все вершины графа (или мультиграфа) имеют чётные степени.
Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.
Цепь (простой путь) в графе — это последовательность вершин и рёбер, где каждое последующее ребро соединяет текущую вершину со следующей в последовательности.
Цикл в графе — это путь, у которого начало и конец находятся в одной вершине, а рёбра и промежуточные вершины не повторяются.
Эйлеров цикл — это замкнутый путь, проходящий через каждое ребро графа ровно по одному разу.
Теорема Эйлера: в связном графе (или мультиграфе) эйлеров цикл существует тогда и только тогда, когда все вершины графа имеют чётные степени.
Ответ
- Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.
- Цепь — последовательность вершин и рёбер, где каждое последующее ребро соединяет текущую вершину со следующей.
- Цикл — путь, у которого начало и конец совпадают, а рёбра и промежуточные вершины не повторяются.
- Эйлеров цикл — замкнутый путь, проходящий через каждое ребро графа ровно один раз.
- Теорема Эйлера: эйлеров цикл в связном графе существует тогда и только тогда, когда степени всех его вершин чётные.
