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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
zhenik9
0 / 0 / 0
Регистрация: 29.09.2012
Сообщений: 23
#1

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

24.04.2013, 22:08. Просмотров 1196. Ответов 2
Метки нет (Все метки)

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

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4949 / 3025 / 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     Теория графов
Ответ Создать тему
Опции темы

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