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

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

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

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

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

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

Алгоритм Флойда (теория графов) - C++
код: int** floid(int** W,int n){ vector<int**>D(n); int** A=new int*; for(int i=0;i<n;i++){ A=new int; for(int...

Теория графов. Задача Обрати меня! - C++
Мальчик Вася очень любит разворачивать ориентированные графы. Помогите ему в этом. Входные данные Во входном файле записано число N...

Теорие графов. Композиция двух неор. графов. - C++
Здравствуйте. Прошу помощи уже здесь :| (old topic)... Прошу помочь с составлением алгоритма "Композиции двух неориентированных графов". ...

Представление графов С++ - C++
#include <iostream> #include <vector> using namespace std; int n; int m; vector<int> *adj; vector<bool>...

Реализация графов - C++
Помогите пожалуйста!!!!! как написать программу на Си ++ на эту тему :реализация различных типов графов и операций над ними. спасибо...

Представление графов С++ - C++
Считывания графу из входного файла. На вход подается текстовый файл следующего вида: n m v1 u1 v2 u2 .... vm um

Программирование графов - C++
Неподскажите сайт где очень понятно объясняют графы, как запрограммировать, и т.д. Просто гуглил но чо то мне не понравилось то, что он...

Визуализация графов - C++
В общем есть такой пакет http://ru.wikipedia.org/wiki/Graphviz С помощью него можно вводить граф ввиде dot файла и получать её...

Для любителей графов - C++
Иван Иванович любит ходить на скачки, надеясь на них заработать кругленькую сумму. Ему приглянулась лошадь с номером K, и он решил...

Методы обхода графов - C++
Всем привет! Есть задание : Обойти граф, используя заданный алгоритм ( Обход в глубину по матрице инцидентности ). Все что касается...

Генерирование особых графов - C++
кто может привести какой-либо тест(пример в текстовом файле) или алгоритм генерирования тестов для создания произвольного графа с...

Нужна литература по теории графов - C++
у меня курсовая работа идет на основе графов, а мы их не изучали, в теории которую дал препод все запутанно, смотрела в Google тож ничего...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
29.04.2013, 12:10     Теория графов #2
1, 2: http://vuz.exponenta.ru/PDF/L14.html (первая ссылка в гугле по запросу "центральные вершины графа").
3: Каким боком это к С++?
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     Теория графов
Ответ Создать тему
Опции темы

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