Главная → Уроки → Вероятность и статистика 7 класс

§ 20. Пути в графе. Связные графы

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

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

Схема тропинок лесопарка: семь полян-вершин А, Б, В, Г, Д, Е, Ж и девять тропинок-рёбер — А—Б, А—В, Б—В, Б—Г, В—Д, Г—Д, Г—Е, Д—Е, Е—Ж. Поляна Ж соединена только с Е, а из А выходят две тропинки — к Б и к В
Рис. 1. Схема тропинок лесопарка: семь полян и девять тропинок

Путь

Путь из вершины А в вершину Ж — это цепочка рёбер, по которым от А можно «пройти» до Ж. Записывают путь буквами вершин подряд, в порядке прохождения. На рисунке 1 из А в Ж ведёт путь АБГЕЖ, есть и другой — АВДЕЖ, и более длинный АБВДГЕЖ из шести тропинок.

Цепь

В путях АБГЕЖ и АБВДГЕЖ ни одна поляна не встречается дважды. Такие пути называют цепями, или простыми путями.

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

Дальше — в приложении

Полный пересказ по учебнику «Вероятность и статистика 7 класс», тест из большого пула вопросов и разбор ошибок с ИИ-репетитором. За сданный тест ребёнок получает экранное время — родители задают, сколько минут стоит урок.

Пройти урок бесплатноКак это работает

Вопросы из теста

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

Какой путь называют цепью (простым путём)?

Посмотри на схему тропинок. Какая из записей задаёт путь из А в Ж?

← § 19. Степень вершины§ 21. Задача о Кёнигсбергских мостах, эйлеровы пути и эйлеровы графы →