| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 7 | cnnfls_csy | 3569 |
| 9 | ecnerwala | 3494 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 158 |
| 4 | awoo | 158 |
| 4 | cry | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | maroonrk | 152 |
Здравствуйте , хотелось бы узнать , существует ли алгоритм, с помощью которого можно было бы вычислить количество остовных деревьев в заданном графе быстрее чем за O(n^3) как это указано тут : http://e-maxx.ru/algo/kirchhoff_theorem ?
Заранее спасибо !
Если граф полный, то можно быстрее: ответ равен n(n - 2).
Или может Ваш граф чем другим примечателен?
Можно даже расширить класс графов :-)
Пусть G = Kn - {e1, e2..., em}. Тогда, чтобы свести задачу к полному графу, достаточно использовать формулу: Ans(G) = Ans(G + e1) - Ans(G / e1). Где (+) — это добавление ребра в граф, а (/) — стягивание концов ребра в одну вершину.
Итого O(n + 2m).
Например, можно находить определитель матрицы Кирхгофа быстрее чем за O(n^3).
Там ведь очень просто :)
Три раза прочитал пост и нигде не увидел чтобы требовалось просто
Минус тридцать один! Раньше, если послать кого-то, то так не минусовали. Офигеть...
Поведай как, пожалуйста.
Ну есть же модные способы подсчета определителя за O(n^2.376). В википедии даже ссылочка на статью есть, где описан этот способ. Я, правда, сомневаюсь, что в реальных задачах его можно использовать, но вопрос был про сложность "быстрее чем за O(n^3)"...
А вообще, что-то мне подсказывает, что автор топика хочет решить задачу, где нужно найти количество остовных деревьев в графе, который состоит из циклов и простых путей (с одной идущей сейчас олимпиады). Пусть он меня поправит, если это не так:)
Ясно, я подумал есть что хорошее для матричек нужного нам вида.