Графы

@Dunis · Регистрация: 03.07.2010

Студворк — интернет-сервис помощи студентам

Проверить является ли граф максимально связным.
На языке С.

@el Gato Estelar · 19.07.2010, 09:32

мм..максимально связность -- это определить 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 - число компонент связности.

@Dunis · 19.07.2010, 09:37 **[ТС]**

максимально связным - это проверить доступность из любой вершины в любую...

@el Gato Estelar · 19.07.2010, 09:40

ну это и означает, что в графе только одна компонента связности. Проверь число iCurColor на равенство с 1, если верно -> граф максимально связный

@M128K145 · 19.07.2010, 13:35

Dunis, собственно можно рассматривать эту задачу как раскрашивание вершин графа. Если количество цветов необходимых для раскрашивания равно количеству вершин - то граф максимально связный

@el Gato Estelar · 19.07.2010, 13:38

M128K145, вы вероятно путаете "односвязный" и "полный". ваше утверждение будет верно только в случае полного графа.
пример: N=4
связи: 1-2, 1-3, 1-4. Граф - односвязный. Но можно покрасить в два цвета.

Или путаю я? "проверить доступность из любой вершины в любую" -- за один переход или это не обязательно?

@M128K145 · 19.07.2010, 13:50

Сообщение от el Gato Estelar

Или путаю я? "проверить доступность из любой вершины в любую" -- за один переход или это не обязательно?

Я трактовал это как за один переход, поэтому ждем ТС

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/

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

	Графы 17.07.2010, 18:07. Показов 1343. Ответов 6 Метки нет (Все метки) Проверить является ли граф максимально связным. На языке С. 0

@Dunis 0 / 0 / 0 Регистрация: 03.07.2010 Сообщений: 3
	19.07.2010, 09:37 [ТС]
	максимально связным - это проверить доступность из любой вершины в любую... 0

@el Gato Estelar 9 / 9 / 1 Регистрация: 26.05.2010 Сообщений: 36
	19.07.2010, 09:40
	ну это и означает, что в графе только одна компонента связности. Проверь число iCurColor на равенство с 1, если верно -> граф максимально связный 0

@M128K145 8384 / 3617 / 419 Регистрация: 03.07.2009 Сообщений: 10,709
	19.07.2010, 13:35
	Dunis, собственно можно рассматривать эту задачу как раскрашивание вершин графа. Если количество цветов необходимых для раскрашивания равно количеству вершин - то граф максимально связный 0

@el Gato Estelar 9 / 9 / 1 Регистрация: 26.05.2010 Сообщений: 36
	19.07.2010, 13:38
	M128K145, вы вероятно путаете "односвязный" и "полный". ваше утверждение будет верно только в случае полного графа. пример: N=4 связи: 1-2, 1-3, 1-4. Граф - односвязный. Но можно покрасить в два цвета. Или путаю я? "проверить доступность из любой вершины в любую" -- за один переход или это не обязательно? 0