1. Да се напише функция, която проверява дали граф, зададен със списък от насленици е ориентиран или неориентиран, т.е. дали за всяка дъга имаме обратна дъга.
  2. Да се напише функция, която проверява дали даден ориентиран граф е дърво. Примери за непълни критерии:
    • графът да е ацикличен (може да имаме 1 -> 2, 2 -> 3, 1-> 3)
    • всички възли да имат най-много един родител (може да имаме цикъл)
    • всички възли да имат най-много един родител и да има възел без родители (може да имаме гора)
    • всички възли да имат най-много един родител и да има точно един възел без родители (може да имаме 1 -> 2, 3 -> 4, 4 -> 3)
    Правилен критерий е: графът да е ацикличен, всички възли да имат най-много един родител и да има точно един възел без родители
Последно модифициране: събота, 12 ноември 2011, 17:38