Curs 1: Grafuri; Introducere

Curs 1: Grafuri; IntroducereTeoria grafurilor

Radu Dumbraveanu

Universitatea de Stat “A. Russo” din Balt, iFacultatea de S, tiint,e Reale

Aceasta prezentare este pusa la dispozitie sub Licenta Atribuire -Distribuire-ın-conditii-identice 3.0 Ne-adaptata (CC BY-SA 3.0)

Balt, i, 2013

R. Dumbraveanu (USARB) Curs 1: Grafuri; Introducere Balt,i, 2013 1 / 42

https://creativecommons.org/licenses/by-sa/3.0/deed.ro

https://creativecommons.org/licenses/by-sa/3.0/deed.ro

Graf; Vırfuri; Muchii

Definit, ieUn graf este o pereche G = (V ,E) de mult, imi unde E este o mult, ime deperechi neordonate de elemente din V .

Elementele mult, imii V se numesc vırfurile grafului G; elementele mult, imiiE se numesc muchiile grafului G.

Daca e = {u, v} este o muchie a grafului atunci spunem ca e esteincidenta cu vırfurile u s, i v; iar u s, i v sınt adiacente (sau vecine).

Vırfurile cu care o muchie este incidenta se numesc extremitat, ile acesteia.


Reprezentarea grafica

u

v x

yz

G = ({u, v, x, y, z}, {{u, v}, {u, x}, {u, y}, {u, z}})


Reprezentarea grafica

u

v x

yz

H = (V ,E) unde V = {u, v, x, y, z}, E = {vx, xy, yz, zv}


Graf vid; Graf trivial; Graf nul

Graful (∅, ∅) se noteaza simplu prin ∅ s, i se numes, te graful vid.

Graful fara vırfuri sau doar cu 1 vırf se numes, te graf trivial.

Graful cu 0 muchii se numeste graf nul s, i se noteaza Nn unde n ∈ N estenumarul de vırfuri.


Numarul de vırfuri; Numarul de muchii

Numarul de vırfuri ale unui graf G se numes, te ordinul grafului G; senoteaza |G|.

Numarul de muchii ale unui graf G se noteaza ||G||.

Daca |G| = n s, i ||G|| = m, atunci spunem ca avem un (n,m)-graf.

Pentru a indica faptul ca un graf are ordinul n se poate folosi expresia:“graf pe n vırfuri”.


Mult, imea vırfurilor; Mult, imea muchiilor

Fiind dat un graf G putem folosi notat, ia V (G) pentru a ne referi lamult, imea de vırfuri s, i E(G) a ne referi la mult, imea de muchii.

I De exemplu: Daca G = ({a, b, c}, {ab, ac}) atunci V (G) = {a, b, c},iar E(G) = {ab, ac};

I De exemplu: V (∅) = ∅ s, i E(∅) = ∅.

Pentru a indica faptul ca un graf are mult, imea vırfurilor V se poate folosiexpresia: “graf pe V ”.


Multigraf

v

u

x

yz


Multigraf

Definit, ieUn multigraf este o un triplet G = (V ,E , f ) care consta din douamult, imi disjuncte V , E s, i o funct, ie de incident, a f : E → V ∪ [V ]2.

Prin [V ]2 am notat mult, imea tuturor perechilor neordonate de elementedin V .

Mult, imile V s, i E sınt multimile de vırfuri s, i muchii;

Funct, ia f pune ın corespondent, a fiecarei muchii capetele acesteia;

Muchiile e1, e2, ..., en pentru care f (e1) = ... = f (en) se numesc muchiimultiple (sau paralele);

Iar muchiile pentru care f este un doar un vırf, f (e) = {v} se numescbucle.


Multigraf

Definit, ieUn graf este o pereche G = (X ,Γ) formata de mult, imea X s, i aplicat, iaΓ : X → X .

Definit, ieUn graf este o pereche G = (X ,U ); unde X este mult, imea vırfurilor, iarU ⊆ X ×X mult, imea arcelor.


Grafuri izomorfe

Definit, ieDoua grafuri G s, i H sınt izomorfe daca exista o biject, ief : V (G)→ V (H ) cu proprietatea ca doua vırfuri u s, i v sınt adiacente ınG daca s, i numai daca f (u) s, i f (v) sınt adiacente ın H pentru orice u s, i vdin V (G).

Pentru grafurile izmorfe se utilizeaza notat, ia G ∼ H .

O asemenea funct, ie f se numes, te izomorfism daca G 6= H s, iautomorfism ın caz contrar.

Din punct de vedere vizual, grafurile G s, i H sınt izomorfe daca pot fiaranjate astfel ıncıt ınfat, is, area lor sa fie identica (desigur, fara a schimbaadiacent, a).


Grafuri izomorfe

