Реферат: Aлгоритмы на графах

– повторяем процесс для вершины и т.д.

Для окончания доказательства (и построения алгоритма) заметим, что база индукции очевидна: если ребро одно, то оно – петля.

Хотя доказательство проведено для неориентированных графов, оно сразу переносится на ориентированные, только требование четности заменяется теперь на такое: число входящих в каждую вершину ребер должно быть равно числу выходящих.

Осталось заметить, что предложенный в доказательстве алгоритм линеен, т.е. число действий прямо пропорционально числу ребер.

Program Euler;

const n=9;

m: array[1..n, 1..n] of boolean=

(

(False, True, True, False, False, False, False, False, False),

(True, False, True, False, False, False, True, True, False),

(True, True, False, True, True, False, False, False, False),

(False, False, True, False, True, False, False, False, False),

(False, False, True, True, False, True, False, True, False),

(False, False, False, False, True, False, True, True, True ),

(False, True, False, False, False, True, False, True, True ),

(False, True, False, False, True, True, True, False, False),

(False, False, False, False, False, True, True, False, False)

);

Type

list=^node;

node=record

i: integer;

next: list

end;

Var stack1, stack2: list;

v, u, x, i: integer;

Procedure Push(x: integer; var stack: list);

Var temp: list;

Begin