1. Graf (a)ciclic Scrieți o funcție care determină dacă un graf neorientat (presupus conex) are cicluri sau nu (returnând un boolean). Adaptați traversarea în adâncime.
2. Distanța între noduri Scrieți o funcție care ia un graf neorientat și două noduri și returnează lungimea celui mai scurt drum între ele (sau generează excepția Not_found dacă nu există). Adaptați parcurgerea prin cuprindere.
3. Diametrul unui graf. Scrieți o funcție care returnează valoarea diametrului unui graf neorientat aciclic. Diametrul unui graf e definit ca distanța maximă între oricare două noduri. (Distanța între două noduri e lungimea drumului minim între ele).
Porniți de la un vârf arbitrar și determinați nodurile la distanță maximă. Apoi, pornind de la unul din acestea, determinați nodul aflat la distanța maximă de el -- această din urmă distanță e diametrul.
Observație: Acest algoritm e corect doar pentru un graf aciclic (puteți încerca să vă gândiți la o demonstrație).
4. Centrul unui graf e definit ca mulțimea nodurilor pentru care distanța maximă până la orice alt nod din graf are valoare minimă. Scrieți o funcție care dat fiind un graf neorientat aciclic determină centrul acestuia (adaptând căutarea după diametru).
Observație: Un graf neorientat aciclic e un arbore. Un arbore are unul sau două centre, după cum diametrul său e par sau impar.