![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 18. Поиск на графе. 18.23.Дайте описание семейства графов с V вершинами, для которого на выполнение стандартного DFS на матрице смежности с целью обнаружения циклов
> 18.24. Постройте реализацию класса определения связности из программы 18.4 как > 18.25. Укажите, какие изменения следует внести в программу 18.5, чтобы она была • 18.26. Внесите в программу 18.5 такие изменения, чтобы она всегда могла вычислить двухпроходной эйлеров цикл, который, аналогично показанному на рис. 18.14, может быть начерчен таким образом, что не пересекает сам себя ни в одной вершине. Например, если бы поиск, представленный на рис. 18.14, должен был пройти по ребру 4-3 перед тем, как пройти по ребру 4-7, то цикл пересек бы сам себя; ваша задача заключается в том, чтобы добиться того, чтобы алгоритм избегал подобного рода ситуаций. 18.27. Разработайте версию программы 18.5, которая сортирует все ребра в порядке 18.28. Покажите, что граф принадлежит к числу раскрашиваемых двумя цветами тогда о 18.29. Объясните, почему подход, использованный в программе 18.6, не допускает обобщения, которое позволило бы получить эффективный метод определения, является ли конкретный граф раскрашиваемым тремя цветами. 18.30. Большая часть графов не относится к категории раскрашиваемых двумя цве о 18.31. Докажите, что в каждом связном графе имеются вершины, удаление которых не нарушает связности графа, и напишите функцию DFS, которая обнаруживает такие вершины. Указание: Рассмотрите листья дерева DFS. 18.31. Докажите, что каждый граф, состоящий из более чем одной вершины, содер
|