Цитата(Kosya4ok @ 3.1.2008, 10:50  ) |
| как работает алгоритм разбиения графа |
на что?
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм разбиения графа (многоуровневая схема) |
| Автор: Kosya4ok 3.1.2008, 10:50 |
| Доброе утрО!Ещё раз всех с новым годом! Кто нить понимает как работает алгоритм разбиения графа и для чего он нужен, а именно многоуровневая схема? Для чего например сперва делается стадия укрупнения, стадия разбиения, стадия многоуровневого улучшения? Например, если у меня есть матрица смежности 1 2 3 4 5 6 7 1 0 0 0 0 0 0 0 2 1 0 0 0 0 1 0 3 1 1 0 0 0 0 0 4 1 0 1 1 0 0 1 5 0 0 1 0 0 1 0 6 0 1 0 0 1 0 0 7 0 0 0 1 1 0 0 Как то можно на листке бумаги применить данный алгоритмк такой матрице? |
| Автор: JackYF 3.1.2008, 13:57 | ||
на что? |
| Автор: Kosya4ok 3.1.2008, 15:37 |
| Эээ...вот и хотелось бы разоьбраться с этим алгоритмом. Вот сам алгоритм http://glaros.dtc.umn.edu/gkhome/metis/metis/overview Я просто сам пока не понимаю каки образом разбивается граф и как реализуется данный алгоритм....поэтому и создал тему Добавлено через 6 минут и 16 секунд А вот русский сайт...http://www.masters.donntu.edu.ua/2006/fvti/shepel/diss/index.htm |
| Автор: chozen 6.1.2008, 01:13 |
| Насколько я понял, суть алгоритма - выделение n-го кол-ва подграфов данного графа, основываясь на критерии наименьшего количества связей между подграфами (или общего минимального "веса" связей). Задача относится к классу NP, т.е. конкретного алгоритма не существует, имеются лишь решения частных случаев. Мой совет: если тебе это не жизненно необходимо, не забивай себе голову. Как правило, такими задачами занимаются целые исследовательские группы, так что подумай трижды, прежде чем залезать в теорию =))) ЗЫ но за ссылку на инф спс |
| Автор: Vitaly333 23.1.2008, 02:04 |
| Kosya4ok, у меня есть одна статья по многоуровым алгоритмам вложенных сечений .... я в ближайшем будущем хочу заняться ими. Там подробно все описано как находить сепараторы... всё на русском.. Если тебя заинтересует то можно вместе попробывать понять алгоритм и запрограммировать его! Вот кстати сама http://www.zsu.zp.ua/herald/articles/2813.pdf |
| Автор: Kosya4ok 17.2.2008, 12:57 |
| Извини что так долго не отвечал сильно был занят. Предложение по поводу алгоритма вложенных сечений ещё в силе? Пиши в аську 237160094. |
| Автор: coyl 27.2.2008, 14:12 | ||
Ну например для в схемотехнике для разбиения схемы на несколько плат с минимальным колличеством межблочных связей. |