Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=922612 Sun, 20 Nov 2005 22:11:36 +0000 Разместить граф на торе. https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=922612 angel Алгоритмы https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=254705 Sun, 30 Nov 2003 00:52:03 +0000 Разместить граф на торе. https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=254705 Вот возьмем планарный граф. Разместим его его на плоскости. А дырку от того бублика поместим в середине одной из ячеек. Выход из етой дырки выведем в другую ячейку или во внешнюю ячейку графа. Получится, что любую вершину графа, содержащуюся в етой ячейке можно связать с любой из других вершин, и при етом не будет пересечений ребер. Отсюда и мораль -- на двусторонней печатной плате, являющейся N-тором (бубликом с N дырками) можно развести любую эл. схему. smile.gif ]]> Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=254431 Sat, 29 Nov 2003 13:19:00 +0000 Разместить граф на торе. https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=254431
Цитата (G. Gisborn @ 29.11.03, 02:35)
В 3-х мерном пространстве можно расположить любой граф, это понятно. На торе без пересечиний ребер можно расположить и полный 5-вершинный и полный двудольный 3,3. На плоскости нельзя. Собсвенно т. Понтрягина-Куратовского и заключается в том, что если граф не содержит подграфов гомеоморфных К3,3 и G5 то он планарный. Из этого может следовать, что если эти графы можно расположить на торе, то любой граф можно ???

нет на торе тоже нельзя любой граф изобразить

нельзя например К(7,7) ]]> esperanto Алгоритмы https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=254265 Sat, 29 Nov 2003 03:35:16 +0000 Разместить граф на торе. https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=254265 G. Gisborn Алгоритмы https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=91392 Tue, 06 May 2003 12:50:05 +0000 Разместить граф на торе. https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=91392 wormball Алгоритмы https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=91391 Tue, 29 Apr 2003 19:28:28 +0000 Разместить граф на торе. https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=91391 планарное число увеличивается на единицу]]> esperanto Алгоритмы https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=91390 Wed, 16 Apr 2003 07:49:59 +0000 Разместить граф на торе. https://forum.sources.ru/index.php?showtopic=9384&view=findpost&p=91390
Задан граф (неважно как, про граф мы знаем все, или почти все :)
Нужно выяснить можно ли разместить граф на торе без самопересечения ребер...
Понимаю, что есть какая-то связь с планарностью графа..
Теорему о планарности графа знаю, но тор на полскость не сильно похож :)
Подскажите плз хоть чем-нибудь......
Ссылочкой, верной мыслью, алгоритмом или просто добрым советом :)))

]]> vaxyzek Алгоритмы