Таблицы Брадиса

Рассмотрим в графе максимальное поддерево.

Рассмотрим в графе максимальное поддерево.

Элементы математики в задачах - Г. А. Мерзон

б) Приведите пример связного ориентированного графа, в кото­ром для некоторых двух вершин А и В нет пути ни из А в В, ни из В в А.

 

Ответ. а)

 

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

Решение. Рассмотрим в графе максимальное поддерево. Оно связно, так как исходный граф связен, и в нем есть висячая вершина А. Теперь расставим стрелки на ребрах так, чтобы все они вели «от» А (то есть, если ребро соединяет две вершины В и С, и В дальше от А, чем С, то стрелка ведет от С к В).

На оставшихся ребрах, не содержащихся в максимальном поддере­ве, можно расставить стрелки произвольным образом. Видно теперь, что из А есть пути во все остальные вершины.

Задача 13. Можно ли так расставить на ребрах полного неориен­тированного графа стрелки, чтобы в полученном ориентированном графе не было циклов?

Решение. Можно. Занумеруем все вершины графа числами от 1 до п и расставим стрелки так, чтобы они вели из большей вершины в меньшую. Тогда в полученном графе циклов быть не может, так как вдоль любого пути номер вершины все время увеличивается.

Задача 14. В полном неориентированном графе на ребрах как-то расставили стрелки. Докажите, что найдется вершина, из которой существуют пути во все остальные.

Решение. Докажем по индукции: база для п = 2 очевидна. Пусть те­перь у нас есть полный граф с п вершинами, на ребрах которого произвольным образом расставлены стрелки. Удалим произвольную вершину А. В оставшемся графе с п — 1 вершиной есть вершина В, из которой существуют пути во все остальные. Если в исходном графе стрелка вела из В в А, то вершина В останется такой, какой нам надо. Если же стрелка вела из А в В, то получаем, что в исходном графе из вершины А существуют пути во все остальные.