| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Graf |
| Автор: PLAKAT 16.11.2002, 22:03 |
| ну вопшем так. ест граф с н вершинами, двуx цветов 1 и 2 например. и ест второи граф с н вцершинами (м<н), с вершинами двуx цветов 1,2. требуеца наити аналог второго графа в первом, то ест что бы у него был то ге число вершин, теми ребрами, теми э цветами как у первого. Я не мог решит ету задачцку за 4 часа. Иза ето не работу не принаяли....[censored 11]  |
| Автор: neutrino 17.11.2002, 19:39 |
| По-моему, кроме перебора (n*m штук) ничего сделать нельзя. Начинаешь с какой-нибудь вершины в первом и втором графе и сравниваешь все вершины (рекурсивно) пока не найдешь различия, потом начинаешь с соседней вершины и т.д. Когда "кончатся" вершины в одном графе, переходишь в другом графе на соседнюю вершину... |
| Автор: PLAKAT 18.11.2002, 21:17 |
| да но если будет 20 вершин, ответа программы могут увидет наши провнуки |
| Автор: AntonSaburov 18.11.2002, 22:14 |
| Ищите ответы: http://algolist.manual.ru/maths/graphs/index.php Хотя странная задачка пр приеме на работу. Что за контора, чем занимается ? |
| Автор: podval 19.11.2002, 04:55 |
| Я думаю, число переборов можно сократить, если графы представить матрицами связности А(n,n) и В(m,m), в которой цвет задать, скажем, знаками (будут 1 и -1). А дальше разбить по определенному правилу матрицу А на матрицы того же размера, что и В. Среди них найти те, которые совпадут с В. |
| Автор: PLAKAT 19.11.2002, 18:08 |
| Я так и сделал, из болшои матрицы я взял все возмогные маленкие матрицы, и сделал сравнение, но сравнение видимо не дастаточно, муген ешё одно условие, но видно времани не xватало, всего 4 часа. |
| Автор: podval 19.11.2002, 18:16 | ||
Что ты имеешь в виду? |