Grafuri neorientate

1.  Noțiunea de graf neorientat

Definiție:

Se numește graf neorientat o pereche ordonată de mulțimi notată G=(V,M) unde:

V : este o mulțime finită și nevidă, ale cărei elemente se numesc noduri sau vârfuri;

M : este o mulțime, de perechi neordonate de elemente distincte din V, ale cărei elemente se numesc muchii.

Exemplu de graf neorientat:

G=(V,M) unde: V={1,2,3,4} și M={{1,2},{2,3},{1,4}}

Demonstratie:

Perechea G este graf neorientat deoarece respect definiția prezentată mai sus, adică:

V : este finită si nevidă;

M : este o mulțime de perechi neordonate (submulțimi cu două elemente) de elemente din V.

În continuare, vom nota submulțimea {x,y}, care reprezintă o muchie, cu [x,y] (într-un graf neorientat muchia [x,y] este aceeasi cu muchia [y,x]).

În baza celor spuse anterior, graful prezentat în exemplul de mai sus se reprezintă textual astfel:

G=(V,M) unde: V={1,2,3,4}

M={[1,2],[2,3],[1,4]}

În teoria grafurilor neorientate, se întâlnesc frecvent notiunile:

• extremitățile unei muchii
• fiind dată muchia m=[x,y], se numesc extremități ale sale nodurile x și y;
• vârfuri adiacente
• dacă într-un graf există muchia m=[x,y], se spune despre nodurile x și y că sunt adiacente;
• incidentă
• dacă m1 și m2 sunt două muchii ale aceluiași graf, se numesc incidente dacă au o extremitate comună

Exemplu:

m1=[x,y] și m2=[y,z] sunt incidente.

Dacă m=[x,y] este o muchie într-un graf, se spune despre ea și nodul x, sau nodul y, că sunt incidente.

Reprezentarea unui graf neorientat admite două forme, și anume:

• reprezentare textuală: așa cum s-a reprezentat graful din exemplul anterior;
• reprezentare grafică: muchiile sunt reprezentate prin linii, iar nodurile prin puncte.

Exemplu de graf neorientat reprezentat textual:

G=(V,M) unde: V={1,2,3,4}

M={[1,2],[2,3],[1,4]}