всех каркасов графа
всех каркасов графа G делится на два класса: содержащие выделенное ребро <v,u> и не содержащие. Каркасы последовательно строятся в графах G<v,u> и G-<v,u>. Каждый из графов G<v,u> и G-<v,u> меньше, чем G. Последовательное применение этого шага уменьшает графы до тех пор, пока не будет построен очередной каркас, либо графы станут несвязными и не имеющими каркасов.
Для реализации идеи построения каркасов графа G используются следующие структуры данных:
• очередь - Turn (array[1..N] of integer) с нижним (down) и верхним (up) указателями;
• массив признаков Nnew (см. предыдущее занятие);
• список ребер, образующих каркас - Tree (см. предыдущее занятие);
• число ребер в строящемся каркасе - numb.
Начальное значение переменных:
.....
FillChar(Nnew,SizeOf(Nnew),true);
FillChar(Tree,SizeOf(Tree),0);
Nnew[1]:=false;
{*в очередь заносим первую вершину*}
Turn[1]:=1; down:=1;up:=2; numb:=0;
......
Procedure Solve(v,q:integer);
{*v - номер
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