v

u

x

yz a b

cd

e

Grafuri izomorfe

u bv ax cy dz e

Tabela: Corespondent, eleR. Dumbraveanu (USARB) Curs 1: Grafuri; Introducere Balt,i, 2013 12 / 42

Grade [ale vırfurilor]Gradul (sau valent, a) unui vırf v este numarul muchiilor incidente cu v s, ise noteaza cu d(v).

Pentru un orice graf G notam δ(G) = min{d(v) : v ∈ V (G)} s, i∆(G) = max{d(v) : v ∈ V (G)}.

Daca δ(G) = ∆(G) atunci graful G se numes, te regulat.

Daca δ(G) = ∆(G) = k atunci graful G se numes, te k-regulat.

k Denumire0 graf nul2 graf bivalent3 graf cubic (sau graf trivalent)

Tabela: Grafuri k-regulate remarcabile


Grafuri k-regulate

Grafuri regulate (de la stınga spre dreapta): 0-regulat, 2-regulat, 3-regulat


Cazuri particulare

Cıte grafuri 1-regulate neizomorfe exista?

Un vırf cu gradul 1 se numes, te terminal.

Un vırf cu gradul 0 se numes, te izolat.

O bucla mares, te gradul vırfului cu care este incidenta cu 2.


Cazuri particulare

u0

u1

u2

u3

v

De la stınga spre dreapta: graf 1-regulat, graf cu un vırf izolat


Proprietat, i

TeoremaIntr-un graf simplu s, i netrivial exista cel put, in doua vırfuri cu acelas, i grad.

TeoremaIn orice graf G suma gradelor vırfurilor este de doua ori numarul demuchii, adica ∑

v∈V (G)d(v) = 2|E(G)|. (1)

CorolarIn orice graf, numarul varfurilor de grad impar este par.


Secvent, e de grade

O secvent, a nevida (d1, d2, ..., dn) de numere naturale se numes, te secvent, agrafica daca exista un graf pe n vırfuri a carui grade sınt membrii acesteisecvent, e.

Suma gradelor dintr-o secvent, a grafica este un numar par.

Graful pe n vırfuri a carui grade sınt membrii secvent, ei (d1, d2, ..., dn) senumes, te realizarea acestei secvent, e.


Secvent, e de grade

Teorema (Havel-Hakimi)O secvent, a descresatoare

(d1, d2, ..., dn) (2)

de numere naturale, d1 ≥ 1 s, i n ≥ 2, este secvent, a de grade a unui grafsimplu daca s, i numai daca

(d2 − 1, d3 − 1, ..., dd1+1 − 1, dd1+2, ..., dn) (3)

este secvent, a de grade a unui graf simplu.

Secvent, a (3) se obt, ine din (2) prin ınlaturarea primului numar s, idecrementarea urmatoarelor d1 numere.


Aplicat, ii

Teorema Havel-Hakimi poate fi utilizata pentru a determina daca osecvent, a de numere naturale reprezinta secvent, a de grade a unui grafsimplu.

De exemplu:

(4, 3, 3, 3, 1)↓

(2, 2, 2, 0)↓

(1, 1, 0)↓

(0, 0)

Ultima secvent, a este secvent, a grafulN2 care este simplu.


Aplicat, ii

(2, 2, 1, 1)↓

(1, 0, 1)↓

(−1, 1)

Ultima secvent, a nici nu este grafica.


Lant, uri [ın grafuri]

Un lant, este o secvent, a de vırfuri s, i muchii

(v0, e1, v1, e2, v2, ..., vn−1, en , vn)

ale unui graf G, cu proprietatea ca oricare doua vırfuri consecutive din lant,vi−1 s, i vi sınt unite prin muchia ei , ∀i = 1,n.

Vırfurile e1, e2, ..., en−1 se numesc vırfuri interioare ale lant, ului, iar v0 s, ivn - extremitat, i.

Daca lantul contine numai muchii distincte atunci se numes, te lant simplu.

Daca lantul contine numai vırfuri distincte atunci el se numes, te lant,elementar.


Lant, uri

v4

v1

v2

v3

v7

v8

v5

v6

Lant, : (v3, v3v4, v4, v4v5, v5, v5v8, v8);

Lant, neelementar:(v1, v1v4, v4, v4v5, v5, v5v8, v8, v8v7, v7, v7v6, v6, v6v5, v5v4, v4, v4v3, v3);


Lant, uri

Lant, ul se poate defini s, i cu ajutorul muchiilor sale

(v0v1, v1v2, ..., vn−1, vn),

iar ın cazul cınd graful G este simplu putem definit lant, ul doar cu ajutorulvırfurilor sale

(v0, v1, v2, ..., vn−1, vn).

