Найти дополнение графа, (ч/з структуру Вирта) Опции

[Triplet]

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

Дополнение 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; 

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

[volvo]

Насчет как ей пользоваться - см. здесь: 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]

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

Сообщение отредактировано: Triplet - 10.11.2008 6:01