dimaniac
Удален
|
    
Ну извините, не спец я по графам.
Дано дерево. Пусть мы нашли самую длинную цепь в этом дереве. Взяли от балды любую вершину. Нашли самую длинную цепь в дереве, начинающуюся в этой вершине.
Вопрос: эта цепь всегда будет заканчиватся в 1-м из концов 1-й цепи?
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 26 апр. 2005 8:02 | IP
|
|
Guest
Новичок
|
Нет, не всегда. Но всегда будет заканчиваться в одной из концевых точек одной из самых длинных цепей. Это следует из хорошо известного неравенства в деревьях:
ab+cd<=max{ac+bd,ad+bc}, где через xy обозначено расстояние между вершинами x и y.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 29 апр. 2005 3:28 | IP
|
|
dimaniac
Удален
|
Цитата: Guest написал 29 апр. 2005 3:28
Но всегда будет заканчиваться в одной из концевых точек одной из самых длинных цепей.
Но длина-то этих самых длинны цепей будет одинакова? То есть мне нужно найти длину самой длинной цепи. Из произвольной точки скажем методом волны находим одну из концевых вершин одной из самых длинных цепей. Из нее снова пускаем волну и определяем максимальную длину в дереве. Правильно? Я знаю другой способ с помощью динамического программирования, но волной кажется попроще если конечно все верно.
(Сообщение отредактировал dimaniac 29 апр. 2005 13:13)
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 29 апр. 2005 13:03 | IP
|
|
Guest
Новичок
|
Не понял вопроса.
Давайте примем такие определения: "диаметр" - это самая длинная цепь в графе. Тогда длины всех диаметров равны по определению; "радиус из точки" - это самая длинная цепь выходящая из данной точки. Тогда длины всех радиусов из данной точки равны по определению. Мы доказали, что конец любого радиуса есть конец некоторого диаметра. Что еще нужно?
Из произвольной точки скажем методом волны находим одну из концевых вершин одной из самых длинных цепей. Из нее снова пускаем волну и определяем максимальную длину в дереве. Правильно?
Не знаю. Что такое "пускаем волну"?
Я знаю другой способ с помощью динамического программирования,
Способ чего?
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 29 апр. 2005 23:05 | IP
|
|
dimaniac
Удален
|
Сразу видно, что ты не программист. Вообще-то это все программисткие термины. Динамическое программирование из исследования операций и очень широко применяется в программировании. Если интересно можешь почитать Беллмана "Динамическое программирование". Метод волны = поиск в ширину см любую книгу по алгоритмам на графах. В конечном счете ты все-таки ответил на мой вопрос. Спасибо.
(Сообщение отредактировал dimaniac 30 апр. 2005 15:34)
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 30 апр. 2005 10:33 | IP
|
|
Guest
Новичок
|
Вот так вот людям помогать: сам же нерюхом и оказался! ))))
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 10 марта 2008 4:37 | IP
|
|
Форум
Теория графов
