ALGORITMICA GRAFURILOR
09 - 10
C. Croitoru
săptămâna 3
AGENDA
Vocabular al teoriei grafurilor
(ag 09- 10 [Link] pag. ≈ 32 - 67)
Problemele pentru seminarul 3
♦♦
1
Vocabular
(Variaţii ı̂n definiţia unui graf)
Grade
Subgrafuri
Operaţii cu grafuri
Clase de grafuri
Drumuri şi circuite
Conexiune
Matrici asociate
Structuri de date
2
Problemele pentru seminarul 3
Acesta este un seminar special, cu probleme foarte uşoare, având
ca singur scop fixarea unor noţiuni.
Problema 1. Fie G1, G2, G3 trei grafuri. Se
ştie că G1 ∼ G şi că G =
= ∼ G . Rezultă că
2 2 3
G1 =∼G ? (justificare)
3
Problema 2. Sunt cele două grafuri desenate
mai jos izomorfe ? (justificare)
Problema 3. Demonstraţi că dacă un graf
conex G are exact un circuit atunci |G| = |E(G)|.
3
Problema 4. Determinaţi numărul de stabili-
tate al grafului desenat mai jos. (justificare)
Problema 5. Fie G un graf conex cu |G| >
1 si fără vı̂rfuri de grad 1. Demonstraţi că
|E(G)| ≥ n.
Problema 6. Fie G = (V, E) un graf conex cu
|G| ≥ 2. Demonstraţi că există un vârf v0 ∈ V
astfel ı̂ncât G − v0 este conex.
Problema 7. Este posibil ca numărul arbo-
rilor parţiali ai unui graf să fie 1? Dar 2 ?
(justificare)
4
Problema 8. Să se determine L(L(G)), unde
graful G este:
Problema 9. Dacă G este graful desenat mai
jos, este L(G) –graful reprezentativ al muchi-
ilor sale– hamiltonian? (justificare)
Problema 10. Precizaţi numărul cromatic
(argumentare) al complementarului grafului de
mai sus.
Problema 11. Precizaţi numărul de conexiune
(argumentare) al grafului de la problema 9.
5
Problema 12. Este graful următor autocom-
plementar ? (argumentare)
Problema 13. Are graful de mai sus doi ar-
bori parţiali fără muchii comune? (argumentare)
Problema 14. Stabiliţi numărul arborilor parţiali
ai complementarului grafului de la problema
12. (argumentare)
Problema 15. Stabiliţi cardinalul maxim al
unei multimi stabile din graful K2 × G, unde G
este tot graful de la problema 12.
Problema 16. Dacă G este graful desenat mai
jos, este L(G) –graful reprezentativ al muchi-
ilor sale– hamiltonian? (justificare)
6
Problema 17. Pentru graful G desenat mai
jos să se determine numărul cromatic χ(G) (ar-
gumentare).
Problema 18. Este graful de mai sus izomorf
cu complementarul său ? (justificare)
Problema 19. Determinaţi numărul de conex-
iune al grafului de la problema 17. (justificare)
Problema 20. Determinaţi diametrul grafului
de la problema 17. (justificare)
Problema 21. Determinaţi χ (G), indicele cro-
matic al grafului de la problema 17. (justifi-
care)
7