Функционално програмиране (КН 2011/12)

(Ориентиран) Граф се представя със списък от спицъци от наследници. Например: ((1 2 3) (2 3) (3 4) (4 1)) представя графа

1. Да се напише функция (succs graph), която намира наследниците на даден възел в граф. Внимавайте за цикли!
2. Да се напише функция (oriented? graph), която проверява дали даден граф е наистина ориентиран. Един граф е неориентиран, ако за всяко ребро (v_i,v_j) съществува и обратното ребро (v_j,v_i). Графът е ориентиран, ако има ребро, което няма съответно обратно.
3. Да се напише функция (extend path graph), която намира всички възможни разширения на пътя path с едно ребро.
4. Да се напише функция (paths-from node graph k), която намира всички пътища от node с дължина k.
5. Да се напише функция (acyclic-paths-from node graph k), която намира всички ациклични пътища от node с дължина k. Упътване: добавете filter на подходящо място в extend.
6. Да се напише функция (acyclic-from node graph), която намира всички ациклични пътища започващи от възела node в граф. Упътване: ако използвате предната функция, решението няма да е ефективно. Измислете итеративно решение.
7. Да се напише функция (acyclic-from-to node1 node2 graph), която намира всички ациклични пътища от node1 до node2 в граф.
8. Да се напише функция (acyclic graph), която намира всички ациклични пътища в граф.