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

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

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

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

fig

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

Задача 3. Да се намерят всички пътища в даден граф, които имат дължина k.

Last modified: Saturday, 12 November 2011, 5:38 PM