Форум программистов, компьютерный форум CyberForum.ru

Теория графов - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
zhenik9
0 / 0 / 0
Регистрация: 29.09.2012
Сообщений: 23
24.04.2013, 22:08     Теория графов #1
Есть задание. найти максимальное и среднее расстояние между центральными вершинами неориентированного графа.
1 Что такое центральные вершины? если не сложно объясните алгоритм их нахождения
2 что такое расстояние и в частности среднее расстояние?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.04.2013, 22:08     Теория графов
Посмотрите здесь:

Реализация графов C++
C++ алгоритм Флойда (теория графов).
Реализация алгоритмов теории графов на С/С++ C++
генерирование особых графов C++
Теорие графов. Композиция двух неор. графов. C++
Программирование графов C++
C++ Визуализация графов
C++ Для любителей графов

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
29.04.2013, 12:10     Теория графов #2
1, 2: http://vuz.exponenta.ru/PDF/L14.html (первая ссылка в гугле по запросу "центральные вершины графа").
3: Каким боком это к С++?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
29.04.2013, 17:49     Теория графов #3
zhenik9, используйте алгоритм поиска кратчайших путей. Находите самый короткий путь м\д вершинами v1 | v2
Затем используете тот же алгоритм, но только, при релаксации берите не min() а max() и тогда найдёте самый длинный путь, среднее расстояние и будет полусумма кратчайшего пути и самого длинного. Учтите, путь должен быть простым, иначе максимальное расстояние -- бесконечность

Добавлено через 1 час 44 минуты
Назовем центром графа такую вершину, что наибольшее расстояние от нее до любой другой вершины наименьшее.
Yandex
Объявления
29.04.2013, 17:49     Теория графов
Ответ Создать тему
Опции темы

Текущее время: 01:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru