Процесс Предшествующий процесс Длительность (недели)A: Прочтение рукописи редактором - 3B: Пробная верстка отдельных страниц книги - 2C: Разработка обложки книги - 4D: Подготовка

1. Издатель имеет контракт с автором на издание его книги. Ниже представлена последовательность (упрощенная) процессов, приводящая к реализации проекта издания книги.

Процесс Предшествующий процесс Длительность (недели)A: Прочтение рукописи редактором - 3B: Пробная верстка отдельных страниц книги - 2C: Разработка обложки книги - 4D: Подготовка иллюстраций - 3E: Просмотр автором редакторских правок и сверстанных страниц А,В 2F: Верстка книги (создание макета книги) Е 4G: Проверка автором макета книги F 2H: Проверка автором иллюстраций D 1I: Подготовка печатных форм G,H 2J: Печать и брошюровка книги C,I 4

1. Построить ориентированный граф и матрицу смежности для взвешенного графа (2 балла)
2. Написать программу, вычисляющую по матрице смежности время начала и окончания любой работы (2 балла)

1. Используя приведенные процедуры создать список смежности для заданного графа с помощью динамических структур. Задать веса ребер самостоятельно. Вывести содержимое этого конкретного списка в таком виде, как указано в примера (6 баллов)

Список смежности графов подразумевает, что для каждой вершины будет указан список всех смежных с нею вершин (при необходимости с весами)

Пример:

a: b 1 c 10

b: a 1 c 2 d 10

c: a 10 d 3

d: b 10 c 3

Представление типов данных

Type refnode=^node;

refarc=^arc;

node= record {список вершин}

id:integer; {номер вершины}

infnode:integer; {вес}

next:refnode; {указатель на следующую вершину в списке}

arclist:refarc {указатель на список дуг}

end;

arc= record {список дуг определенной вершины}

infarc:integer; {вес}

next:refarc; {указатель на следующую дугу, исходящую из данной вершины}

adj [1]:refnode {указатель на вершину, в которую ведет данная дуга}

end;

В универсальном динамическом представлении используется линейный список. Для любой вершины можно хранить ее вес.

Например, для графа следующего вида

типы данных для представления графов:

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;

Добавление вершины

Процедура AddNode добавляет в граф вершину с заданным номером n и весом x. Предполагается, что уникальность номера обеспечивается вызывающей программой.

Procedure AddNode(Var graph: refnode; n,x:integer);

Var p:refnode;

Begin new(p);

With p^ do

Begin id:=n;

Infnode:=x;

Arclist:=nil;

Next:graph

End;

graph:=p;

end;

Добавление дуги

Процедура добавления дуги AddArc в граф использует в качестве входной информации ссылки на соединяемые вершины и значения вес создаваемой дуги. Обе вершины должны существовать к моменту выполнения процедуры.

Procedure AddArc(u,v:refnode; y:integer);

Var a:refarc;

Beginif u=nil or v=nil then writeln(‘Отсутствует вершина’)

Elsebegin

New(a);

With a^ do begin

Infarc:=y;

Adj:=v;

Next:=u^.arclist

End;

u^.arclist:=a

end

end;

[1] от adjacency – смежность

Дата добавления: 2015-10-21