Задача 1. Нека е даден някакъв прост път w в граф. Да се състави функция, която намира множеството от всички прости пътища, които могат да се получат чрез добавяне на връх към w.

При тази задача може да се изпозлва представяне на пътя в стил "стек", т.е. върховете в списъка да са подредени в обратен ред - първият от тях да е последният връх в пътя. Такова представяне улесневя решението както и използването му за долните задачи.

Задача 2. Да се състави процедура, която по дадено множество от прости пътища в граф намира множеството от всички техни едностъпкови развирения.

Нека едностъпково разширение на  w да наречем прост път, който може да се получи чрез добавяне на връх към w.

figure

На фигура 1 е илюстрирана работата на функцията, като на фигура 2 е даден отрязък от графа, върху който тя работи.

Последно модифициране: събота, 12 ноември 2011, 17:38