Curs 3: Grafuri; Subgrafuri; Operat, iiTeoria 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 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 1 / 26
Subgraf
Un subgraf al unui graf G este un graf H astfel ıncıt V (H ) ⊆ V (G),E(H ) ⊆ E(G) s, i pentru orice muchie din E(H ) capetele acesteia sınt ınV (G).
Altfel spus, trebuie sa avem E(H ) ⊆ [V (H )]2 pentru ca H sa poata finumit subgraf al lui G.
Pentru a desemna ca H este subgraf al lui G utilizam notat, ia H ⊆ G s, iputem spune ca H se cont, ine ın G (sau G cont, ine H ).
Daca H ⊆ G, H 6= ∅ s, i H 6= G spunem ca H este un subgraf propriu allui G.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 2 / 26
Subgraf
Un subgraf al unui graf G este un graf H astfel ıncıt V (H ) ⊆ V (G),E(H ) ⊆ E(G) s, i pentru orice muchie din E(H ) capetele acesteia sınt ınV (G).
Altfel spus, trebuie sa avem E(H ) ⊆ [V (H )]2 pentru ca H sa poata finumit subgraf al lui G.
Pentru a desemna ca H este subgraf al lui G utilizam notat, ia H ⊆ G s, iputem spune ca H se cont, ine ın G (sau G cont, ine H ).
Daca H ⊆ G, H 6= ∅ s, i H 6= G spunem ca H este un subgraf propriu allui G.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 2 / 26
Subgraf
Un subgraf al unui graf G este un graf H astfel ıncıt V (H ) ⊆ V (G),E(H ) ⊆ E(G) s, i pentru orice muchie din E(H ) capetele acesteia sınt ınV (G).
Altfel spus, trebuie sa avem E(H ) ⊆ [V (H )]2 pentru ca H sa poata finumit subgraf al lui G.
Pentru a desemna ca H este subgraf al lui G utilizam notat, ia H ⊆ G s, iputem spune ca H se cont, ine ın G (sau G cont, ine H ).
Daca H ⊆ G, H 6= ∅ s, i H 6= G spunem ca H este un subgraf propriu allui G.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 2 / 26
Subgraf
Un subgraf al unui graf G este un graf H astfel ıncıt V (H ) ⊆ V (G),E(H ) ⊆ E(G) s, i pentru orice muchie din E(H ) capetele acesteia sınt ınV (G).
Altfel spus, trebuie sa avem E(H ) ⊆ [V (H )]2 pentru ca H sa poata finumit subgraf al lui G.
Pentru a desemna ca H este subgraf al lui G utilizam notat, ia H ⊆ G s, iputem spune ca H se cont, ine ın G (sau G cont, ine H ).
Daca H ⊆ G, H 6= ∅ s, i H 6= G spunem ca H este un subgraf propriu allui G.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 2 / 26
Exemple
v
u
x
yz
G
v
u
x
yz
v
u
x
z
H = ({u, v, x, z}, {uv, xz})
v
u
x
yz
v
u
x
yz
I = ({u, v, x, y, z}, {})
v
u
x
yz
v
u
x
z
J = ({u, v, x, z}, {uv, xz, vy})
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 3 / 26
Exemple
v
u
x
yz
G
v
u
x
yz
v
u
x
z
H = ({u, v, x, z}, {uv, xz})
v
u
x
yz
v
u
x
yz
I = ({u, v, x, y, z}, {})
v
u
x
yz
v
u
x
z
J = ({u, v, x, z}, {uv, xz, vy})
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 3 / 26
Exemple
v
u
x
yz
G
v
u
x
yz
v
u
x
z
H = ({u, v, x, z}, {uv, xz})
v
u
x
yz
v
u
x
yz
I = ({u, v, x, y, z}, {})
v
u
x
yz
v
u
x
z
J = ({u, v, x, z}, {uv, xz, vy})
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 3 / 26
Exemple
v
u
x
yz
G
v
u
x
yz
v
u
x
z
H = ({u, v, x, z}, {uv, xz})
v
u
x
yz
v
u
x
yz
I = ({u, v, x, y, z}, {})
v
u
x
yz
v
u
x
z
J = ({u, v, x, z}, {uv, xz, vy})
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 3 / 26
Exemple
v
u
x
yz
G
v
u
x
yz
v
u
x
z
H = ({u, v, x, z}, {uv, xz})
v
u
x
yz
v
u
x
yz
I = ({u, v, x, y, z}, {})
v
u
x
yz
v
u
x
z
J = ({u, v, x, z}, {uv, xz, vy})
Structura J nu este subgraf al lui G
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 3 / 26
Cazuri particulare de subgrafuri
I Daca H ⊆ G s, i V (H ) = V (G), atunci H se numes, te subgraf deacoperire.
I Daca H ⊆ G s, i E(H ) cont, ine toate muchiile uv ∈ E(G) cuu, v ∈ V (H ), atunci H se numes, te subgraf indus(sau generat) demult, imea V (H ) – s, i se noteaza H = G[V (H )].
I Daca H ⊆ G s, i V (G) consta numai din extremitat, ile muchiilor dinE(H ) atunci H se numes, te subgraf muchie-indus de E(H ) s, i senoteaza G[E(H )].
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 4 / 26
Cazuri particulare de subgrafuri
I Daca H ⊆ G s, i V (H ) = V (G), atunci H se numes, te subgraf deacoperire.
I Daca H ⊆ G s, i E(H ) cont, ine toate muchiile uv ∈ E(G) cuu, v ∈ V (H ), atunci H se numes, te subgraf indus(sau generat) demult, imea V (H ) – s, i se noteaza H = G[V (H )].
I Daca H ⊆ G s, i V (G) consta numai din extremitat, ile muchiilor dinE(H ) atunci H se numes, te subgraf muchie-indus de E(H ) s, i senoteaza G[E(H )].
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 4 / 26
Cazuri particulare de subgrafuri
I Daca H ⊆ G s, i V (H ) = V (G), atunci H se numes, te subgraf deacoperire.
I Daca H ⊆ G s, i E(H ) cont, ine toate muchiile uv ∈ E(G) cuu, v ∈ V (H ), atunci H se numes, te subgraf indus(sau generat) demult, imea V (H ) – s, i se noteaza H = G[V (H )].
I Daca H ⊆ G s, i V (G) consta numai din extremitat, ile muchiilor dinE(H ) atunci H se numes, te subgraf muchie-indus de E(H ) s, i senoteaza G[E(H )].
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 4 / 26
Exemple
v
u
x
yz
G
v
u
x
yz
v
u
x
z
H = G[{u, v, x, z}]
v
u
x
yz
v
u
x
yz
J = G[{uv, xz, vy}]
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 5 / 26
Exemple
v
u
x
yz
G
v
u
x
yz
v
u
x
z
H = G[{u, v, x, z}]
v
u
x
yz
v
u
x
yz
J = G[{uv, xz, vy}]
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 5 / 26
Exemple
v
u
x
yz
G
v
u
x
yz
v
u
x
z
H = G[{u, v, x, z}]
v
u
x
yz
v
u
x
yz
J = G[{uv, xz, vy}]
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 5 / 26
Cazuri particulare de subgrafuri
Evident, orice graf G ıs, i este subgraf de acoperire.
Evident, G = G[V (G)].
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 6 / 26
Maximalitate/minimalitate
Spunem ca un subgraf H este maximal ın raport cu o proprietate daca nuexista un alt subgraf I cu acesta proprietate s, i H ⊂ I .
Spunem ca un subgraf H este minimal ın raport cu o proprietate daca nuexista un alt subgraf I cu acesta proprietate s, i H ⊃ I .
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 7 / 26
Maximalitate/minimalitate
Spunem ca un subgraf H este maximal ın raport cu o proprietate daca nuexista un alt subgraf I cu acesta proprietate s, i H ⊂ I .
Spunem ca un subgraf H este minimal ın raport cu o proprietate daca nuexista un alt subgraf I cu acesta proprietate s, i H ⊃ I .
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 7 / 26
Maximalitate/minimalitate
v0
v1
v2
v3
v4
G
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 8 / 26
Maximalitate/minimalitate
v0
v1
v2
v3
v4
G
In graful G subgraful evident, iat [cu sur] este un subgraf minimal carecont, ine un ciclu.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 8 / 26
Maximalitate/minimalitate
v0
v1
v2
v3
v4
G
v0
v1
v2
v3
u0 u1
H
In graful G subgraful evident, iat [cu sur] este un subgraf minimal carecont, ine un ciclu.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 8 / 26
Maximalitate/minimalitate
v0
v1
v2
v3
v4
G
v0
v1
v2
v3
u0 u1
H
In graful G subgraful evident, iat [cu sur] este un subgraf minimal carecont, ine un ciclu.
In graful H cel doua subgrafuri evident, iate [cu sur] sınt maximal conexe.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 8 / 26
Componente conexe
Subgrafurile maximal conexe se numesc componente conexe (sau simplucoponente).
Un graf conex consta dintr-o singura comonenta conexa.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 9 / 26
Componente conexe
Subgrafurile maximal conexe se numesc componente conexe (sau simplucoponente).
Un graf conex consta dintr-o singura comonenta conexa.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 9 / 26
Componente conexe
G H
Graful G consta din 2 componente conexe.
Graful H consta din 3 componente conexe.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 10 / 26
Operat, ii; Suprimarea unui vırf
Suprimarea unui vırf v dintr-un graf G presupune ındepartarea vırfuluipropriuzis s, i ındepartarea tuturor muchiilor incidente cu v; se noteazaG − v.
Echivalent, G − v = G[V (G) \ {v}].
v
K4 K4 − v
Sinonime pentru operat, ia “suprimare”: “s, tergerea”, “ınlaturarea”,“ındepartarea”, “eliminarea” unui vırf.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 11 / 26
Operat, ii; Suprimarea unui vırf
Suprimarea unui vırf v dintr-un graf G presupune ındepartarea vırfuluipropriuzis s, i ındepartarea tuturor muchiilor incidente cu v; se noteazaG − v.
Echivalent, G − v = G[V (G) \ {v}].
v
K4 K4 − v
Sinonime pentru operat, ia “suprimare”: “s, tergerea”, “ınlaturarea”,“ındepartarea”, “eliminarea” unui vırf.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 11 / 26
Operat, ii; Suprimarea unui vırf
Suprimarea unui vırf v dintr-un graf G presupune ındepartarea vırfuluipropriuzis s, i ındepartarea tuturor muchiilor incidente cu v; se noteazaG − v.
Echivalent, G − v = G[V (G) \ {v}].
v
K4 K4 − v
Sinonime pentru operat, ia “suprimare”: “s, tergerea”, “ınlaturarea”,“ındepartarea”, “eliminarea” unui vırf.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 11 / 26
Suprimarea unei muchii
Suprimarea unei muchii e dintr-un graf G presupune ındepartarea doarmuchiei propriuzise; se noteaza G − e.
Echivalent, G − e este graful (V (G), E ′) cu E ′ = E \ {e}.
v
x
y
z
G
v
x
y
z
G − xy
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 12 / 26
Suprimarea unei muchii
Suprimarea unei muchii e dintr-un graf G presupune ındepartarea doarmuchiei propriuzise; se noteaza G − e.
Echivalent, G − e este graful (V (G), E ′) cu E ′ = E \ {e}.
v
x
y
z
G
v
x
y
z
G − xy
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 12 / 26
Suprimarea unei muchii
Suprimarea unei muchii e dintr-un graf G presupune ındepartarea doarmuchiei propriuzise; se noteaza G − e.
Echivalent, G − e este graful (V (G), E ′) cu E ′ = E \ {e}.
v
x
y
z
G
v
x
y
z
G − xy
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 12 / 26
Contract, ia muchiilor
Contract, ia unei muchii e = uv [ıntr-un vırf ve] presupune suprimareamuchiei e s, i ınlocuirea vırfurilor u, v printr-un singur vırf ve adiacentevecinilor atıt vecinilor lui u cıt s, i vecinilor lui v.
Contract, ia unei muchii e a unui graf G se noteaza G/e.
Formal G/e = (V (G) \ {u, v} ∪ {ve}, E ′) unde v /∈ V (G) ∪ E(G), iar
E ′ = {xy ∈ E(G) : xy ∩ uv = ∅}∪{vey : uy ∈ E(G) \ {e} sau vy ∈ E(G) \ {e}}.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 13 / 26
Contract, ia muchiilor
Contract, ia unei muchii e = uv [ıntr-un vırf ve] presupune suprimareamuchiei e s, i ınlocuirea vırfurilor u, v printr-un singur vırf ve adiacentevecinilor atıt vecinilor lui u cıt s, i vecinilor lui v.
Contract, ia unei muchii e a unui graf G se noteaza G/e.
Formal G/e = (V (G) \ {u, v} ∪ {ve}, E ′) unde v /∈ V (G) ∪ E(G), iar
E ′ = {xy ∈ E(G) : xy ∩ uv = ∅}∪{vey : uy ∈ E(G) \ {e} sau vy ∈ E(G) \ {e}}.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 13 / 26
Contract, ia muchiilor
Contract, ia unei muchii e = uv [ıntr-un vırf ve] presupune suprimareamuchiei e s, i ınlocuirea vırfurilor u, v printr-un singur vırf ve adiacentevecinilor atıt vecinilor lui u cıt s, i vecinilor lui v.
Contract, ia unei muchii e a unui graf G se noteaza G/e.
Formal G/e = (V (G) \ {u, v} ∪ {ve}, E ′) unde v /∈ V (G) ∪ E(G), iar
E ′ = {xy ∈ E(G) : xy ∩ uv = ∅}∪{vey : uy ∈ E(G) \ {e} sau vy ∈ E(G) \ {e}}.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 13 / 26
Contract, ia muchiilor
u v
G
ve
G/uv
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 14 / 26
Adaugarea unei muchii
Suma dintre un graf G s, i o muchie e se noteaza G + e s, i este graful(V (G) ∪V (e), E(G) ∪ e).
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 15 / 26
Generalizarea unor operat, iilor
S, tergerea unei mult, imi de vırfuri U ⊆ V ,
G −U = G[V \U ].
S, tergerea unei mult, imi de muchii F ⊆ E ,
G − F = (V , E \ F).
Suma dintre un graf G s, i o mut, ime de muchii F ,
G + F = (V ∪V (F), E ∪ F).
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 16 / 26
Generalizarea unor operat, iilor
S, tergerea unei mult, imi de vırfuri U ⊆ V ,
G −U = G[V \U ].
S, tergerea unei mult, imi de muchii F ⊆ E ,
G − F = (V , E \ F).
Suma dintre un graf G s, i o mut, ime de muchii F ,
G + F = (V ∪V (F), E ∪ F).
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 16 / 26
Generalizarea unor operat, iilor
S, tergerea unei mult, imi de vırfuri U ⊆ V ,
G −U = G[V \U ].
S, tergerea unei mult, imi de muchii F ⊆ E ,
G − F = (V , E \ F).
Suma dintre un graf G s, i o mut, ime de muchii F ,
G + F = (V ∪V (F), E ∪ F).
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 16 / 26
Maximalitate/minimalitate
Spunem ca un graf G este muchie-maximal cu o anumita proprietatedaca G are acesta proprietate, dar G + uv, pentru orice vırfuri neadiacenteu s, i v din G, nu are aceasta proprietate.
Spunem ca un graf G este muchie-minimal cu o anumita proprietatedaca G are acesta proprietate, dar G − uv, pentru orice vırfuri adiacente us, i v din G, nu are aceasta proprietate.
Un graf G este maximal cu o anumita proprietate daca G are aceastaproprietate, iar orice alt graf H cu H ⊃ G nu are acesta proprietate.
Un graf G este minimal cu o anumita proprietate daca G are aceastaproprietate, iar orice alt subgraf H cu H ⊂ G nu are acesta proprietate.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 17 / 26
Maximalitate/minimalitate
Spunem ca un graf G este muchie-maximal cu o anumita proprietatedaca G are acesta proprietate, dar G + uv, pentru orice vırfuri neadiacenteu s, i v din G, nu are aceasta proprietate.
Spunem ca un graf G este muchie-minimal cu o anumita proprietatedaca G are acesta proprietate, dar G − uv, pentru orice vırfuri adiacente us, i v din G, nu are aceasta proprietate.
Un graf G este maximal cu o anumita proprietate daca G are aceastaproprietate, iar orice alt graf H cu H ⊃ G nu are acesta proprietate.
Un graf G este minimal cu o anumita proprietate daca G are aceastaproprietate, iar orice alt subgraf H cu H ⊂ G nu are acesta proprietate.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 17 / 26
Maximalitate/minimalitate
Spunem ca un graf G este muchie-maximal cu o anumita proprietatedaca G are acesta proprietate, dar G + uv, pentru orice vırfuri neadiacenteu s, i v din G, nu are aceasta proprietate.
Spunem ca un graf G este muchie-minimal cu o anumita proprietatedaca G are acesta proprietate, dar G − uv, pentru orice vırfuri adiacente us, i v din G, nu are aceasta proprietate.
Un graf G este maximal cu o anumita proprietate daca G are aceastaproprietate, iar orice alt graf H cu H ⊃ G nu are acesta proprietate.
Un graf G este minimal cu o anumita proprietate daca G are aceastaproprietate, iar orice alt subgraf H cu H ⊂ G nu are acesta proprietate.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 17 / 26
Maximalitate/minimalitate
Spunem ca un graf G este muchie-maximal cu o anumita proprietatedaca G are acesta proprietate, dar G + uv, pentru orice vırfuri neadiacenteu s, i v din G, nu are aceasta proprietate.
Spunem ca un graf G este muchie-minimal cu o anumita proprietatedaca G are acesta proprietate, dar G − uv, pentru orice vırfuri adiacente us, i v din G, nu are aceasta proprietate.
Un graf G este maximal cu o anumita proprietate daca G are aceastaproprietate, iar orice alt graf H cu H ⊃ G nu are acesta proprietate.
Un graf G este minimal cu o anumita proprietate daca G are aceastaproprietate, iar orice alt subgraf H cu H ⊂ G nu are acesta proprietate.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 17 / 26
Maximalitate/minimalitate
v0
v1
v2
v3
v3 v0
v1
v2
Aceste grafuri sınt muchie-maximale cu P3 ⊆ G
[p.165, Diestel]
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 18 / 26
Punt, i
Fiind dat un graf G, o muchie e ∈ E(G) se numes, te punte daca G − eare mai multe componenete conexe decıt G.
Sınt grafuri care nu au punt, i, de exemplu, Kn sau Cn .
Daca G este conex s, i orice muchie a sa este punte ⇔ G estemuchie-minimal conex.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 19 / 26
Punt, i
Fiind dat un graf G, o muchie e ∈ E(G) se numes, te punte daca G − eare mai multe componenete conexe decıt G.
Sınt grafuri care nu au punt, i, de exemplu, Kn sau Cn .
Daca G este conex s, i orice muchie a sa este punte ⇔ G estemuchie-minimal conex.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 19 / 26
Punt, i
Fiind dat un graf G, o muchie e ∈ E(G) se numes, te punte daca G − eare mai multe componenete conexe decıt G.
Sınt grafuri care nu au punt, i, de exemplu, Kn sau Cn .
Daca G este conex s, i orice muchie a sa este punte ⇔ G estemuchie-minimal conex.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 19 / 26
Punt, i
v
u
x
yz
Muchia zx este punte; celelalte muchii nu sınt punt, i.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 20 / 26
Vırfuri de articulare
Fiind dat un graf G, un vırf v ∈ V (G) se numes, te vırf de articulare dacaG − v are mai multe componenete conexe decıt G.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 21 / 26
Vırfuri de articulare
v0 v1 v2 v3 v4
Toate vırfurile cu except, ia vırfurilor v0 s, i v4 sınt vırfuri de articulare
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 22 / 26
Punt, i; Cicluri
Teorema
O muchie e a unui graf conex G este punte daca s, i numai daca nu existaun ciclu ın G [ın] care sa [se] cont, ina aceasta muchie.
Demonstrat, ie; Necesitatea.Fie e ∈ E(G) o punte ın G atunci G − e cont, ine mai multe componentedecıt G.Adica exista cel put, in doua vırfuri u s, i v care-s conexe ın G, dar nu s, i ınG − e.Acest fapt implica existent, a unui uv-lant, P care trece prin e (de fapt toateuv-lant, urile trec prin e).Notam prin x s, i y capetele muchiei e s, i consideram ca x precede y ın P.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 23 / 26
Punt, i; Cicluri
Teorema
O muchie e a unui graf conex G este punte daca s, i numai daca nu existaun ciclu ın G [ın] care sa [se] cont, ina aceasta muchie.
Demonstrat, ie; Necesitatea.Fie e ∈ E(G) o punte ın G atunci G − e cont, ine mai multe componentedecıt G.Adica exista cel put, in doua vırfuri u s, i v care-s conexe ın G, dar nu s, i ınG − e.Acest fapt implica existent, a unui uv-lant, P care trece prin e (de fapt toateuv-lant, urile trec prin e).Notam prin x s, i y capetele muchiei e s, i consideram ca x precede y ın P.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 23 / 26
Punt, i; Cicluri
Teorema
O muchie e a unui graf conex G este punte daca s, i numai daca nu existaun ciclu ın G [ın] care sa [se] cont, ina aceasta muchie.
Demonstrat, ie; Necesitatea.Fie e ∈ E(G) o punte ın G atunci G − e cont, ine mai multe componentedecıt G.Adica exista cel put, in doua vırfuri u s, i v care-s conexe ın G, dar nu s, i ınG − e.Acest fapt implica existent, a unui uv-lant, P care trece prin e (de fapt toateuv-lant, urile trec prin e).Notam prin x s, i y capetele muchiei e s, i consideram ca x precede y ın P.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 23 / 26
Punt, i; Cicluri
Teorema
O muchie e a unui graf conex G este punte daca s, i numai daca nu existaun ciclu ın G [ın] care sa [se] cont, ina aceasta muchie.
Demonstrat, ie; Necesitatea.Fie e ∈ E(G) o punte ın G atunci G − e cont, ine mai multe componentedecıt G.Adica exista cel put, in doua vırfuri u s, i v care-s conexe ın G, dar nu s, i ınG − e.Acest fapt implica existent, a unui uv-lant, P care trece prin e (de fapt toateuv-lant, urile trec prin e).Notam prin x s, i y capetele muchiei e s, i consideram ca x precede y ın P.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 23 / 26
Punt, i; Cicluri
Demonstrat, ie; Necesitatea; Continuare.As, adar ın G − e vırful u este conectat cu x printr-o sect, iune a lui P s, i yeste conectat cu v prin alta sect, iune a lui P.Daca ın G ar fi existat un ciclu C care ar cont, ine muchia e atunci x s, i y arfi conectat, i ın G − e prin lant, ul C − e s, i respectiv u s, i v ar fi conectat, i ınG − e.Am obt, inut o contradict, ie.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 24 / 26
Punt, i; Cicluri
Demonstrat, ie; Necesitatea; Continuare.As, adar ın G − e vırful u este conectat cu x printr-o sect, iune a lui P s, i yeste conectat cu v prin alta sect, iune a lui P.Daca ın G ar fi existat un ciclu C care ar cont, ine muchia e atunci x s, i y arfi conectat, i ın G − e prin lant, ul C − e s, i respectiv u s, i v ar fi conectat, i ınG − e.Am obt, inut o contradict, ie.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 24 / 26
Punt, i; Cicluri
Demonstrat, ie; Necesitatea; Continuare.As, adar ın G − e vırful u este conectat cu x printr-o sect, iune a lui P s, i yeste conectat cu v prin alta sect, iune a lui P.Daca ın G ar fi existat un ciclu C care ar cont, ine muchia e atunci x s, i y arfi conectat, i ın G − e prin lant, ul C − e s, i respectiv u s, i v ar fi conectat, i ınG − e.Am obt, inut o contradict, ie.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 24 / 26
Punt, i; Cicluri
Demonstrat, ie; Suficient, a.Vom demonstra implicat, ia inversa, adica daca e nu este punte atunci ea secont, ine ıntr-un ciclu.Presupunem ca e nu este punte, atunci G − e are acelas, i numar decomponente ca s, i G.Notınd prin x s, i y capetele muchiei e reiese ca x s, i y sınt conectate ınG − e.Adica exista un xy-lant, P ın G − e.Atunci e se cont, ine ın ciclul P + e din G.Presupunem ca teorema este adevarata pentru orice doua vırfuri ladistant, a mai mica decıt k.Fie u, v doua vırfuri la distant, a k.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 25 / 26
Punt, i; Cicluri
Demonstrat, ie; Suficient, a.Vom demonstra implicat, ia inversa, adica daca e nu este punte atunci ea secont, ine ıntr-un ciclu.Presupunem ca e nu este punte, atunci G − e are acelas, i numar decomponente ca s, i G.Notınd prin x s, i y capetele muchiei e reiese ca x s, i y sınt conectate ınG − e.Adica exista un xy-lant, P ın G − e.Atunci e se cont, ine ın ciclul P + e din G.Presupunem ca teorema este adevarata pentru orice doua vırfuri ladistant, a mai mica decıt k.Fie u, v doua vırfuri la distant, a k.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 25 / 26
Punt, i; Cicluri
Demonstrat, ie; Suficient, a.Vom demonstra implicat, ia inversa, adica daca e nu este punte atunci ea secont, ine ıntr-un ciclu.Presupunem ca e nu este punte, atunci G − e are acelas, i numar decomponente ca s, i G.Notınd prin x s, i y capetele muchiei e reiese ca x s, i y sınt conectate ınG − e.Adica exista un xy-lant, P ın G − e.Atunci e se cont, ine ın ciclul P + e din G.Presupunem ca teorema este adevarata pentru orice doua vırfuri ladistant, a mai mica decıt k.Fie u, v doua vırfuri la distant, a k.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 25 / 26
Punt, i; Cicluri
Demonstrat, ie; Suficient, a.Vom demonstra implicat, ia inversa, adica daca e nu este punte atunci ea secont, ine ıntr-un ciclu.Presupunem ca e nu este punte, atunci G − e are acelas, i numar decomponente ca s, i G.Notınd prin x s, i y capetele muchiei e reiese ca x s, i y sınt conectate ınG − e.Adica exista un xy-lant, P ın G − e.Atunci e se cont, ine ın ciclul P + e din G.Presupunem ca teorema este adevarata pentru orice doua vırfuri ladistant, a mai mica decıt k.Fie u, v doua vırfuri la distant, a k.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 25 / 26
Punt, i; Cicluri
Demonstrat, ie; Suficient, a.Vom demonstra implicat, ia inversa, adica daca e nu este punte atunci ea secont, ine ıntr-un ciclu.Presupunem ca e nu este punte, atunci G − e are acelas, i numar decomponente ca s, i G.Notınd prin x s, i y capetele muchiei e reiese ca x s, i y sınt conectate ınG − e.Adica exista un xy-lant, P ın G − e.Atunci e se cont, ine ın ciclul P + e din G.Presupunem ca teorema este adevarata pentru orice doua vırfuri ladistant, a mai mica decıt k.Fie u, v doua vırfuri la distant, a k.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 25 / 26
Punt, i; Cicluri
Demonstrat, ie; Suficient, a.Vom demonstra implicat, ia inversa, adica daca e nu este punte atunci ea secont, ine ıntr-un ciclu.Presupunem ca e nu este punte, atunci G − e are acelas, i numar decomponente ca s, i G.Notınd prin x s, i y capetele muchiei e reiese ca x s, i y sınt conectate ınG − e.Adica exista un xy-lant, P ın G − e.Atunci e se cont, ine ın ciclul P + e din G.Presupunem ca teorema este adevarata pentru orice doua vırfuri ladistant, a mai mica decıt k.Fie u, v doua vırfuri la distant, a k.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 25 / 26
Punt, i; Cicluri
Demonstrat, ie; Suficient, a.Vom demonstra implicat, ia inversa, adica daca e nu este punte atunci ea secont, ine ıntr-un ciclu.Presupunem ca e nu este punte, atunci G − e are acelas, i numar decomponente ca s, i G.Notınd prin x s, i y capetele muchiei e reiese ca x s, i y sınt conectate ınG − e.Adica exista un xy-lant, P ın G − e.Atunci e se cont, ine ın ciclul P + e din G.Presupunem ca teorema este adevarata pentru orice doua vırfuri ladistant, a mai mica decıt k.Fie u, v doua vırfuri la distant, a k.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 25 / 26
Demonstrat, ie; Suficient, a; Continuare.Adica ıntre ele exista un k-lant, P.Fie w un vırf din P care precede v.Atunci d(u, w) = k − 1 s, i deci ıntre u s, i w exista doua lant, uriindependente P s, i Q.Deoarece G este 2-conex reiese ca daca eliminam w graful ramıne conex s, ideci ıntre u s, i v exista un lant, P ′ ın G − w.Acum daca P ′ nu intersecteaza nici P nici Q teorema este demonstrata.Deaceea presupunem fara a pierde din generalitate ca V (P ′) ∩V (P) = xs, i deci iata lant, urile independente cautate: primul: u, sect, iunea din P dela u spre x, x, sect, iunea din P ′ de la x spre v, v.Al doilea: Q ımpreuna cu wv.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 26 / 26
Demonstrat, ie; Suficient, a; Continuare.Adica ıntre ele exista un k-lant, P.Fie w un vırf din P care precede v.Atunci d(u, w) = k − 1 s, i deci ıntre u s, i w exista doua lant, uriindependente P s, i Q.Deoarece G este 2-conex reiese ca daca eliminam w graful ramıne conex s, ideci ıntre u s, i v exista un lant, P ′ ın G − w.Acum daca P ′ nu intersecteaza nici P nici Q teorema este demonstrata.Deaceea presupunem fara a pierde din generalitate ca V (P ′) ∩V (P) = xs, i deci iata lant, urile independente cautate: primul: u, sect, iunea din P dela u spre x, x, sect, iunea din P ′ de la x spre v, v.Al doilea: Q ımpreuna cu wv.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 26 / 26
Demonstrat, ie; Suficient, a; Continuare.Adica ıntre ele exista un k-lant, P.Fie w un vırf din P care precede v.Atunci d(u, w) = k − 1 s, i deci ıntre u s, i w exista doua lant, uriindependente P s, i Q.Deoarece G este 2-conex reiese ca daca eliminam w graful ramıne conex s, ideci ıntre u s, i v exista un lant, P ′ ın G − w.Acum daca P ′ nu intersecteaza nici P nici Q teorema este demonstrata.Deaceea presupunem fara a pierde din generalitate ca V (P ′) ∩V (P) = xs, i deci iata lant, urile independente cautate: primul: u, sect, iunea din P dela u spre x, x, sect, iunea din P ′ de la x spre v, v.Al doilea: Q ımpreuna cu wv.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 26 / 26
Demonstrat, ie; Suficient, a; Continuare.Adica ıntre ele exista un k-lant, P.Fie w un vırf din P care precede v.Atunci d(u, w) = k − 1 s, i deci ıntre u s, i w exista doua lant, uriindependente P s, i Q.Deoarece G este 2-conex reiese ca daca eliminam w graful ramıne conex s, ideci ıntre u s, i v exista un lant, P ′ ın G − w.Acum daca P ′ nu intersecteaza nici P nici Q teorema este demonstrata.Deaceea presupunem fara a pierde din generalitate ca V (P ′) ∩V (P) = xs, i deci iata lant, urile independente cautate: primul: u, sect, iunea din P dela u spre x, x, sect, iunea din P ′ de la x spre v, v.Al doilea: Q ımpreuna cu wv.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 26 / 26
Demonstrat, ie; Suficient, a; Continuare.Adica ıntre ele exista un k-lant, P.Fie w un vırf din P care precede v.Atunci d(u, w) = k − 1 s, i deci ıntre u s, i w exista doua lant, uriindependente P s, i Q.Deoarece G este 2-conex reiese ca daca eliminam w graful ramıne conex s, ideci ıntre u s, i v exista un lant, P ′ ın G − w.Acum daca P ′ nu intersecteaza nici P nici Q teorema este demonstrata.Deaceea presupunem fara a pierde din generalitate ca V (P ′) ∩V (P) = xs, i deci iata lant, urile independente cautate: primul: u, sect, iunea din P dela u spre x, x, sect, iunea din P ′ de la x spre v, v.Al doilea: Q ımpreuna cu wv.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 26 / 26
Demonstrat, ie; Suficient, a; Continuare.Adica ıntre ele exista un k-lant, P.Fie w un vırf din P care precede v.Atunci d(u, w) = k − 1 s, i deci ıntre u s, i w exista doua lant, uriindependente P s, i Q.Deoarece G este 2-conex reiese ca daca eliminam w graful ramıne conex s, ideci ıntre u s, i v exista un lant, P ′ ın G − w.Acum daca P ′ nu intersecteaza nici P nici Q teorema este demonstrata.Deaceea presupunem fara a pierde din generalitate ca V (P ′) ∩V (P) = xs, i deci iata lant, urile independente cautate: primul: u, sect, iunea din P dela u spre x, x, sect, iunea din P ′ de la x spre v, v.Al doilea: Q ımpreuna cu wv.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 26 / 26
Demonstrat, ie; Suficient, a; Continuare.Adica ıntre ele exista un k-lant, P.Fie w un vırf din P care precede v.Atunci d(u, w) = k − 1 s, i deci ıntre u s, i w exista doua lant, uriindependente P s, i Q.Deoarece G este 2-conex reiese ca daca eliminam w graful ramıne conex s, ideci ıntre u s, i v exista un lant, P ′ ın G − w.Acum daca P ′ nu intersecteaza nici P nici Q teorema este demonstrata.Deaceea presupunem fara a pierde din generalitate ca V (P ′) ∩V (P) = xs, i deci iata lant, urile independente cautate: primul: u, sect, iunea din P dela u spre x, x, sect, iunea din P ′ de la x spre v, v.Al doilea: Q ımpreuna cu wv.
R. Dumbraveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat,ii Balt,i, 2013 26 / 26