--------------------------------------------------------------------------
Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, are muchiile [1,2], [2,3], [2,4], [2,5], [4,5], [4,6], [5,6]. Scrieți listele de adiacență ale unui graf parțial al său care să fie conex și fără cicluri.
--------------------------------------------------------------------------
Teorie:
Definiție. Un GRAF PARȚIAL al grafului G=(X,U) este un graf G1=(X,V), astfel încât V⊂U.
Definiție. Se numește CICLU în G un lanț L pentru care xi1 = xik și toate muchiile [xi1,xi2], [xi2,xi3], ..., [xik-1,xik] sunt diferite două câte două.
Definiție. Un GRAF G se numește CONEX dacă pentru oricare două vârfuri x și y diferite ale sale, există un lanț care le leagă.
Definiție. Se numește LANȚ în G succesiunea de vârfuri L=[xi1,xi2,...,xik], cu proprietatea că oricare două vârfuri consecutive din L sunt adiacente, adică [xi1,xi2], [xi2,xi3], ..., [xik-1,xik]aparțin lui U. Vârfurile xi1 și xik se numesc extremitățile lanțului, iar numărul de muchii care apar în L se numește lungimea lanțului L.
--------------------------------------------------------------------------
Din lanțul dat putem elimina muchiile [2,5] și [5,6], în acest fel graful este parțial, conex și fără cicluri. Din eliminarea acestora rezultă...
--------------------------------------------------------------------------
Răspuns:
Liste de adiacență:
vârful i  |  lista Li a vecinilor lui i
-------------------------------------------
1         | 2
2         | 1,3,4
3         | 2
4         | 2,5
5         | 4
6         | 4


