Разместить граф на торе.
 |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [18.97.9.174] |
|
|
правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
Модераторы: Akina, shadeofgray
Разместить граф на торе.
|
Сообщ.
#1
,
|
|
|
|
Дана такая задачка. (Взята не из головы, а конкретное задание, данное преподавателем)
Задан граф (неважно как, про граф мы знаем все, или почти все Нужно выяснить можно ли разместить граф на торе без самопересечения ребер... Понимаю, что есть какая-то связь с планарностью графа.. Теорему о планарности графа знаю, но тор на полскость не сильно похож Подскажите плз хоть чем-нибудь...... Ссылочкой, верной мыслью, алгоритмом или просто добрым советом )) |
|
Сообщ.
#2
,
|
|
  |
тор= плоскость + ручка
планарное число увеличивается на единицу |
|
Сообщ.
#3
,
|
|
|
|
а почему? я сколько ни силился представить, так и не получилось
 . у меня получается, что там всё будет так же, как на плоскости. |
|
Сообщ.
#4
,
|
|
|
|
В 3-х мерном пространстве можно расположить любой граф, это понятно. На торе без пересечиний ребер можно расположить и полный 5-вершинный и полный двудольный 3,3. На плоскости нельзя. Собсвенно т. Понтрягина-Куратовского и заключается в том, что если граф не содержит подграфов гомеоморфных К3,3 и G5 то он планарный. Из этого может следовать, что если эти графы можно расположить на торе, то любой граф можно ???
|
|
Сообщ.
#5
,
|
|||
|
|
нет на торе тоже нельзя любой граф изобразить нельзя например К(7,7) |
|
Сообщ.
#6
,
|
|
 |
Почему на торе не как на плоскости:
Вот возьмем планарный граф. Разместим его его на плоскости. А дырку от того бублика поместим в середине одной из ячеек. Выход из етой дырки выведем в другую ячейку или во внешнюю ячейку графа. Получится, что любую вершину графа, содержащуюся в етой ячейке можно связать с любой из других вершин, и при етом не будет пересечений ребер. Отсюда и мораль -- на двусторонней печатной плате, являющейся N-тором (бубликом с N дырками) можно развести любую эл. схему.  |
|
Сообщ.
#7
,
|
|
|
|
Где можно найти исходники по определению планарности графа и укладки графа на плоскости?
|
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:
[ Script execution time: 0.0805 ] [ 15 queries used ] [ Generated: 5.10.26, 23:18 GMT ]