Глава 19. Вероятность и статистика. Введение в теорию графов
§ 66.
Связность, цепи, циклы и пути
Связность, цепи, циклы и пути
Ищите пути, различайте цепь и цикл, определяйте связность графа.
Запомни
Записывайте решение последовательно. Для вычислительных задач делайте проверку, для текстовых — указывайте модель и единицы, для геометрических — чертёж и обоснования.
Вопросы и задания
- Постройте связный граф с 6 вершинами и минимально возможным числом рёбер.
- Постройте несвязный граф с 6 вершинами и 4 рёбрами.
- Найдите все простые пути из A в D в графе-цепочке A–B–C–D с дополнительным ребром A–C.
- Приведите пример цепи, не являющейся циклом.
- Приведите пример цикла длины 5.
- Можно ли удалить одно ребро из цикла так, чтобы граф остался связным?
- На схеме дорог найдите кратчайший по числу рёбер путь между двумя пунктами.
- Составьте задачу из геометрии, которую удобно представить графом.
Ключевые понятия:Вероятность и статистика7 класссвязностьцепьциклпуть