ГДЗ по вероятность и статистика 7-9 класс Высоцкий, номер 131

№

Путь и связность графа

Есть ли в графе, изображённом на рисунке 30, путь: а) из вершины $A$ в вершину $C$ ; б) из вершины $B$ в вершину $F$ ? Связный ли это граф? На рисунке вершины $A,B,C,D$ соединены между собой, а вершины $E,F$ соединены отдельным ребром.

Решение

а) Из можно пройти по ребру , затем по ребру . Получается путь , значит, путь из в есть.

б) Вершины образуют одну часть графа, а — другую. Между этими частями ребра нет. Поэтому из невозможно попасть в .

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

Ответ

а) Да, например ; б) нет. Граф несвязный.

Помогло?

Номер 131