Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Упражнения

5.1. Пусть G — ориентированный граф без петель и параллельных дуг. Пусть Докажите, что а) граф G имеет ориентированный путь длины не менее k и б) если то граф G имеет контур длины не менее

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

5.3. Ориентированный разрез ориентированного графа — это разрез все дуги которого или исходят из , или заходят в S. Покажите, что дуга ориентированного графа принадлежит либо ориентированному разрезу, либо контуру, но не принадлежит им одновременно. (Это частный случай результата, известного под названием «лемма о раскраске дуг», который доказывается в гл. 10, теорема 10.31.)

5.4. Покажите, что для ориентированного графа G, имеющего не менее одной дуги, следующие утверждения равносильны: а) граф G не имеет контуров и б) любая дуга графа G входит в ориентированный разрез.

5.5. Покажите, что для ориентированного графа G, имеющего по крайней мере одну дугу, следующие утверждения равносильны: а) граф G — сильно связный, б) любая дуга графа G лежит в контуре и в) граф G не имеет ориентированных разрезов.

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

5.7. Покажите, что сильно связный граф, содержащий цикл нечетной длины, содержит также контур нечетной длины.

5.8. Пусть — такой ориентированный граф, что для . Покажите, что в графе G имеется I реберно-непересекающихся ориентированных -путей.

5.9. Покажите, что сильно связный граф имеет остовный ориентированный маршрут.

5.10. Что из себя представляет длиннейшая циклическая последовательность, образованная из трех символов так, что никакая подпоследовательность из четырех символов не повторяется? Приведите пример такой последовательности.

5.11. Найдите такую циклическую последовательность из семи и семи «1», что все -разрядные двоичные последовательности, кроме 0000 и 1111, являются ее подпоследовательностями.

5.12. Докажите, что гамильтонов контур соответствует ориентированной эйлеровой цепи Всегда ли имеет гамильтонов контур?

5.13. Покажите, что число ориентированных эйлеровых цепей в ориентированном графе, имеющем вершин и дуг, четно.

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

5.15. Покажите, что любой турнир сильно связен или его можно преобразовать в сильно связный турнир сменой ориентации только одной дуги.

5.16. Подмножество называтся независимым множеством графа , если никакие две вершины S не смежны. Докажите, что ориентированный граф G без петель имеет такое независимое подмножество S, что всякую вершину v графа G, не входящую в подмножество S, можно достичь из вершины в подмножестве S ориентированным путем длины не более 2 [5.17]. Этот результат имеет интересное следствие: турнир обладает вершиной, из которой все остальные достигаются ориентированным путем длиной не более 2.

5.17. Покажите, что очки турнира на -вершинах удовлетворяют условию

<< Предыдущий параграф Следующий параграф >>
Оглавление