Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Sp1
19 / 19 / 10
Регистрация: 07.02.2014
Сообщений: 35
1

Планарность графов по теореме Понтрягина-Куратовского

30.06.2014, 06:38. Просмотров 627. Ответов 0
Метки нет (Все метки)

Ищу в графе полный подграф из пяти вершин. Граф представлен вершинами, у каждой вершины есть список смежных ей. При количестве вершин в графе равном пяти все просто. Если их больше, я нахожу все возможные сочетания вершин из N по 5 без повторений и проверяю каждый из наборов на наличие (является ли) подграфа Куратовского. Сочетания находятся правильно, но результат проверки не всегда верен. Не подскажет кто-нибудь, как лучше проверить 5 вершин на это? Или 6 вершин на домики-колодцы?

Не по теме:

Другой алгоритм не предлагать, нужен именно этот. Про то, что искать надо гомеоморфные тоже знаю



Добавлено через 11 часов 50 минут
Решил проверять количество ребер между входящими в набор вершинами. Все верно.
Вопрос о втором подграфе все еще актуален.

Добавлено через 19 часов 50 минут
Решил простым перебором с разделением на две части. Всем спасибо.
1
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.06.2014, 06:38
Ответы с готовыми решениями:

Найти определитель массива по теореме Лапласа
Дан массив размера М х N найти определитель данного массива по теореме лапласа...

Задача на максимум Понтрягина
Добрый вечер! У меня задача на принцип максимума Понтрягина. Задача...

Теорие графов. Композиция двух неор. графов.
Здравствуйте. Прошу помощи уже здесь :| (old topic)... Прошу помочь с...

планарность графа
помогите проверить граф на планарность если дана таблица смежности...

Планарность графа
В новом районе города планируется построить 5 домов и соединить их скоростными...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.06.2014, 06:38

Графы. Планарность
как доказать, что стягивание ребра планарного графы приводит к планарному графу...

Графы. Задание на планарность
Добрый день, решите пожалуйста задание, буду примного благодарен)))

Проверить планарность графа
Проверить нужно граф на то, что он планарный или нет (если да, то по...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru