0 / 0 / 0
Регистрация: 03.07.2010
Сообщений: 3
1

Графы

17.07.2010, 18:07. Показов 1209. Ответов 6
Метки нет (Все метки)

Проверить является ли граф максимально связным.
На языке С.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.07.2010, 18:07
Ответы с готовыми решениями:

Графы
Помогите!!!:help: Очень срочно надо сделать на visual C++!!! :cry: 1.нарисовать произвольный граф...

Графы в С++
Как можно в программу на С++ ввести граф??моей задачей является определить оптимальное расположение...

Графы
Помогите! Не могу решить последние 3 задачи! Не в ладах я с алгоритмами!

Графы
Где можно почитать, как решать графы на pascal?

6
9 / 9 / 1
Регистрация: 26.05.2010
Сообщений: 36
19.07.2010, 09:32 2
мм..максимально связность -- это определить 1 компонента связности или нет? (гугл такого определения не знает, я тоже вспомнить не могу). Если задача в этом -- можно решать например через поиск в глубину(dfs), храня граф матрицой смежности, т.е.
пусть m[N][N] - м.с. для графа, v[N] - вектор(массив) вершин, первоначально заполненный 0
C++
1
2
3
4
5
6
7
8
9
10
/** 
реализует обход в глубину из вершины iStartVertex, помечая вершины цветом iColor
**/
void dfs(int iStartVertex, int iColor); 
....
int iCurColor = 0;
for(int i=0; i<N; i++) {
 if (!v[i])
  dfs(i, ++iCurColor);
}
собственно, iCurColor - число компонент связности.
0
0 / 0 / 0
Регистрация: 03.07.2010
Сообщений: 3
19.07.2010, 09:37  [ТС] 3
максимально связным - это проверить доступность из любой вершины в любую...
0
9 / 9 / 1
Регистрация: 26.05.2010
Сообщений: 36
19.07.2010, 09:40 4
ну это и означает, что в графе только одна компонента связности. Проверь число iCurColor на равенство с 1, если верно -> граф максимально связный
0
Эксперт JavaЭксперт С++
8373 / 3595 / 419
Регистрация: 03.07.2009
Сообщений: 10,708
19.07.2010, 13:35 5
Dunis, собственно можно рассматривать эту задачу как раскрашивание вершин графа. Если количество цветов необходимых для раскрашивания равно количеству вершин - то граф максимально связный
0
9 / 9 / 1
Регистрация: 26.05.2010
Сообщений: 36
19.07.2010, 13:38 6
M128K145, вы вероятно путаете "односвязный" и "полный". ваше утверждение будет верно только в случае полного графа.
пример: N=4
связи: 1-2, 1-3, 1-4. Граф - односвязный. Но можно покрасить в два цвета.

Или путаю я? "проверить доступность из любой вершины в любую" -- за один переход или это не обязательно?
0
Эксперт JavaЭксперт С++
8373 / 3595 / 419
Регистрация: 03.07.2009
Сообщений: 10,708
19.07.2010, 13:50 7
Цитата Сообщение от el Gato Estelar Посмотреть сообщение
Или путаю я? "проверить доступность из любой вершины в любую" -- за один переход или это не обязательно?
Я трактовал это как за один переход, поэтому ждем ТС
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.07.2010, 13:50
Помогаю со студенческими работами здесь

Графы
1) Построить граф, используя язык С++ (или Си), согласно данной схеме на рис.1. 2) По запросу...

Графы
Подскажите,пожалуйста, с помощью чего в python можно визуально представить граф? Делал с помощью...

Графы
Задача звучит так: Задано N городов c номерами от 1 до N и сеть из M дорог с односторонним...

Графы
Задача на графы: На олимпиаду прибыло N человек. Некоторые из них знакомы между собой. Можно ли...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru