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