Двудольный граф, Построить двудольный граф Опции

[Maximus]

Задача:
Нужно создать двудольный граф (то есть задаются начальные вершины и записываются пока без дуг в один граф, потом каким-то образом нужно разделить его с произвольными кол-вами вершин на две доли и соединить дугами каждую вершину одной доли с каждой вершиной другой доли, причем смежные вершины между собой не соединяются дугами).
Вот динамическая структура, которая должна использоваться:

Код

type refnode=^node;
refarc=^arc;
node=record
id: integer; // номер(идентификатор) вершины
infnode: integer; //вес вершины, не обязательно!
next: refnode; //ссылка на след. вершину
arclist: refarc //ссылка на дуги
end;
arc=record
infarc: integer; //вес дуги, это тоже не обязательно юзать!
next: refarc; //ссылка на след. дугу
adj: refnode //ссылка не след. вершину
end;

Помогите! Напишите процедуру разделения графа на две доли(как бы на два подграфа) и поцедуру соединения вершин долей!

Сообщение отредактировано: volvo - 22.01.2005 20:51

[Maximus]

Поясняю из теории "Дискретной математики":
Двудольный граф - это граф, множество вершин которого можно разбить на две части(доли) так, что вершины из одной доли не смежно между собой.
Не смежны - то есть не соединены дугой! Смежность - соединённость! Вот!
То бишь к примеру: 4 вершины в левой доли, 3 в правой
1,2,3,4 - между собой не соединяются
5,6,7 - между собой не соединяются
1* *5
2* *6
3* *7
4*
Результат должен быть такой:
1 вершина соединяется с : 5,6,7
2 вершина соединяется с : 5,6,7
3 вершина соединяется с : 5,6,7
4 вершина соединяется с : 5,6,7
5 вершина соединяется с : 1,2,3,4
6 вершина соединяется с : 1,2,3,4
7 вершина соединяется с : 1,2,3,4
Короче нужно грузить примерно из такого текстового файла ВЕС вершин из каждой доли:
к примеру input.txt:
---------------------------------------------
| 5 10 8 - 1 доля
| 3 12 9 18 - 2 доля
|
|
|
1) Либо создать два графа (как бы доли) и вставить вершины из 1 строки и 2ой
2) Либо есть просто файл, где перечислены весы каждой вершины в одну строку. И нужно создать один граф и вставить вершины, а потом как-то разбить на два графа, ну и затем связать вершины двух разных графов.
Коды процедур ниже:
{Graph} - заголовки для процедур.

Код

procedure Add_Node_To_Graph(var graph: refnode; n,x: integer);
procedure Add_Arc_To_Graph(p1,p2: refnode);
function Find_Node_In_Graph(graph: refnode; x: integer): refnode;
function Find_Arcs_In_Graph(graph: refnode; x: integer): alist;
procedure Delete_Node_In_Graph(var graph: refnode; var p: refnode);
procedure Delete_Arc_In_Graph(u,v: refnode);
procedure Destroy_Graph(graph: refnode);
procedure Browse_D_Graph(graph: refnode);
Procedure Browse_Graph2(graph:refnode);
procedure Print_Graph(var graph: refnode; l,k,y:integer);[/b]

Вот пока 3 процедуры, если что-то еще нужно из верхнего списка, запостю.

Код

procedure Add_Node_To_Graph;
var p,q: refnode;
begin
 new(p);
 p^.id:=n;
 p^.infnode:=x;
 p^.arclist:=nil;
 p^.next:=graph;
 graph:=p;
end;

procedure Add_Arc_To_Graph;
var a: refarc;
begin
 begin
   if (p1=nil) or (p2=nil) then writeln('Error: Node is empty!')
     else
       begin
         new(a);
         {a^.infarc:=x;}
         a^.adj:=p2;
         a^.next:=p1^.arclist;
         p1^.arclist:=a;
       end;
 end;
end;
{...}
procedure Browse_D_Graph;
var a: refarc; nc,na: integer;
begin
 nc:=0; na:=0;
 while graph<>nil do
   begin
     writeln('Node #',graph^.id);
     writeln('List of arcs:');
     a:=graph^.arclist;
     {if a=nil then write('Empty!');}
     while a<>nil do
       if (a^.adj)^.id=0 then a:=a^.next
         else
           begin
             writeln('Arc to Node #',(a^.adj)^.id);
             a:=a^.next
           end;
     {writeln;}
     nc:=nc+1;
     graph:=graph^.next;
   end;
 na:=(nc div 2)*(nc-(nc div 2));
 writeln('Graph have: ',nc,' - nodes; ',na,' - arcs');
end;

Естли кто хочет взяться в серъёз, вот моя ася (304592952) - чтобы быстрей всё уяснить и думать вместе on-line (я почти круглые сутки в инете). Sorry, если я слишком наглею

Сообщение отредактировано: APAL - 2.08.2004 14:14