IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Правильность построения графа.
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 4
Пол: Женский

Репутация: -  0  +


Всем доброго времени суток smile.gif мне нужна помощь по одной задачке, у самой не получается...

Нам дана матрица смежности n*n (n - количество врешин в графе.) Если путь из i в j есть, то массив[i,j]=1 и массив[j,i]=1, если нет - то 0. Как мне по такой вот матрице проверить правильность построения графа, то есть чтобы обязательно был хотя бы один путь из 1 в n вершину. ( граф НЕ обязательно должен быть связным, т е не обязательно, чтобы был путь из каждой вершины в каждую).

Заранее спасибо за помощь.

Сообщение отредактировано: mamba -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 7)
сообщение
Сообщение #2





Группа: Пользователи
Сообщений: 4
Пол: Женский

Репутация: -  0  +


и я не прошу текста, сама справлюсь, просто у меня что то даже идей нету. Ну они есть, но неправильные) очень прошу помочь)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(mamba @ 28.11.2007 21:36) *
чтобы обязательно был хотя бы один путь из 1 в n вершину. ( граф НЕ обязательно должен быть связным, т е не обязательно, чтобы был путь из каждой вершины в каждую).
Погоди.. Если из вершины 1 можно попасть в любую другую - не значит ли это, что он связный? Ведь из любой можно попасть в 1-ую, а потом в любую другую. Разве не так?..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(mamba @ 28.11.2007 22:02) *

не прошу текста, сама справлюсь, просто у меня что то даже идей нету.

Хм.. Я уважаю такой подход, но программеру проще накатать текст, чем объяснять.. smile.gif
Сначала я пытался найти простой признак (типа суммировать как-нить элементы), но потом оставил попытки и сделал в лоб.
Процесс рекурсивный.
Сначала множество InReach (Доступные) пусто.
Берем первую вершину, от которой мы отталкиваемся (в данном случае - первую), добавляем ее к множеству InReach и проходим по строке с ее номером. Если встречаем связь с вершиной, которая еще не в числе доступных - прыгаем на эту вершину и делаем с ней то же самое (рекурсия).
В результате множество InReach содержит все вершины, доступные из первой. Если оно содержит все вершины графа, то ответ на вопрос задания положительный, если нет - то отрицательный smile.gif.

Данная реализация использует множества и поэтому ограничена по количеству вершин графа числом 255. Это можно обойти при желании..

Вот, что получилось:
const
m=100;

var
Link: array[1..m,1..m]of byte;
InReach: set of byte;
v,i,j,k,n: byte;
AllReached: boolean;
f: text;

procedure Reached(v:byte);
var
i: byte;
begin
Include(InReach,v);
for i:=1 to n do begin
if (Link[v,i]=1) and not (i in InReach) then Reached(i)
end;
end;

begin
{Reading File}
Assign(f,'mamba.txt');
Reset(f);
ReadLn(f,n);
for i:=1 to n-1 do begin
for j:=i+1 to n do begin
Read(f,Link[i,j]);
Link[j,i]:=Link[i,j]
end;
ReadLn(f)
end;
Close(f);

{Printing the Matrix}
for i:=1 to n do begin
for j:=1 to n do Write(Link[i,j]:2);
WriteLn
end;

{Work}
InReach:=[];
Reached(1);

{Pribting the result}
AllReached:=true;
for i:=1 to n do AllReached:=AllReached and (i in InReach);
if AllReached then WriteLn('All verteces are in reach') else WriteLn('Some vertices are unreachable');
ReadLn
end.

В качестве входных данных используется файл mamba.txt, в котором сначала идет число вершин в графе, а потом верхняя половинка матрицы (без главной диагонали). Вот пример входного файла для графа из 6 вершин:
6
1 1 0 1 0
0 1 0 0
0 0 0
0 0
0

Для этой матрицы ответ отрицательный.

PS
Мне по-прежнему кажется, что более простой признак должен существовать.. Кто-нить знает его?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






из 1 в n - то есть из первой в последнюю.Просто,чтобы можно было попасть, пусть за несколько переходов. Т.е у нас, допустим, 4 вершины. есть пути 1--2 и 3--4. Нельзя попасть из 1ой в четвертую никак. А если бы было 1--2 2--3 3--4, то видно, что можно. Вот пытаюсь сделать проверку.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






В результате множество InReach содержит все вершины, доступные из первой. Если оно содержит все вершины графа, то ответ на вопрос задания положительный, если нет - то отрицательный
Цитата
В результате множество InReach содержит все вершины, доступные из первой. Если оно содержит все вершины графа, то ответ на вопрос задания положительный, если нет - то отрицательный


о, мне просто надо изменить, чтобы проверка шла не на содержание множеством всех вершин, а на содержание вершины n. (например 6)... *пошла думать =))
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


mamba, это ты? забыла пароль? выслать?

Цитата(Гость @ 29.11.2007 14:56) *
о, мне просто надо изменить, чтобы проверка шла не на содержание множеством всех вершин, а на содержание вершины n. (например 6)... *пошла думать =))
Да, именно так. Странно, почему-то я понял так, что тебе нужно в каждую.. глюки, извини. Если просто одну n-ную (ага, понял.. ты не пишешь окончания - видимо, "для краткости" - и я просто взял не ту форму от n) вершину - нет проблем. Просто последнюю группу операторов нужно заменить примерно на следующее:

if n in InReach then WriteLn('Connected!') else WriteLn('Disconnected..');

Все.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8





Группа: Пользователи
Сообщений: 4
Пол: Женский

Репутация: -  0  +


Огромное спасибо! rolleyes.gif

З.Ы: да,забыла, но уже вспомнила =)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 21.10.2020 14:28
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name