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