Семинар 2.

1.	При удалении всех мостов граф распадается на компоненты рёберной двусвязности,
	т.е. такие что внутри каждой компоненты любые две вершины рёберно двусвязны.
	Между двумя компонентами рёберной двусвязности не может быть более одного ребра
	(почему?), которое как раз и будет мостом. Таким образом, компонента рёберной
	двусвязности — максимальный подграф, не содержащий мостов.
	Аналогично компонента вершинной двусвязности — максимальный подграф, не
	содержащий точек сочленения. Заметим, что в то время как компоненты рёберной
	двусвязности не пересекаются, компоненты вершинной двусвязности могут иметь
	общие вершины.

2.	Алгоритм нахождения мостов и компонент рёберной двусвязности.
	Делаем первый проход в глубину, каждую новую вершину добавляем в конец списка,
	а каждое пройденное ребро ориентируем против направления обхода.
	Второй обход в глубину делаем по порядку из списка, сделанного в первом обходе,
	при этом по ориентированным рёбрам ходим только в разрешённом направлении.
	Деревья получающиеся в результате второго обхода будут соответствовать
	компонентам двусвязности.

3.	Сильная связность ориентированного графа (есть путь из любой вершины в любую).
	Компоненты сильной связности. Конденсация графа. Идея факторизации.
	Конденсированный граф не содержит циклов (почему?).

4.	Алгоритм нахождения компонент сильной связности. Смысл тот же, что и в пункте 2.
	Мы хотим, чтобы наш алгоритм крутился в одной компоненте, всю её обрабатывал,
	затем перемещался на другую, а обратно не возвращался. Для этого сконденсируем
	наш граф и получим новый граф без циклов. Транспонирование коммутирует с
	конденсацией. Мы хотим топологически отсортировать сконденсированный граф
	(он же без циклов!) и запустить поиск в глубину с самого конца, но у нас это
	сделать не получится, ведь сконденсировать граф как раз означает найти компоненты
	сильной связности. Исходный же граф сортировать нельзя, так как он содержит
	циклы. Но можно при обходе графа в глубину не замечать обратных рёбер и поступать
	так же как и при топологической сортировке (выписывать вершину в начало списка,
	когда заканчиваем её обработку). В итоге получится топологическая сортировка леса
	обхода, но не простая, а обладающая специальным свойством.
	Про отсортированные таким образом вершины можно сказать следующее: если есть
	путь из вершины U сконденсированного графа в вершину V, то найдётся вершина
	u исходного графа из класса U, которая идёт перед всеми вершинами из V.
	Действительно, либо мы попали в V обрабатывая U, и тогда мы его весь обработаем,
	только потом вернёмся в U и дообработаем там некоторые вершины, либо мы сначала
	целиком обработали V, и только потом как-то попали в U. Теперь если мы
	транспонируем граф и будем брать вершины по порядку из нашего списка и запускать
	на них обход в глубину, то во-первых, каждая сильно связная компонента целиком
	попадёт в какое-то из деревьев обхода (так как сильно связные компоненты
	инвариантны относительно транспонирования), а во-вторых каждое дерево обхода
	будет содержать не более одной компоненты. Действительно, если мы начали
	обход с компоненты V, а потом вдруг перешли в компоненту U, то это значит,
	что в исходном графе был путь из U в V, а это значит, что должна была
	найтись вершина u из U, которая шла раньше любой вершины из V, поэтому
	мы компоненту U должны были обработать раньше. Итого, каждое дерево обхода
	соответствует одной компоненте сильной связности. Это алгоритм Косарайю.