De ce ın cazul grafului simplu lant, ul poate fi definit doar utilizınd vırfurilesale?

Numarul de muchii din lant, se numeste lungimea lant, ului.


Cicluri

Un lant, ın care extremitat, ile reprezinta acelas, i vırf numes, te ciclu.

Ciclul este elementar daca vırfurile interioare sınt distincte.

O muchie care unes, te doua vırfuri ale unui ciclu ınsa nu apart, ine acestuiase numes, te coarda.


Cicluri

u0 u1 v0

v1

v2

v3

Ciclu: u0, v1, v0, v3, u0;

Ciclu: v0, v1, v2, v3, v0;

Ciclu neelementar: u0, v1, v2, v3, v0, v1, u0.


Grafuri bipartite

Definit, ieUn graf bipartit este un graf G cu proprietat, ile:

I exista submult, imile X ,Y ⊆ V (G) cu X ∩Y = ∅ s, i X ∪Y = V (G);I orice muchie are un capat ın X s, i altul ın Y .

Perechea {X ,Y } se numes, te bipartit, ia grafului G.


Grafuri bipartite

u0

u1

u2

v0

v1

G1

u0

u1

u2

v0

v1

v2

G2

v5 v0

v1v2

v3v4

G3

Care sınt bipartit, iile grafurilor G1,G2 s, i G3?


Grafuri bipartite; Cicluri

TeoremaUn graf este bipartit daca s, i numai daca nu cont, ine cilcuri impare.


Graf conex

Un graf este conex daca ıntre oricare doua varfuri exista un lant, .

Un lant, care unes, te vırfurile u s, i v se numes, te u − v-lant, .


Graf conex

Un graf conex

Un graf neconex


Centru; Raza; Diametru

Distant, a dintre doua vırfuri u, v ale unui graf conex este numarul minimde muchii ale unui lant de la u la v; se noteaza d(u, v).

Excentricitatea unui vırf v este distanta maxima de la acest vırf lacelelalte vırfuri; se noteaza ε(v)

Excentricitatea minima a vırfurilor se numes, te raza grafului G; se noteazarad(G).

Vırfurile cu excentricitatea minima se numesc centrale.

Centrul grafului este mult, imea tuturor vırfurilor centrale.

Excentricitatea maxima a vırfurilor se numes, te diametrul grafului G; senoteaza diam(G).


Centru; Raza; Diametru

a0

b0 b1 b2 b3 b4

Un graf G;ε(a0) = 1, ε(b0) = ε(b1) = ... = ε(b4) = 2;

rad(G) = 1, diam(G) = 2 s, i unicul vırf central este a0.

v

u

x

yz

???


Proprietat, i

TeoremaPentru orice graf G, rad(G) ≤ diam(G) ≤ 2rad(G).


Grafuri remarcabile; Graf nul vs. graf complet

N3 N4 N5

K3 K4 K5


Grafuri remarcabile; Graf nul vs. graf complet

Definit, ie (Graf nul)Un graf nul este un graf ın totalitate fara muchii, adica de forma (V , ∅);un graf nul pe n vırfuri se noteaza Nn , n ≥ 1.

Definit, ie (Graf complet)Un graf graf complet este un graf ın care orice 2 vırfuri diferite sıntadiacente; se noteaza Kn , unde n, n ≥ 1, semnifica numarul de vırfuri alegrafului.


Grafuri remarcabile; Graf bipartit vs. graf bipartit complet

G0 G4 G8

K2,3 K4,4 K1,3


Grafuri remarcabile; Graf bipartit vs. graf bipartit complet

Definit, ie (Graf bipartit)

Definit, ie (Graf bipartit complet)Kp,q , p, q ≥ 1.


Grafuri remarcabile; Graf lant, vs. graf ciclu

P3 P4

C3 C4 C5


Grafuri remarcabile; Graf lant, vs. graf ciclu

Definit, ie (Graf lant, )Un graf pe n vırfuri, n ≥ 1, se numes, te graf lant, daca consta dintr-unlant, elementar; se noteza Pn .

Definit, ie (Graf ciclu)Un graf pe n vırfuri, n ≥ 3, se numes, te graf ciclu daca consta dintr-uncilcu elementar; se noteza Cn .


Grafuri remarcabile; Graf stea vs. graf roata

S4 S5 S6

W4 W5 W6


Grafuri remarcabile; Graf stea vs. graf roata

Definit, ie (Graf stea)Un graf pe n vırfuri, n ≥ 1, se numes, te graf stea daca este K1,n−1; senoteza Sn .

Definit, ie (Graf roata)Un graf pe n vırfuri, n ≥ 4, se numes, te graf roata daca ...; se noteza Wn .


Curs 1: Grafuri; Introducere

Education

Transcript of Curs 1: Grafuri; Introducere