Функционално програмиране 2009/2010

Граф се задава с асоциативен списък, където ключ е връх в графа, а стойност е списък от неговите преки наследници (деца).

Локални задачи

1. Да се напише функция (children v g), която по намира децата на v в g.
2. Да се напише функция (parents v g), която по намира роителите на v в g.
3. Да се напише функция (oriented? g), която проверява дали един граф е ориентиран. Графът е неориентиран ако за всяка дъга x->y има дъга y->x.

Търсене на път

1. Да се напише функция (extend path g), която по даден път path в g (записан за удобство наобратно, от последния възел към първия) намира всички пътища, които разширяват path с една стъпка в графа.
2. Да се напише функция (succ-n n v g), която намира всички върхове, които могат да се достигнат с точно n стъпки от v.
• Използва се extend
• Задачата може да се реши и с repeated
3. Да се напише функция (paths-n n v g), която намира всички ациклични пътища с дължина n от v.
4. Да се напише функция (paths-acyclic v g), която намира всички ациклични пътища от v.
5. Да се напише функция (paths-acyclic -all v g), която намира всички ациклични пътища в графа.
6. Да се напише функция (hamilton? g), която проверява дали един граф е Хамилтонов, т.е. дали съдържа Хамилтонов път (път минаващ през всички върхове на графа точно по веднъж).
7. Да се напише функция (longest-cycle g), която намира най-дългия прост цикъл в графа g.