curs 3: grafuri; subgrafuri; operații

72
Curs 3: Grafuri; Subgrafuri; Operat , ii Teoria grafurilor Radu Dumbr˘ aveanu Universitatea de Stat “A. Russo” din B˘ alt , i Facultatea de S , tiint , e Reale Aceast˘ a prezentare este pus˘ a la dispozit ¸ie sub Licent ¸a Atribuire - Distribuire-ˆ ın-condit ¸ii-identice 3.0 Ne-adaptat˘ a (CC BY-SA 3.0) alt , i, 2013 R. Dumbr˘ aveanu (USARB) Curs 3: Grafuri; Subgrafuri; Operat , ii alt , i, 2013 1 / 26

Upload: radu-dumbraveanu

Post on 20-Jul-2015

487 views

Category:

Education


3 download

TRANSCRIPT

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