всех каркасов графа


всех каркасов графа 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 - номер
Индекс
Элементарные функции    Линейные уравнения    Нелинейные уравнения    Случайные числа


Hosted by uCoz