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

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

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

Не понял параграф? Бесплатный ИИ-репетитор по вероятности и статистике 7 класс объяснит по шагам, но готовый ответ не скажет.

Спросить репетитора

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

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

Путь

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

Цепь

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

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

Хочешь больше времени в телефоне?

В Family Track телефон открывается за уроки: прочитал параграф, сдал тест и получил минуты. Сколько минут стоит урок, решают родители. Отправь им ссылку, пусть посмотрят.

Отправить родителямПройти урок бесплатно

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

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

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

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

Не получается разобраться? Бесплатный ИИ-репетитор по вероятности и статистике 7 класс разберёт ошибку по шагам и не даст списать.

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