curs 1_ag_2013
TRANSCRIPT
Marinescu – Ghemeci Ruxandra
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