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

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

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

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

fig

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

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

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