4. а) Укажите по рисунку путь из вершины О в Л; б) запишите цепь, ведущую из вершины К в Ч; в) Укажите какой-нибудь цикл; г) Является ли связным граф, изображенный на рисунке?

Решение:

На данном графе вершины обозначены буквами: О, К, Т, Л, Ч, Р.

а) Путь из вершины О в Л:

• О → К → Т → Л

б) Цепь, ведущая из вершины К в Ч:

• К → Т → Ч

в) Цикл:

• К → Т → Ч → (связь между Ч и Т) → К (пример цикла). Другой пример: О → К → Т → Л → (связь между Л и Т) → Т → К → О

г) Является ли связным граф, изображенный на рисунке?

• Да, является. Из любой вершины графа можно добраться до любой другой вершины, пройдя по рёбрам.

Ответ: а) О → К → Т → Л; б) К → Т → Ч; в) К → Т → Ч → К (пример); г) Да.