Elemente de combinatorica. Teoria grafurilor

Am vazut ca notiunea de graf neorientat are o larga aplicabilitate in probleme ce permit reprezentari prin puncte si segmente care unesc o parte dintre aceste puncte (orase si drumurile dintre ele, persoane si legaturi intre acestea etc.)

Exista insa si situatii in care legaturile dintre elemente nu sunt neaparat reciproce. De exemplu, sa consideram relatiile de simpatie dintre n persoane: persoana x simpatizeaza pe persoana y ceea ce nu inseamna neaparat ca persoana y simpatizeaza, la randul ei, pe persoana x. Astfel de legaturi nu pot fi reprezentate prin intermediul unui graf neorientat, deoarece intr-un graf neorientat nu se face distinctie intre muchiile [x,y] si [y,x]. In astfel de cazuri vom folosi notiunea de graf orientat.