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

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

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

 
 Ответить  Открыть новую тему 
> Найти дополнение графа, (ч/з структуру Вирта)
Triplet
сообщение 9.11.2008 19:24
Сообщение #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 
 К началу страницы 
+ Ответить 
volvo
сообщение 9.11.2008 21:19
Сообщение #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, поскольку в графе ее нет }

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


Пионер
**

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

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


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

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

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

 

- Текстовая версия 28.07.2025 3:34
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"