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

Граф
  1. Да се напише функция (succs graph), която намира наследниците на даден възел в графа
  2. Да се напише функция (oriented? graph), която проверява дали даден граф е наистина ориентиран. Един граф е неориентиран, ако за всяко ребро (vi,vj) съществува и обратното ребро (vj,vi). Графът е ориентиран, ако има ребро, което няма съответно обратно.
  3. Да се напише функция (paths node k graph), която намира списък от всички пътища от възела node, които са с дължина точно k.
    1. Напшете функция (extend path graph), която намира списък от всички пътища, които са с дължина точно 1 възел по-голяма от path и се получават с добавяне на всички възможни наследници на последния връх в пътя. За улеснение пътят може да е в обратен ред. Решете задачата с помощта на рекурсия по k и функцията extend
    2. Наришете функция (extend-all paths graph), която прилага функцията extend над всички пътища в списъка paths. Покажете как може да се реши задачата с помощта на функцията от по-висок ред repeated
    3. Променете решението така че да намира всички ациклични пътища с дължина k започващи от възела node.

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