Упражнения

14.1. Транзитивная редукция ориентированного графа определяется как граф с минимальным числом ребер, транзитивное замыкание которого совпадает с графом G. Сконструируйте алгоритм нахождения транзитивной редукции ориентированного графа. Как этот алгоритм связан с алгоритмом транзитивного замыкания

14.2. Используя ПВГ, сконструируйте алгоритмы для следующих проблем:

а) топологическая сортировка вершин графа;

б) выделение мостов графа;

в) выделение остовного леса;

г) выделение множества базисных циклов и базисных разрезающих множеств;

д) проверка графа на двудольность;

в) проверка, является ли заданное множество ребер разрезом графа.

14.3. Рассмотрим граф G; пусть Т — остовный лес ПВГ для графа G. Пусть — число потомков v (включая ее саму). Докажите, что вершина w является потомком v тогда и только тогда, когда выполняется соотношение

14.4. Модифицируйте алгоритм ПВГ так, чтобы он включал шаги для вычисления

14.5. Пусть Т — дерево ПВГ в связном графе G. Пусть полный подграф графа G. Покажите, что все вершины лежат на одном ориентированном пути в Т.

14.6. Пусть Т — дерево ПВГ в ориентированном графе G. Покажите, что если С — ориентированный цикл графа вершина, входящая в С и имеющая минимальную глубину, то и — предок в Т любой вершины цикла С.

14.7. Поиск в ширину (ПВШ) просматривает связный граф G следующим образом:

S1. В начале ни одна из вершин G не помечена.

S2. Выбирать вершину s и пометить ее как 0.

S3. Положить .

S4. Пусть S — множество всех непомеченных вершин, смежных по меньшей мере с одной вершиной с меткой.

S5. Если S — пустое, то STOP, иначе пометить все вершины в S меткой .

S6. Положить и идти к шагу S4.

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

14.8. Покажите как ПВШ можно использовать для вычисления расстояния от вершины s до всех вершин связного графа G. (Под расстоянием между вершинами и и v мы понимаем длину -пути, включающего наименьшее число ребер.)

14.9. Покажите, что множество обратных ребер сводимого графа программы уникально, т. е. все остовные леса ПВГ имеют одно и то же множество обратных ребер [14.35].

14.10. Используйте результат теоремы 6.10 для построения алгоритма нахождения всех остовов связного графа.

14.11. Пусть Т — дерево на вершинах. Пусть — множество вершин Т. Мы можем сопоставить единственную последовательность Дереву Т следующим образом: пусть первая вершина степени 1 в Т, тогда вершина, смежная есть первый элемент последовательности Удалим из Т. Если первая вершина степени 1 в то вершина, смежная есть Удалим и будем повторять операцию до тех пор, пока не будет определена вершина Последовательность называется последовательностью Прюфера, связанной с Т. Ясно, что два различных дерева имеют различные последовательности Прюфера.

Дана последовательность для которой

Сконструируйте алгоритм построения дерева Т, для которого есть последовательность Прюфера (число ) буквенных последовательностей, которые могут быть построены из множества равно Каждая такая последовательность является последовательностью Прюфера для остова графа Поэтому существует взаимно-однозначное соответствие между последовательностями, построенными из каких-либо букв (не обязательно различных), принадлежащих множеству и остовами графа Таким образом, число остовов графа равно Это доказательство приведено Прюфером [14.59].

14.12. Используйте результат теоремы 9.10 для построения алгоритма нахождения хроматического числа графа,