Доказательство тождества Эйлера (V — E + F = 2) "методами топологии" — самое наркоманское, что я видел в своей жизни.
ПОТРЯСЕМ, ПУСТЬ ПЛЮСИКИ ЗАПАДУТ. Охмай.
Ну бляд. Ну я не хочу читать про сведение поиска вершинной 3-связности к поиску реберной 3-связности.
Ну бляд.
SOMEPROP(v) = min({v} U {w | v is reachable from w});
А зачем теперь доказывать, что SOMEPROP <= v ?
._.
Я сейчас буду сильно плакать.
dump.bitcheese.net
Утверждается, что это дерево. Т.е., там нет циклов. БЛЯДЬ ДА ВЫ ЧТО, КАК ЭТО НЕТ ВОТ ЖЕ ОНИ! ЗДОРОВЕННЫЕ! 9 12 10 11 9, 5 7 4 5, етц, ЧТО ЗА ХУЙНЯ?
По остовному дереву(оно тут не ориентировано) ходить можно, вверх-то точно, это несомненно. НО ТОГДА ЭТО НЕ ДЕРЕВО!!!! РЕБЯТА!!! БЛЯДЬ?!?!
Говно какое-то.
В графе, в котором есть как минимум две взаимнодостижимых вершины, мы нумеруем все вершины от 1 до |V| так, что если есть путь из v в w, то номер v меньше номера w.
Но они же взаимнодостижимы.... v > w && w < v ._. Блядь, ну что такое...
"vertex v followed by a frond", где frond — ребро, удовлетворяющее некоторым свойствам(не важно каким).
Граф у нас ориентированный(частично), и, как мне кажется, фраза должна означать, что из v ВЫХОДИТ frond. Но, судя по всему, имеется ввиду, что оно туда входит. Или и то, и то(что достаточно логично, но, кажется, не верно).
~3.14здец.
Уважаемые господин Тарьян и господин Хопкрофт — наркоманы.
Приведу одну строку из их листинга в статье вышеупомянутых авторов (#1623085).
...
else if (NUMBER(w) < NUMBER(v)) and (w != u) or (FLAG(v) + FALSE)) then begin
...
FLAG — массив "булов".
FLAG(v) + FALSE.
Что это должно значить? ЧТО?
И вообще, статья, в целом, убийственная. Ничего сложнее для моего понимания в жизни не читал.
,
Няяяяяяяяяяяя ._.
dtic.mil
"Finding the triconnected component of a graph"
J.E. Hopcrof, R.E. Tarjan.
Жуйк, говорят, есть статья о три-связности графов, авторов не помню, но знаю, что там ~40 страниц. На английском или русском. (в голове вертятся фамилии "Лейзерсон" и "Томпсон", но это наверное не про то).
Мне очень хотелось бы их получить раньше, чем завтра. Завтра они у меня будут.
Ну и вообще, если имеешь — интересных статей про три-связность накидай.
Спасибо.
дак как там все контуры в орграфе искать?
а как правильно искать все минимальные s-t пути во взвешенном орграфе с неотрицательными весами?
я, правда, изобрел что-то сложное: поиск в ширину в обратном направлении (от t) с переходами (против направления дуги соотв.) только по дугам с весом равным разности между длинами кратчайших путей (от s) до текущей и следующей (которая на другом конце дуги) вершин. но конечно же ничего об этом методе доказывать даже не пытался.
есть реализация алгоритма Форда-Фалкерсона. внезапно оказалось, что нужен еще и минимальный разрез. как его лучше искать?
(знание максимального потока, вроде как должно бы помочь, только не соображу как)
Ух какая няка, кто-нибудь пользовался? gephi.org
Кто ещё не видел графы github сообществ: lumberjaph.net ? Многое о языке программирования вам расскажут графы python, ruby и php ;)