Grafuri Celebre

1. Introducere

Numeroase situatii din viata cotidiana pot fi modelate cu ajutorul teoriei grafurilor.

Teoria grafurilor este o importanta aplicatie a combinatoricii matematice în inginerie, informatica chiar si filosofie. Grafurile mai au importanta în chimie (structura benzenului este o structura graf), fizica (modelarea circuitelor electrice si a legilor lui Kirchoff), industrie (rezolvarea problemei transportului pe rute minime), informatica (transferul pachetelor pe Internet).

Exista doua mari categorii de grafuri: grafuri orientate si grafuri neorientate. Cu ajutorul unui graf neorientat putem modela o relatie simetrica între elementele unui multimi, în timp ce cu ajutorul unui graf orientat modelam o relatie care nu este simetrica.

Pentru o mai buna întelegere a notiunii de graf se utilizeaza o reprezentare vizuala descrisa astfel:

- fiecarui vârf din graf îi corespunde un punct în plan, în dreptul caruia este specificat numarul vârfului;

- daca graful este orientat, vom reprezenta fiecare arc ca o sageata dinspre extremitatea initiala câtre extremitatea finala a arcului;

- daca graful este neorientat, vom reprezenta fiecare muchie ca o linie (dreapta sau curba) care uneste cele doua extremitati ale muchiei.

Uneori, pentru o mai mare lizibilitate, un vârf se reprezinta ca un cerc sau un patrat în interiorul caruia se specifica numarul vârfului, ori un disc lânga care se specifica numarul vârfului.

Dintre numeroasele grafuri existente, lucrarea de fata evidentiaza acele grafuri “celebre”, prin simplitatea reprezentarii lor grafice, sau prin simetria lor exceptionala, precum si prin proprietatile remarcabile pe care unele grafuri le poseda. Amintim aici, fara a avea pretentia sa le epuizam grafuri ca :

1. Benzen – graf ce simuleaza o structura chimica extrem de cunoscuta;

2. Grafuri complete – grafuri cu proprietatea ca exista un arc între oricare 2 vârfuri ale sale;

3. Grafuri de tip stea – cu aplicatii în dezvoltarea retelelor de calculatoare;

4. Grafuri Petersen – graf K-regulat utilizat ca exemplu sau contraexemplu pentru numeroase aplicatii din teoria grafurilor;

5. Grafuri Euleriene – cu proprietatea ca exista un lant ce trece prin toate muchiile grafului o singura data si revine în vârful de plecare;

6. Grafuri Hamiltoniene – cu proprietatea ca exista un drum ce parcurge toate vârfurile grafului o singura data si revine în vârful de plecare;

2.Suport teoretic

Definitie. Se numeste graf neorientat o pereche ordonata de multimi (X, U), X fiind o multime finita si nevida de elemente numite noduri sau vârfuri, iar U o multime de perechi neordonate ( submultimi cu doua elemente) din X, numite muchii.

Ex.

Fig.1

Pentru graful de mai sus avem:

X={1, 2, 3, 4, 5, 6, 7, 8}

U={[1,2], [1,4], [1,5], [2,3], [2,5], [3,4], [6,7]}

Daca u1 si u2 sunt doua muchii care au o extremitate comuna ele se vor numi adiacente.

Definitie. Un graf partial al grafului G=(X,U) este un graf G1=(X,V) astfel încât VÍU, adica G1 are aceeasi multime de vârfuri ca G iar multimea de muchii V este chiar U sau o submultime a acesteia.

Ex. Mai jos avem un graf partial al grafului de mai sus (Fig.1)

Fig.2

Cu alte cuvinte, un graf partial al unui graf se obtine pastrând aceeasi multime de vârfuri si eliminând o parte din muchii.

Definitie. Un subgraf al unui graf G=(X,U) este un graf H=(Y,V) astfel încât YÌ X iar V contine toate muchiile din U care au ambele extremitati în Y. Vom spune ca subgraful H este indus sau generat de multimea de vârfuri Y.

Ex. Mai jos avem un subgraf al grafului din Fig.1 obtinut prin eliminarea nodului 3

Definitie. Gradul unui vârf x este numarul muchiilor incidente cu x.

Gradul vârfului x se noteaza cu d(x).

Ex. în Fig.1 d(1)=3, d(4)=2, d(8)=0, d(6)=1

Un vârf care are gradul 0 se numeste vârf izolat.

Un vârf care are gradul 1 se numeste vârf terminal.