curs 1_ag_2013

Marinescu – Ghemeci Ruxandra

verman@fmi.unibuc.ro

Dragos-Radu Popescu, Combinatorică şi

teoria grafurilor, Editura Societatea de Ştiinţe

Matematice din România, Bucureşti, 2005.

J.A. Bondy, U.S.R Murty – Graph theory with

applications, The Macmillan Press 1976

T.H. Cormen, C.E. Leiserson, R.R. Rivest –

Introducere in algoritmi, Mit Press, trad.

Computer Libris Agora

Ioan Tomescu, Problems in combinatorics

and graph theory, New York: Wiley, 1985

H. Georgescu – Tehnici de programare,

Editura Universităţii din Bucureşti, 2005

infoarena.ro

25% laborator

75% examen scris

Secvenţe de grade

Conectivitate

Arbori

Parcurgerea grafurilor

Drumuri minime

Arbori parţiali de cost minim

Cuplaje

Fluxuri în reţele de transport

Grafuri hamiltoniene

Grafuri euleriene

Grafuri planare

Colorări

S o mulţime finită nevidă

Multiset

R = (S, r)

r : S ℕ funcţie de multiplicitate

S o mulţime finită nevidă

Multiset

R = (S, r)

r : S ℕ funcţie de multiplicitate

Notaţie

R = {xr(x) | x S}

Exemplu

S = {1, 2, 3, 4, 5}

R = {22, 3, 53}

S o mulţime finită nevidă

Multiset

R = (S, r)

r : S ℕ funcţie de multiplicitate

Notaţie

R = {xr(x) | x S}

Exemplu

S = {1, 2, 3, 4, 5}

R = {22, 3, 53}

|R| = k → k-multiset

incluziune, reuniune / reuniune disjunctă…

Sm = { (x1, x2, …, xm) | xi S}

S<m> = { X | X este m-multiset peste S}

S(m) = { X | X S, |X| = m}

G = (V, E), E = (V2, r)

◦ e = (u, v) - arc

◦ u = v - buclă

◦ u = e- - vârf iniţial / origine / extremitate iniţială

◦ v = e+ - vârf final / terminus

◦ - grad interior

◦ - grad exterior

◦ - grad

( )G

d u

( )G

d u

( )G

d u

G = (V, E), E = (V<2>, r)

◦ e = uv - muchie

◦ u = v - buclă

◦ u, v - capete / extremităţi

◦ - grad

( )G

d u

G = (V, E), E V(2)

◦ e = {u, v} - muchie

◦ u = v - buclă

◦ u, v - capete / extremităţi

◦ - grad

( )G

d u

V(G), E(G)

e = uv

vârfuri adiacente

muchii adiacente

vecinii unui vârf v: N(v)

muchie incidentă într-un vârf

Drum / Lanţ

P = [v1, e1, v2, e2, …, vm-1,em-1,vm]

Drum simplu / elementar

Lungime

Circuit / cilcu

Circuit simplu / elementar

Graf parţial

Subgraf

Subgraf indus G[X]

Caz neorientat

Graf conex

Componentă conexă

Graf bipartit

G orientat, V = {v1, v2, …, vn}

◦ Multisetul gradelor interioare

◦ Multisetul gradelor exterioare

G neorientat, V = {v1, v2, …, vn}

◦ Multisetul gradelor

1( ) { ( ), ..., ( )}

G G ns G d v d v

1( ) { ( ), ..., ( )}

G G ns G d v d v

1( ) { ( ), ..., ( )}

G G ns G d v d v

G – v , v V(G)

G – e , e E(G)

G – V ' , V ' V(G)

G – E' , E' E(G)

G + e

G1 = (V1, E1), E1 = (V1<2>, r1)

G2 = (V2, E2), E2 = (V2<2>, r2)

G1 G2 există f : V1 V2 bijectivă cu

r1( uv ) = r2( f(u)f(v) )

G1 G2 s(G1) = s(G2)

s(G1) = s(G2) G1 G2 ?

1736 - Leonhard Euler

Solutio problematis ad geometriam situs

pertinentis

Ciclu eulerian

Graf eulerian

Interpretare

Se poate desena diagrama printr-o curbă

continuă închisă fără a ridica creionul de pe

hârtie şi fără a desena o linie de două ori?

De câte ori (minim) trebuie să ridicăm

creionul de pe hârtie pentru a desena

diagrama?

Pn – lanţ elementar

Cn – ciclu elementar

Kn – graf complet

Kp,q – graf bipartit complet

Geometrică

Algebrică

Matrice de adiacenţă

Liste de adiacenţă

Listă de muchii

Matrice de incidenţă

Dată o secvenţă de numere s, se poate

construi un graf neorientat având

secvenţa gradelor s?

Dar un graf simplu?

Condiţii necesare

Condiţii suficiente