 |
|
|
 
|
|
Graf, poisk grafof v grafe 
| PLAKAT |
|
|||
|
Unregistered |
ну вопшем так.
ест граф с н вершинами, двуx цветов 1 и 2 например. и ест второи граф с н вцершинами (м<н), с вершинами двуx цветов 1,2. требуеца наити аналог второго графа в первом, то ест что бы у него был то ге число вершин, теми ребрами, теми э цветами как у первого. Я не мог решит ету задачцку за 4 часа. Иза ето не работу не принаяли....[censored 11]  |
|||
|
||||
Загрузка ...
| neutrino |
|
|||
 Gothic soul  Профиль Группа: Модератор Сообщений: 3041 Регистрация: 25.3.2002 Где: Верхняя Галилея, Кармиэль Репутация: нет Всего: 62 |
По-моему, кроме перебора (n*m штук) ничего сделать нельзя. Начинаешь с какой-нибудь вершины в первом и втором графе и сравниваешь все вершины (рекурсивно) пока не найдешь различия, потом начинаешь с соседней вершины и т.д. Когда "кончатся" вершины в одном графе, переходишь в другом графе на соседнюю вершину...
-------------------- The truth comes from within ... Покойся с миром, Vit |
|||
|
||||
| PLAKAT |
|
|||
|
Unregistered |
да но если будет 20 вершин, ответа программы могут увидет наши провнуки
|
|||
|
||||
| AntonSaburov |
|
|||
 Штурман Профиль Группа: Модератор Сообщений: 5658 Регистрация: 2.7.2002 Где: Санкт-Петербург Репутация: нет Всего: 118 |
Ищите ответы:
http://algolist.manual.ru/maths/graphs/index.php Хотя странная задачка пр приеме на работу. Что за контора, чем занимается ? |
|||
|
||||
| podval |
|
|||
 Где я? Кто я? Профиль Группа: Экс. модератор Сообщений: 3094 Регистрация: 25.3.2002 Где: СПб Репутация: 18 Всего: 62 |
Я думаю, число переборов можно сократить, если графы представить матрицами связности А(n,n) и В(m,m), в которой цвет задать, скажем, знаками (будут 1 и -1). А дальше разбить по определенному правилу матрицу А на матрицы того же размера, что и В. Среди них найти те, которые совпадут с В.
|
|||
|
||||
| PLAKAT |
|
|||
|
Unregistered |
Я так и сделал, из болшои матрицы я взял все возмогные маленкие матрицы, и сделал
сравнение, но сравнение видимо не дастаточно, муген ешё одно условие, но видно времани не xватало, всего 4 часа. |
|||
|
||||
| podval |
|
|||
|
Где я? Кто я? Профиль Группа: Экс. модератор Сообщений: 3094 Регистрация: 25.3.2002 Где: СПб Репутация: 18 Всего: 62 |
Что ты имеешь в виду? |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0457 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |