Grafuri neorientate

O muchie u U este deci o submultime {x, y} de varfuri distincte din X si se noteaza u = [x, y]. Vom spune despre varfurile x si y ca sunt adiacente in G, iar despre u si x ca sunt incidente la fel ca si u si y. Se mai spune ca x si y sunt extremitatile muchiei u.Daca u1 si u2 sunt doua muchii care au o extremitate comuna, ele vor fi numite de asemenea incidente.

Un prim element atragator al teoriei grafurilor este aspectul geometric sau grafic al subiectului. Astfel, un graf poate fi prezentat cu ajutorul unei figuri plane in care fiecarui varf i se asociaza un punct si fiecarei muchii [x, y], o linie curba care uneste in plan punctele ce corespund varfurilor x si y.

Al doilea aspect interesant este dezvoltarea naturala a teoriei grafurilor; de indata ce definitia unui graf a fost prezentata, notiunile si rezultatele par sa se nasca singure si in mod spontan, astfel incat cel care studiaza acest domeniu pare sa aiba impresia ca ar fi putut fi chiar el insusi creatorul acestui domeniu.Sa dam un prim exemplu. Fie G = (X,U) astfel incat X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, iar U = [1, 5], [3, 7], [4, 6], [9, 8], [10, 2], [1, 2], [9, 4], [1, 10], [6, 8].

Definitie. Un graf partial al grafului G = (X, U) este un graf G1 = (X, V) astfel incat V U, adica G1 are aceiasi multime de varfuri ca G iar multimea de muchii V este chiar U sau o submultime a acesteia.Cu alte cuvinte, un graf partial al unui graf se obtine pastrand aceeasi multime de varfuri si eliminand o parte din muchii. Se mai spune ca un graf partial G1 =(X, V) este indus de multimea V de muchii.Exemplu . pentru graful G din figura anterioara , G1=(X,V) , unde
V ={[1,5],[2,10],[6,4]}, este un graf partial reprezentat in figura de mai jos. Reprezentarea in plan a acestui graf partial este data in figura 2.

Definitie : Un subgraf al unui graf G=(X,U) este un graf H=(Y,V) astfel incat YX iar V contine toate muchiile din U care au ambele extremitati in Y. Vom spune ca subgraful H este indus sau generat de multimea de varfuri Y. De fapt, subgraful se obtine prin eliminarea unei parti din varfuri si toate muchiile incidente cu acestea .
Exemplu. Pentru graful G din figura anterioara , G1=(X,V) , unde V ={[1,5],[2,10],[6,4]}, este un graf partial reprezentat in figura de mai jos. Reprezentarea in plan a acestui subgraf este data in figura 3.

Definitie. Gradul unui varf x este numarul muchiilor incidente cu x. Se noteaza cu d(x) ('d' reprezinta prima litera din cuvantul degre din limba franceza care inseamna grad).Un varf care are gradul 0 (deci pentru care nu exista vreo muchie incidenta cu el) se numeste varf izolat. Un varf care are gradul 1 (deci care este incident cu o singura muchie) este numit varf terminal.Pentru graful din figura 1 avem : d(11) = 0, deci varful 11 este izolat.

Propozitia 1.
Daca un graf G = (X, U) are m muchii si n varfuri, iar X={x1, x2,..., xn } atunci 2m .Demonstratie. Este suficient sa observam ca fiecare muchie [x, y] contribuie cu o unitate la gradul lui x si cu o unitate la gradul lui y, deci cu doua unitati in suma din enunt. Cum sunt m muchii, suma gradelor tuturor varfurilor este 2m.

Clase speciale de grafuri
Exista tipuri de grafuri care au proprietati speciale si care intervin in anumite categorii de probleme si rationamente. Ele au denumiri si notatii speciale. Vom prezenta doua astfel de clase speciale de grafuri.
Definitie. Se numeste graf complet cu n varfuri un graf care are proprietatea ca orice doua noduri diferite sunt adiacente.
Un graf complet cu n varfuri se noteaza prin Kn .