8.5. Все задачи

Задача 8.1: Докажите, что действительно получится дерево. Точнее, докажите, что в полученном подграфе не будет циклов. Верно ли, что это всегда будет дерево, покрывающее все вершины исходного графа? Как это зависит от того, как мы вызываем поиск в глубину (раздел Как вызывать процедуру )? На самом деле доказательство не очень тривиально.

Задача 8.2: Понимаете, почему может ничего не получиться, если массив \(was\) изначально неправильно заполнен? Заодно что вы можете сказать по поводу проверки ориентированного графа на связность?

Задача 8.3: Может ли эта задача иметь несколько решений? Т.е. может ли быть так, что разбиение вершин графа на доли неоднозначно? Попробуйте сформулировать как можно более простой критерий, который отвечает на этот вопрос. Только, прежде чем читать дальше, ответьте на это задание.

Контрольный вопрос 8.4: Ответ на какой вопрос? :)

Задача 8.5: Реализуйте этот алгоритм с помощью поиска в ширину.

Задача 8.6: А почему также нельзя проверять граф на трехдольность?

Задача 8.7: Напишите эти две программы. Тщательно потестируйте их. Переберите все возможные подлые случаи. Представьте, что вы — жюри на некоторой олимпиаде и даёте участникам такую задачу. Вы знаете, как её решать, поэтому можете продумать, какие тут подлости возможны — на них и делайте тесты. Например, очевидно, надо оттестировать связные и несвязные графы; деревья, леса, несвязные графы, у которые первая компонента является/не является деревом; линейные структуры (т.е. первая вершина связана со второй, вторая — с третьей и т.д.) и разветвлённые деревья; длинные циклы, пустые графы и т.д.

При написании программы почти наверняка вы столкнётесь с одним подводным камнем. Осознайте его, поймите, почему ваша программа не работает, и исправьте программу так, чтобы она работала.

Текст программы тут я приводить не буду, приведу только в ответах. У этой задачи есть подсказка; порешав задачу, посмотрите подсказку до ответа.

Задача 8.8: Попробуйте сформулировать это условие абсолютно точно, т.е. указать, какое условие на связность графа надо добавить к условию на степени вершин, чтобы получить критерий существования эйлерова цикла/пути в графе, такой, что, если он выполняется, то путь/цикл точно есть, иначе точно нет.

Задача 8.9: Напишите и оттестируйте алгоритм поиска эйлерова цикла в ориентированном графе.

Задача 8.10: Подумайте, как искать эйлеров путь в ориентированном графе. А именно, каковы критерии существования пути в ориентированном графе? Как надо писать алгоритм? Почему он будет работать? Напишите и, конечно, потестируйте его.

Контрольный вопрос 8.11: Понимаете ли вы, что этот класс намного шире, чем деревья? Т.е. что ациклический граф — это не только ориентированное дерево?

Задача 8.12: Напишите эту программу в простейшем варианте. Попробуйте придумать, как можно заставить её работать быстрее. На самом деле это делается в два этапа: во-первых, заметим, что каждый раз пересчитывать исходящую степень не надо, а на втором этапе вам пригодится структура данных очередь или стек. Попробуйте придумать это сами. Если не придумаете, то смотрите подсказки, которые есть по этому заданию (впрочем, как и по некоторым другим). Обязательно потом прочитайте подсказки и ответ.

Задача 8.13: (простое) Так ли ясно? Приведите пример связного ориентированного графа, на котором однократно запущенный поиск в глубину не обойдёт все вершины. Не забудьте, что связный ориентированный граф — это такой, который будет связным, если забыть про ориентацию его рёбер. Вспомните доказательство того, что поиск в глубину в неориентированном графе обходит всю компоненту связности, и поймите, почему это доказательство не работает в случае ориентированного графа.

Задача 8.14: Приведите пример ациклического графа, в котором мы при поиске в глубину попадём в вершину, в которой уже были раньше.

Задача 8.15: Попробуйте понять, почему в вышеприведённой идее нельзя в лоб заменить алгоритм топсорта с помощью поиска в глубину на «алгоритм Кнута». Но «алгоритм Кнута», конечно, также несложно приспособить для проверки графа на ацикличность; придумайте, как.

Задача 8.16: Зачем требовать транзитивность? Давайте я попробую определить компоненты слабой связности следующим образом: две вершины \(u\) и \(v\) находятся в одной компоненте слабой связности, если хотя бы в одну сторону есть путь, т.е. или есть путь из \(u\) в \(v\), или назад, или и туда и туда. Имеет ли смысл такое определение? Т.е. сумеете ли вы в любом графе разбить все вершины на компоненты слабой связности?

Задача 8.17: (нетривиальное) Не очевидно, что не работает такой алгоритм: оттопсортим граф и пойдём поиском в глубину в неинвертированном графе справа налево, т.е. от последних вершин к первым. Придумайте контрпример к этому алгоритму (конечно, придумать контрпример проще, чем доказать корректность :) ).

Задача 8.18: Докажите, что конденсация произвольного графа является ациклическим графом.

Задача 8.19: Как надо правильно и проще всего сортировать вершины по временам выхода? Аналогично по временам входа.

Задача 8.20: Постоянно, когда формулирую определения, хочется сказать «компонент связности увеличивается на одну». Можно ли так говорить, т.е. будут ли получающиеся определения эквивалентны тем, что даны выше?

Задача 8.21: Есть ли какая-нибудь простая связь между мостами и точками сочленения? Т.е. верно ли, что а) каждый конец моста — это точка сочленения? б) каждая точка сочленения является концом некоторого моста? в) может быть, ещё что-нибудь придумаете?

Задача 8.22: Докажите это свойство.

Контрольный вопрос 8.23: Что должно быть на месте многоточия?

Задача 8.24: Додумайте этот алгоритм и напишите его.

Задача 8.25: Додумайте этот алгоритм и напишите его.