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

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

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

 
 Ответить  Открыть новую тему 
> Найти дополнение графа, (ч/з структуру Вирта)
сообщение
Сообщение #1


Пионер
**

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

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


Здравствуйте.
Получила такое задание:

Дополнение G~ графа G имеет в качестве множества вершин множество V(G), две вершины в G~ смежны тогда и только тогда, когда они не смежны в G. Постройте дополнение заданного графа G.

Граф необходимо задать через структуру Вирта.
У меня получилась вот такая структура:
type
Lref = ^Leader; { Тип: указатель на заголовочный узел}
Tref = ^Trailer; { Тип: указатель на дуговой узел}
{ Описание типа заголовочного узла }
Leader = Record
Key : Integer; { Имя заголовочного узла}
Count: Integer; { Количество предшественников}
Trail: Tref; { Указатель на список смежности }
Next : Lref { Указатель на следующий узел в списке заголовочных узлов }
end;
{ Описание типа дугового узла }
Trailer = Record
Id : Lref; { Указатель на узел списка заголовочных узлов}
Next: Tref { Указатель на следующий узел списка смежности }
end;


Строила её по методичке, но как ею пользоваться и как найти дополнение графа не совсем понимаю.
Подскажите, пожалуйста, в каком напрвлении двигаться. Надо ли использовать обходы графов?

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Насчет как ей пользоваться - см. здесь: http://ric.uni-altai.ru/Fundamental/pascal3/lab3/prim3-3.htm

Цитата
Надо ли использовать обходы графов?
Я бы не использовал никакие обходы... Есть более простое решение: тебе же известно количество вершин в графе? Вот напиши функцию HasConnection(), которая будет проверять, есть ли связь между вершиной A и вершиной B примерно вот таким образом:

function HasConnection(Head: LRef; A, B: integer): boolean;
var p: TRef;
begin
HasConnection := True;

while (Head <> nil) and (Head^.Key <> A) do Head := Head^.next;
{ Теперь параметр Head указывает на данные о вершине А }
p := Head^.Trail;
while (p <> nil) do begin

if (p^.ID <> nil) and (p^.ID^.Key = B) then Exit
else p := p^.next;

end;
HasConnection := False;
end;
, а уж с ее помощью и с помощью информации по ссылке - очень просто построить дополнение. Заголовочные узлы - те же, что и в исходном графе, а насчет списков смежности - проще сделать перебор всех вершин:

for i := 1 to Count do
for j := 1 to i - 1 do
{ проверяем наличие связи или i -> j или j -> i }
if HasConnection(Head, i, j) or HasConnection(Head, j, i) then { ничего не делать }
else { добавить в Дополнение дугу i -> j, поскольку в графе ее нет }

Набирал прямо здесь, могут быть опечатки, но идея должна быть понятна...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

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

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


volvo, в очередной раз спасибо огромное!!!

Сообщение отредактировано: Triplet -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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