Grafuri

În problemele următoare, dacă nu se precizează altfel, presupunem că grafurile sunt reprezentate ca dicționar cu chei noduri și liste de adiacență. În grafuri neorientate, muchia (u, v) se presupune reprezentată cu v în lista lui u și u în lista lui v.

1. Traversări La curs am scris parcurgerea în adâncime pentru un graf reprezentat cu o listă de vecini la fiecare nod, și parcurgerea prin cuprindere cu vecinii reprezentați ca mulțime. Adaptați aceste parcurgeri:

2. E ciclic graful? 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.

3. 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.

4. 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).

5. 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.


Marius Minea
Last modified: Wed Dec 21 19:00:00 EET 2016