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

Докажите, что найдется вершина, из

Докажите, что найдется вершина, из

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

Заметим, что у нас в ориентированном графе разрешаются дуги из вершины в себя саму (петли), несколько дуг из одной вершины в другую (кратные дуги), «встречные» дуги (из Л в В и из В в Л).

То, что раньше называлось графом, мы теперь будем называть неориентированным графом.

Теория графов 2

Задача 9. Дайте (формальные!) определения пути и цикла в ориен­тированном графе.

Определение 2. Ориентированный граф называется сильно связ­ным, если для любых двух его вершин существует путь как из первой во вторую, так и из второй в первую.

Задача 10. Какие из следующих графов сильно связны?

 

Определение 3. Ориентированный граф называется связным, если он окажется связным неориентированным графом после того, как мы сотрем стрелки с его дуг.

Задача 11. а) Приведите пример связного, но не сильно связного ориентированного графа.

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

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

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

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

Задача 15* (задача 17* из листка «Теория графов 1»). В полном не­ориентированном графе на ребрах как-то расставили стрелки. До­кажите, что полученный граф гамильтонов (т. е. существует путь, проходящий по каждой вершине ровно по одному разу).