curs 5: conexitate

of 87 /87
Curs 5: Conexitate 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) Conexitate alt , i, 2013 1/1

Upload: radu-dumbraveanu

Post on 20-Jul-2015

307 views

Category:

Education


2 download

TRANSCRIPT

Page 1: Curs 5: Conexitate

Curs 5: ConexitateTeoria 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) Conexitate Balt,i, 2013 1 / 1

Page 2: Curs 5: Conexitate

Mult, imi separatoare

Fiind dat un graf G, o mult, ime U ⊆ V (G) se numes, te mult, imeseparatoare de vırfuri (sau mult, ime de articulare) daca G −U are maimulte componenete conexe decıt G.

Daca se cunoas, te ca |U | = k atunci U se numes, te k-mult, imeseparatoare de vırfuri (sau k-mult, ime de articulare).

Daca k = 1, adica U = {v}, atunci v se numes, te vırf de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 2 / 1

Page 3: Curs 5: Conexitate

Mult, imi separatoare

Fiind dat un graf G, o mult, ime U ⊆ V (G) se numes, te mult, imeseparatoare de vırfuri (sau mult, ime de articulare) daca G −U are maimulte componenete conexe decıt G.

Daca se cunoas, te ca |U | = k atunci U se numes, te k-mult, imeseparatoare de vırfuri (sau k-mult, ime de articulare).

Daca k = 1, adica U = {v}, atunci v se numes, te vırf de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 2 / 1

Page 4: Curs 5: Conexitate

Mult, imi separatoare

Fiind dat un graf G, o mult, ime U ⊆ V (G) se numes, te mult, imeseparatoare de vırfuri (sau mult, ime de articulare) daca G −U are maimulte componenete conexe decıt G.

Daca se cunoas, te ca |U | = k atunci U se numes, te k-mult, imeseparatoare de vırfuri (sau k-mult, ime de articulare).

Daca k = 1, adica U = {v}, atunci v se numes, te vırf de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 2 / 1

Page 5: Curs 5: Conexitate

Mult, imi separatoare

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 3 / 1

Page 6: Curs 5: Conexitate

Mult, imi separatoare

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 3 / 1

Page 7: Curs 5: Conexitate

Mult, imi separatoare

Vırfurile albe (graful din stınga) formeaza o 4-mult, ime de articulare. Suprimındaceste vırfuri obt, inem un graf (din dreapta) cu patru componenet conexe.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 3 / 1

Page 8: Curs 5: Conexitate

Mult, imi separatoare

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 3 / 1

Page 9: Curs 5: Conexitate

Mult, imi separatoare

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 3 / 1

Page 10: Curs 5: Conexitate

Mult, imi separatoare

Suprimarea vırfului alb (stınga) rezulta ıntr-un graf (dreapta) cu opt componenteconexe. Cu s, apte componente mai mult decıt cel din stınga. Vırful alb este un

vırf de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 3 / 1

Page 11: Curs 5: Conexitate

Mult, imi separatoare

As, adar printre grafurile conexe sınt grafuri care pot fi “rupte” doar prinsuprimarea unui vırf sau a doua vırfuri, iar ın altele pentru a le “rupe” estenevoie de a ınlatura mai multe vırfuri.

Un fel de “grad al conexitat, ii”.

Not, iunea de k-conexitate

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 4 / 1

Page 12: Curs 5: Conexitate

Mult, imi separatoare

As, adar printre grafurile conexe sınt grafuri care pot fi “rupte” doar prinsuprimarea unui vırf sau a doua vırfuri, iar ın altele pentru a le “rupe” estenevoie de a ınlatura mai multe vırfuri.

Un fel de “grad al conexitat, ii”.

Not, iunea de k-conexitate

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 4 / 1

Page 13: Curs 5: Conexitate

Mult, imi separatoare

As, adar printre grafurile conexe sınt grafuri care pot fi “rupte” doar prinsuprimarea unui vırf sau a doua vırfuri, iar ın altele pentru a le “rupe” estenevoie de a ınlatura mai multe vırfuri.

Un fel de “grad al conexitat, ii”.

Not, iunea de k-conexitate

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 4 / 1

Page 14: Curs 5: Conexitate

k-conexitate

Un graf G este k-conex, k ∈ N, daca:

I |G| > k;I G −U este conex pentru orice U ⊆ V cu |U | < k.

Cu alte cuvinte un graf este k-conex daca are mai mult de k vırfuri s, i nuexista mult, imi de articulare cu mai put, in de k vırfuri.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 5 / 1

Page 15: Curs 5: Conexitate

k-conexitate

Un graf G este k-conex, k ∈ N, daca:

I |G| > k;I G −U este conex pentru orice U ⊆ V cu |U | < k.

Cu alte cuvinte un graf este k-conex daca are mai mult de k vırfuri s, i nuexista mult, imi de articulare cu mai put, in de k vırfuri.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 5 / 1

Page 16: Curs 5: Conexitate

Exemplu: graful W9

s

tu

v

w

xy

z

p

I W9 Cont, ine vırfuri de articulare?I Nu;I Deci este 2-conex.

I W9 Cont, ine 2-mult, imi de articulare?I Nu;I Deci este 3-conex.

I W9 Cont, ine 3-mult, imi de articulare?I Da, de exemplu, {p, v, t};I Deci nu este 4-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 6 / 1

Page 17: Curs 5: Conexitate

Exemplu: graful W9

s

tu

v

w

xy

z

p

I W9 Cont, ine vırfuri de articulare?I Nu;I Deci este 2-conex.

I W9 Cont, ine 2-mult, imi de articulare?I Nu;I Deci este 3-conex.

I W9 Cont, ine 3-mult, imi de articulare?I Da, de exemplu, {p, v, t};I Deci nu este 4-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 6 / 1

Page 18: Curs 5: Conexitate

Exemplu: graful W9

s

tu

v

w

xy

z

p

I W9 Cont, ine vırfuri de articulare?I Nu;I Deci este 2-conex.

I W9 Cont, ine 2-mult, imi de articulare?I Nu;I Deci este 3-conex.

I W9 Cont, ine 3-mult, imi de articulare?I Da, de exemplu, {p, v, t};I Deci nu este 4-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 6 / 1

Page 19: Curs 5: Conexitate

Exemplu: graful W9

s

tu

v

w

xy

z

p

I W9 Cont, ine vırfuri de articulare?I Nu;I Deci este 2-conex.

I W9 Cont, ine 2-mult, imi de articulare?I Nu;I Deci este 3-conex.

I W9 Cont, ine 3-mult, imi de articulare?I Da, de exemplu, {p, v, t};I Deci nu este 4-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 6 / 1

Page 20: Curs 5: Conexitate

Exemplu: graful W9

s

tu

v

w

xy

z

p

I W9 Cont, ine vırfuri de articulare?I Nu;I Deci este 2-conex.

I W9 Cont, ine 2-mult, imi de articulare?I Nu;I Deci este 3-conex.

I W9 Cont, ine 3-mult, imi de articulare?I Da, de exemplu, {p, v, t};I Deci nu este 4-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 6 / 1

Page 21: Curs 5: Conexitate

Exemplu: graful W9

s

tu

v

w

xy

z

p

I W9 Cont, ine vırfuri de articulare?I Nu;I Deci este 2-conex.

I W9 Cont, ine 2-mult, imi de articulare?I Nu;I Deci este 3-conex.

I W9 Cont, ine 3-mult, imi de articulare?I Da, de exemplu, {p, v, t};I Deci nu este 4-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 6 / 1

Page 22: Curs 5: Conexitate

Exemplu: graful W9

s

tu

v

w

xy

z

p

I W9 Cont, ine vırfuri de articulare?I Nu;I Deci este 2-conex.

I W9 Cont, ine 2-mult, imi de articulare?I Nu;I Deci este 3-conex.

I W9 Cont, ine 3-mult, imi de articulare?I Da, de exemplu, {p, v, t};I Deci nu este 4-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 6 / 1

Page 23: Curs 5: Conexitate

Exemplu: graful W9

s

tu

v

w

xy

z

p

I W9 Cont, ine vırfuri de articulare?I Nu;I Deci este 2-conex.

I W9 Cont, ine 2-mult, imi de articulare?I Nu;I Deci este 3-conex.

I W9 Cont, ine 3-mult, imi de articulare?I Da, de exemplu, {p, v, t};I Deci nu este 4-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 6 / 1

Page 24: Curs 5: Conexitate

Exemplu: graful W9

s

tu

v

w

xy

z

p

I W9 Cont, ine vırfuri de articulare?I Nu;I Deci este 2-conex.

I W9 Cont, ine 2-mult, imi de articulare?I Nu;I Deci este 3-conex.

I W9 Cont, ine 3-mult, imi de articulare?I Da, de exemplu, {p, v, t};I Deci nu este 4-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 6 / 1

Page 25: Curs 5: Conexitate

W13 este 3-conex, dar nu s, i 4-conex C7 este 2-conex, dar nu s, i 3-conex

S9 este ???-conex, dar nu s, i ???-conex K9 este ???-conex, dar nu s, i ???-conex

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 7 / 1

Page 26: Curs 5: Conexitate

W13 este 3-conex, dar nu s, i 4-conex C7 este 2-conex, dar nu s, i 3-conex

S9 este ???-conex, dar nu s, i ???-conex K9 este ???-conex, dar nu s, i ???-conex

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 7 / 1

Page 27: Curs 5: Conexitate

W13 este 3-conex, dar nu s, i 4-conex C7 este 2-conex, dar nu s, i 3-conex

S9 este ???-conex, dar nu s, i ???-conex K9 este ???-conex, dar nu s, i ???-conex

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 7 / 1

Page 28: Curs 5: Conexitate

W13 este 3-conex, dar nu s, i 4-conex C7 este 2-conex, dar nu s, i 3-conex

S9 este ???-conex, dar nu s, i ???-conex K9 este ???-conex, dar nu s, i ???-conex

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 7 / 1

Page 29: Curs 5: Conexitate

Exemple extremale

Ce putem spune despre Kn?Dar despre Nn?

Exista grafuri 0-conexe?Care grafuri sınt 1-conexe?

Pentru a raspunde aceste ıntrebari vom considera negat, ia condit, iilor dindefinit, ia k-conexitat, ii s, i anume:

Un graf G nu este k-conex daca:

I |G| ≤ k sauI exista U ⊆ V ıncıt |U | < k s, i G −U nu este conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 8 / 1

Page 30: Curs 5: Conexitate

Exemple extremale

Ce putem spune despre Kn?Dar despre Nn?

Exista grafuri 0-conexe?Care grafuri sınt 1-conexe?

Pentru a raspunde aceste ıntrebari vom considera negat, ia condit, iilor dindefinit, ia k-conexitat, ii s, i anume:

Un graf G nu este k-conex daca:

I |G| ≤ k sauI exista U ⊆ V ıncıt |U | < k s, i G −U nu este conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 8 / 1

Page 31: Curs 5: Conexitate

Exemple extremale

Ce putem spune despre Kn?Dar despre Nn?

Exista grafuri 0-conexe?Care grafuri sınt 1-conexe?

Pentru a raspunde aceste ıntrebari vom considera negat, ia condit, iilor dindefinit, ia k-conexitat, ii s, i anume:

Un graf G nu este k-conex daca:

I |G| ≤ k sauI exista U ⊆ V ıncıt |U | < k s, i G −U nu este conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 8 / 1

Page 32: Curs 5: Conexitate

Exemple extremale

Ce putem spune despre Kn?Dar despre Nn?

Exista grafuri 0-conexe?Care grafuri sınt 1-conexe?

Pentru a raspunde aceste ıntrebari vom considera negat, ia condit, iilor dindefinit, ia k-conexitat, ii s, i anume:

Un graf G nu este k-conex daca:

I |G| ≤ k sauI exista U ⊆ V ıncıt |U | < k s, i G −U nu este conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 8 / 1

Page 33: Curs 5: Conexitate

Exemple extremale

Ce putem spune despre Kn?Dar despre Nn?

Exista grafuri 0-conexe?Care grafuri sınt 1-conexe?

Pentru a raspunde aceste ıntrebari vom considera negat, ia condit, iilor dindefinit, ia k-conexitat, ii s, i anume:

Un graf G nu este k-conex daca:

I |G| ≤ k sauI exista U ⊆ V ıncıt |U | < k s, i G −U nu este conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 8 / 1

Page 34: Curs 5: Conexitate

Exemple extremale

Ce putem spune despre Kn?Dar despre Nn?

Exista grafuri 0-conexe?Care grafuri sınt 1-conexe?

Pentru a raspunde aceste ıntrebari vom considera negat, ia condit, iilor dindefinit, ia k-conexitat, ii s, i anume:

Un graf G nu este k-conex daca:

I |G| ≤ k sauI exista U ⊆ V ıncıt |U | < k s, i G −U nu este conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 8 / 1

Page 35: Curs 5: Conexitate

Exemple extremale

I Kn este este 1-conex, 2-conex, ... s, i (n − 1)-conex;I Insa Kn nu este n-conex deoarce |Kn| 6> n.

I Sn , n ≥ 2, este 1-conex;I Sn nu este 2-conex ıntrucıt are vırfuri de articulare (de fapt doar unul).

I N1 este 0-conex (ıncercat, i sa utilizat, i negat, ia definit, iei pentru a arataca nu este 0-conex);

I N1 nu este 1-conex.I Nn este 0-conex;I Graful ∅ nu este k-conex pentru niciun k ∈ N.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 9 / 1

Page 36: Curs 5: Conexitate

Exemple extremale

I Kn este este 1-conex, 2-conex, ... s, i (n − 1)-conex;I Insa Kn nu este n-conex deoarce |Kn| 6> n.

I Sn , n ≥ 2, este 1-conex;I Sn nu este 2-conex ıntrucıt are vırfuri de articulare (de fapt doar unul).

I N1 este 0-conex (ıncercat, i sa utilizat, i negat, ia definit, iei pentru a arataca nu este 0-conex);

I N1 nu este 1-conex.I Nn este 0-conex;I Graful ∅ nu este k-conex pentru niciun k ∈ N.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 9 / 1

Page 37: Curs 5: Conexitate

Exemple extremale

I Kn este este 1-conex, 2-conex, ... s, i (n − 1)-conex;I Insa Kn nu este n-conex deoarce |Kn| 6> n.

I Sn , n ≥ 2, este 1-conex;I Sn nu este 2-conex ıntrucıt are vırfuri de articulare (de fapt doar unul).

I N1 este 0-conex (ıncercat, i sa utilizat, i negat, ia definit, iei pentru a arataca nu este 0-conex);

I N1 nu este 1-conex.I Nn este 0-conex;I Graful ∅ nu este k-conex pentru niciun k ∈ N.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 9 / 1

Page 38: Curs 5: Conexitate

Exemple extremale

I Kn este este 1-conex, 2-conex, ... s, i (n − 1)-conex;I Insa Kn nu este n-conex deoarce |Kn| 6> n.

I Sn , n ≥ 2, este 1-conex;I Sn nu este 2-conex ıntrucıt are vırfuri de articulare (de fapt doar unul).

I N1 este 0-conex (ıncercat, i sa utilizat, i negat, ia definit, iei pentru a arataca nu este 0-conex);

I N1 nu este 1-conex.I Nn este 0-conex;I Graful ∅ nu este k-conex pentru niciun k ∈ N.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 9 / 1

Page 39: Curs 5: Conexitate

Exemple extremale

I Kn este este 1-conex, 2-conex, ... s, i (n − 1)-conex;I Insa Kn nu este n-conex deoarce |Kn| 6> n.

I Sn , n ≥ 2, este 1-conex;I Sn nu este 2-conex ıntrucıt are vırfuri de articulare (de fapt doar unul).

I N1 este 0-conex (ıncercat, i sa utilizat, i negat, ia definit, iei pentru a arataca nu este 0-conex);

I N1 nu este 1-conex.I Nn este 0-conex;I Graful ∅ nu este k-conex pentru niciun k ∈ N.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 9 / 1

Page 40: Curs 5: Conexitate

Exemple extremale

I Kn este este 1-conex, 2-conex, ... s, i (n − 1)-conex;I Insa Kn nu este n-conex deoarce |Kn| 6> n.

I Sn , n ≥ 2, este 1-conex;I Sn nu este 2-conex ıntrucıt are vırfuri de articulare (de fapt doar unul).

I N1 este 0-conex (ıncercat, i sa utilizat, i negat, ia definit, iei pentru a arataca nu este 0-conex);

I N1 nu este 1-conex.I Nn este 0-conex;I Graful ∅ nu este k-conex pentru niciun k ∈ N.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 9 / 1

Page 41: Curs 5: Conexitate

Exemple extremale

I Kn este este 1-conex, 2-conex, ... s, i (n − 1)-conex;I Insa Kn nu este n-conex deoarce |Kn| 6> n.

I Sn , n ≥ 2, este 1-conex;I Sn nu este 2-conex ıntrucıt are vırfuri de articulare (de fapt doar unul).

I N1 este 0-conex (ıncercat, i sa utilizat, i negat, ia definit, iei pentru a arataca nu este 0-conex);

I N1 nu este 1-conex.I Nn este 0-conex;I Graful ∅ nu este k-conex pentru niciun k ∈ N.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 9 / 1

Page 42: Curs 5: Conexitate

Exemple extremale

I Kn este este 1-conex, 2-conex, ... s, i (n − 1)-conex;I Insa Kn nu este n-conex deoarce |Kn| 6> n.

I Sn , n ≥ 2, este 1-conex;I Sn nu este 2-conex ıntrucıt are vırfuri de articulare (de fapt doar unul).

I N1 este 0-conex (ıncercat, i sa utilizat, i negat, ia definit, iei pentru a arataca nu este 0-conex);

I N1 nu este 1-conex.I Nn este 0-conex;I Graful ∅ nu este k-conex pentru niciun k ∈ N.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 9 / 1

Page 43: Curs 5: Conexitate

Exemple extremale; Concluzii

I Orice graf conex netrivial este 1-conex.I Un graf netrivial este 1-conex doar daca este conex.

I Orice graf neconex s, i nevid este 0-conex.I Orice graf nevid este 0-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 10 / 1

Page 44: Curs 5: Conexitate

Exemple extremale; Concluzii

I Orice graf conex netrivial este 1-conex.I Un graf netrivial este 1-conex doar daca este conex.

I Orice graf neconex s, i nevid este 0-conex.I Orice graf nevid este 0-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 10 / 1

Page 45: Curs 5: Conexitate

Exemple extremale; Concluzii

I Orice graf conex netrivial este 1-conex.I Un graf netrivial este 1-conex doar daca este conex.

I Orice graf neconex s, i nevid este 0-conex.I Orice graf nevid este 0-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 10 / 1

Page 46: Curs 5: Conexitate

Exemple extremale; Concluzii

I Orice graf conex netrivial este 1-conex.I Un graf netrivial este 1-conex doar daca este conex.

I Orice graf neconex s, i nevid este 0-conex.I Orice graf nevid este 0-conex.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 10 / 1

Page 47: Curs 5: Conexitate

Numar de conexiune

Cel mai mare numar k ∈ N pentru care G este k-conex se numes, teconexitatea (sau numar de conexiune a) grafului s, i se noteaza prink(G).

As, adar:

I k(Kn) = n − 1;I k(G) = 0 daca s, i numai daca G nu este conex sau |G| ≤ 1;I k(G) = 1 daca G are vırfuri de articulare;I k(G) ≥ 2 daca G nua re vırfuri de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 11 / 1

Page 48: Curs 5: Conexitate

Numar de conexiune

Cel mai mare numar k ∈ N pentru care G este k-conex se numes, teconexitatea (sau numar de conexiune a) grafului s, i se noteaza prink(G).

As, adar:

I k(Kn) = n − 1;I k(G) = 0 daca s, i numai daca G nu este conex sau |G| ≤ 1;I k(G) = 1 daca G are vırfuri de articulare;I k(G) ≥ 2 daca G nua re vırfuri de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 11 / 1

Page 49: Curs 5: Conexitate

Numar de conexiune

Cel mai mare numar k ∈ N pentru care G este k-conex se numes, teconexitatea (sau numar de conexiune a) grafului s, i se noteaza prink(G).

As, adar:

I k(Kn) = n − 1;I k(G) = 0 daca s, i numai daca G nu este conex sau |G| ≤ 1;I k(G) = 1 daca G are vırfuri de articulare;I k(G) ≥ 2 daca G nua re vırfuri de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 11 / 1

Page 50: Curs 5: Conexitate

Numar de conexiune

Cel mai mare numar k ∈ N pentru care G este k-conex se numes, teconexitatea (sau numar de conexiune a) grafului s, i se noteaza prink(G).

As, adar:

I k(Kn) = n − 1;I k(G) = 0 daca s, i numai daca G nu este conex sau |G| ≤ 1;I k(G) = 1 daca G are vırfuri de articulare;I k(G) ≥ 2 daca G nua re vırfuri de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 11 / 1

Page 51: Curs 5: Conexitate

Numar de conexiune

Cel mai mare numar k ∈ N pentru care G este k-conex se numes, teconexitatea (sau numar de conexiune a) grafului s, i se noteaza prink(G).

As, adar:

I k(Kn) = n − 1;I k(G) = 0 daca s, i numai daca G nu este conex sau |G| ≤ 1;I k(G) = 1 daca G are vırfuri de articulare;I k(G) ≥ 2 daca G nua re vırfuri de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 11 / 1

Page 52: Curs 5: Conexitate

Mult, imi separatoare

Fiind dat un graf G, o mult, ime F ⊆ E(G) se numes, te mult, imeseparatoare de muchii daca G − F are mai multe componenete conexedecıt G.

Daca se cunoas, te ca |F | = k atunci F se numes, te k-mult, imeseparatoare de muchii.

Daca k = 1, adica F = {e}, atunci e se numes, te punte.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 12 / 1

Page 53: Curs 5: Conexitate

Mult, imi separatoare

Fiind dat un graf G, o mult, ime F ⊆ E(G) se numes, te mult, imeseparatoare de muchii daca G − F are mai multe componenete conexedecıt G.

Daca se cunoas, te ca |F | = k atunci F se numes, te k-mult, imeseparatoare de muchii.

Daca k = 1, adica F = {e}, atunci e se numes, te punte.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 12 / 1

Page 54: Curs 5: Conexitate

Mult, imi separatoare

Fiind dat un graf G, o mult, ime F ⊆ E(G) se numes, te mult, imeseparatoare de muchii daca G − F are mai multe componenete conexedecıt G.

Daca se cunoas, te ca |F | = k atunci F se numes, te k-mult, imeseparatoare de muchii.

Daca k = 1, adica F = {e}, atunci e se numes, te punte.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 12 / 1

Page 55: Curs 5: Conexitate

Mult, imi separatoare

Fiind dat un graf G, o mult, ime F ⊆ E(G) se numes, te mult, imeseparatoare de muchii daca G − F are mai multe componenete conexedecıt G.

Daca se cunoas, te ca |F | = k atunci F se numes, te k-mult, imeseparatoare de muchii.

Daca k = 1, adica F = {e}, atunci e se numes, te punte.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 12 / 1

Page 56: Curs 5: Conexitate

λ-muchie-conexitate

Un graf G se numes, te λ-muchie-conex, λ ∈ N, daca:

I |G| > 1;I G − F este conex pentru orice F ⊆ E cu |F | < λ.

Cu alte cuvinte G este λ-muchie-conex daca nu este trivial s, i nu cont, inemult, imi separatoare de muchii din mai put, in de λ elemente.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 13 / 1

Page 57: Curs 5: Conexitate

λ-muchie-conexitate

Un graf G se numes, te λ-muchie-conex, λ ∈ N, daca:

I |G| > 1;I G − F este conex pentru orice F ⊆ E cu |F | < λ.

Cu alte cuvinte G este λ-muchie-conex daca nu este trivial s, i nu cont, inemult, imi separatoare de muchii din mai put, in de λ elemente.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 13 / 1

Page 58: Curs 5: Conexitate

Exemple

fe

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 14 / 1

Page 59: Curs 5: Conexitate

Exemple

fe

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 14 / 1

Page 60: Curs 5: Conexitate

Exemple

fe

Graf 2-muchie-conex (stınga), dar nu s, i 3-muchie-conex pentru ca dupasuprimarea muchiilor e s, i f devine neconex

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 14 / 1

Page 61: Curs 5: Conexitate

Numar de muchie-conexiune

Cel mai mare numar λ ∈ N pentru care G este λ-muchie-conex se numes, tenumar de muchie-conexiune a grafului G s, i se noteaza prin λ(G) (sauk ′(G)).

Din perspectiva “conexitat, ii muchie” conexitatea simpla se mai numes, te“conexitatea vırf”.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 15 / 1

Page 62: Curs 5: Conexitate

Numar de muchie-conexiune

Cel mai mare numar λ ∈ N pentru care G este λ-muchie-conex se numes, tenumar de muchie-conexiune a grafului G s, i se noteaza prin λ(G) (sauk ′(G)).

Din perspectiva “conexitat, ii muchie” conexitatea simpla se mai numes, te“conexitatea vırf”.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 15 / 1

Page 63: Curs 5: Conexitate

Exemple

λ(G) = 2, k(G) = 3

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 16 / 1

Page 64: Curs 5: Conexitate

Exemple

λ(G) = 2, k(G) = 3

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 16 / 1

Page 65: Curs 5: Conexitate

k(G) vs. λ(G)

TeoremaPentru orice graf G avem k(G) ≤ λ(G) ≤ δ(G)

Este evident ca λ(G) ≤ δ(G); daca la un vırf de gradul δ(G) ınlaturamtoate muchiile incidente cu acesta numarul de componente conexe vacres, te cu 1.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 17 / 1

Page 66: Curs 5: Conexitate

k(G) vs. λ(G)

TeoremaPentru orice graf G avem k(G) ≤ λ(G) ≤ δ(G)

Este evident ca λ(G) ≤ δ(G); daca la un vırf de gradul δ(G) ınlaturamtoate muchiile incidente cu acesta numarul de componente conexe vacres, te cu 1.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 17 / 1

Page 67: Curs 5: Conexitate

Grafuri 2-conexe

In cazul cınd un graf nu este conex acesta este format din mai multecomponente conexe.

Vrem sa extindem not, iunea de componenta conexa pentru grafurile carenu-s 2-conexe.

Adica, daca un graf nu este 2-conex atunci el consta din mai multe“componente 2-conexe”.

Analogul este conceptul de bloc:

Un bloc al unui graf este un subgraf maximal conex s, i fara vırfuri dearticulare.

Punctele de legatura ıntre blocurile unui graf sınt vırfurile de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 18 / 1

Page 68: Curs 5: Conexitate

Grafuri 2-conexe

In cazul cınd un graf nu este conex acesta este format din mai multecomponente conexe.

Vrem sa extindem not, iunea de componenta conexa pentru grafurile carenu-s 2-conexe.

Adica, daca un graf nu este 2-conex atunci el consta din mai multe“componente 2-conexe”.

Analogul este conceptul de bloc:

Un bloc al unui graf este un subgraf maximal conex s, i fara vırfuri dearticulare.

Punctele de legatura ıntre blocurile unui graf sınt vırfurile de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 18 / 1

Page 69: Curs 5: Conexitate

Grafuri 2-conexe

In cazul cınd un graf nu este conex acesta este format din mai multecomponente conexe.

Vrem sa extindem not, iunea de componenta conexa pentru grafurile carenu-s 2-conexe.

Adica, daca un graf nu este 2-conex atunci el consta din mai multe“componente 2-conexe”.

Analogul este conceptul de bloc:

Un bloc al unui graf este un subgraf maximal conex s, i fara vırfuri dearticulare.

Punctele de legatura ıntre blocurile unui graf sınt vırfurile de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 18 / 1

Page 70: Curs 5: Conexitate

Grafuri 2-conexe

In cazul cınd un graf nu este conex acesta este format din mai multecomponente conexe.

Vrem sa extindem not, iunea de componenta conexa pentru grafurile carenu-s 2-conexe.

Adica, daca un graf nu este 2-conex atunci el consta din mai multe“componente 2-conexe”.

Analogul este conceptul de bloc:

Un bloc al unui graf este un subgraf maximal conex s, i fara vırfuri dearticulare.

Punctele de legatura ıntre blocurile unui graf sınt vırfurile de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 18 / 1

Page 71: Curs 5: Conexitate

Grafuri 2-conexe

In cazul cınd un graf nu este conex acesta este format din mai multecomponente conexe.

Vrem sa extindem not, iunea de componenta conexa pentru grafurile carenu-s 2-conexe.

Adica, daca un graf nu este 2-conex atunci el consta din mai multe“componente 2-conexe”.

Analogul este conceptul de bloc:

Un bloc al unui graf este un subgraf maximal conex s, i fara vırfuri dearticulare.

Punctele de legatura ıntre blocurile unui graf sınt vırfurile de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 18 / 1

Page 72: Curs 5: Conexitate

Grafuri 2-conexe

In cazul cınd un graf nu este conex acesta este format din mai multecomponente conexe.

Vrem sa extindem not, iunea de componenta conexa pentru grafurile carenu-s 2-conexe.

Adica, daca un graf nu este 2-conex atunci el consta din mai multe“componente 2-conexe”.

Analogul este conceptul de bloc:

Un bloc al unui graf este un subgraf maximal conex s, i fara vırfuri dearticulare.

Punctele de legatura ıntre blocurile unui graf sınt vırfurile de articulare.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 18 / 1

Page 73: Curs 5: Conexitate

Exemplu

Blocurile acestui graf sınt:

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 19 / 1

Page 74: Curs 5: Conexitate

Exemplu

Blocurile acestui graf sınt:

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 19 / 1

Page 75: Curs 5: Conexitate

Exemplu

Blocurile acestui graf sınt:

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 19 / 1

Page 76: Curs 5: Conexitate

Blocuri

TeoremaPentru orice graf G orice cilcu part, ine ın ıntregime unui bloc.

Demonstratie.Orice ciclu este un subgraf conex s, i fara vırfuri de articulare.Deci apart, ine unui subgraf maximal cu acesta proprietate.Astfel de subgrafuri se numesc blocuri.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 20 / 1

Page 77: Curs 5: Conexitate

Blocuri

TeoremaPentru orice graf G orice cilcu part, ine ın ıntregime unui bloc.

Demonstratie.Orice ciclu este un subgraf conex s, i fara vırfuri de articulare.Deci apart, ine unui subgraf maximal cu acesta proprietate.Astfel de subgrafuri se numesc blocuri.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 20 / 1

Page 78: Curs 5: Conexitate

Blocuri

TeoremaFie G un graf conex cu cel put, in 3 vırfuri. Atunci urmatoarele sıntechivalente:

1. G este un bloc;2. Orice doua vırfuri din G apart, in unui ciclu comun;3. Orice vırf s, i muchie din G apart, in unui ciclu comun;4. Orice doua muchii din G apart, in unui ciclu comun;

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 21 / 1

Page 79: Curs 5: Conexitate

Ilustrare

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 22 / 1

Page 80: Curs 5: Conexitate

Teoremele Menger

Doua sau mai multe lant, uri se numesc independente daca au cel multdoua vırfuri comune - capetele.

Teorema (Menger 1927)[?] Fie G = (V ,E) un graf s, i U ,W ⊆ V . Atunci numarul minim devırfuri care separa U s, i W ın G este egal cu numarul maxim de(U ,W )-lant, uri independente.

Teorema (Menger 1932)[?] Un graf G cu |G| = n ≥ 3 este 2-conex daca s, i numai daca ıntre oricedoua vırfuri exista cel put, in doua lant, uri independente.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 23 / 1

Page 81: Curs 5: Conexitate

Teoremele Menger

Doua sau mai multe lant, uri se numesc independente daca au cel multdoua vırfuri comune - capetele.

Teorema (Menger 1927)[?] Fie G = (V ,E) un graf s, i U ,W ⊆ V . Atunci numarul minim devırfuri care separa U s, i W ın G este egal cu numarul maxim de(U ,W )-lant, uri independente.

Teorema (Menger 1932)[?] Un graf G cu |G| = n ≥ 3 este 2-conex daca s, i numai daca ıntre oricedoua vırfuri exista cel put, in doua lant, uri independente.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 23 / 1

Page 82: Curs 5: Conexitate

Teoremele Menger

Doua sau mai multe lant, uri se numesc independente daca au cel multdoua vırfuri comune - capetele.

Teorema (Menger 1927)[?] Fie G = (V ,E) un graf s, i U ,W ⊆ V . Atunci numarul minim devırfuri care separa U s, i W ın G este egal cu numarul maxim de(U ,W )-lant, uri independente.

Teorema (Menger 1932)[?] Un graf G cu |G| = n ≥ 3 este 2-conex daca s, i numai daca ıntre oricedoua vırfuri exista cel put, in doua lant, uri independente.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 23 / 1

Page 83: Curs 5: Conexitate

Demonstratie.Suficient, a. Daca ıntre orice doua vırfuri ale lui G exista cel put, in doualant, uri independente atunci nici un vırf al lui G nu poate fi vırf dearticulare. Deci G este 2-conex.Necesitatea. Fie G un graf 2-conex. Vom demonstra teorema prin induct, iepe distant, a d(v,w) dintre doua vırfuri v s, i w.Fie d(v,w) = 1, ıntrucıt G este 2-conex reiese ca v s, i w nu pot fi vırfuride articulare s, i evident muchia {v,w} nu poate fi punte, ceea cepresupune ca exista un ciclu C ın G care cont, ine muchia {v,w}. Iata celedoua lant, uri independente cautate: v,w s, i vCw.Presupunem ca teorema este adevarata pentru orice doua vırfuri cudistant, a mai mica decıt k ∈ N. Fie v s, i w doua vırfuri cu d(v,w) ≥ 2.Consideram un (v,w)-lant, de lungimea k s, i fie x un vırf care ıl precede pew ın acest lant, . Intrucıt d(v, x) < k, din ipoteza induct, iei, pentru acestedoua vırfuri exista doua lant, uri independente P s, i Q. Pe de alta parte,ıntrucıt G este 2-conex, G − x este conex s, i respectiv cont, ine un(v,w)-lant, P ′.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 24 / 1

Page 84: Curs 5: Conexitate

CorolarDaca G cu |G| = n ≥ 3 este 2-conex atunci pentru orice doua vırfuriexista un ciclu care le cont, ine.

CorolarDaca G este un bloc cu |G| = n ≥ 3 atunci pentru orice doua muchiiexista un ciclu care le cont, ine.

Demonstratie.Fie e1 s, i e2 doua muchii. Subdividem aceste doua muchii s, i notam vırfurilenoi prin v1 s, i v2. Graful nou la fel este bloc s, i deci putem aplica corolarulde mai sus. Adica exista un cilcu care cont, ine aceste doua vırfuri. Daraceste doua vırfuri nu alt, i vecini decıt extremitat, ile mucgiilor e1 s, i e2. Decis, i ele paart, in ciclului.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 25 / 1

Page 85: Curs 5: Conexitate

CorolarDaca G cu |G| = n ≥ 3 este 2-conex atunci pentru orice doua vırfuriexista un ciclu care le cont, ine.

CorolarDaca G este un bloc cu |G| = n ≥ 3 atunci pentru orice doua muchiiexista un ciclu care le cont, ine.

Demonstratie.Fie e1 s, i e2 doua muchii. Subdividem aceste doua muchii s, i notam vırfurilenoi prin v1 s, i v2. Graful nou la fel este bloc s, i deci putem aplica corolarulde mai sus. Adica exista un cilcu care cont, ine aceste doua vırfuri. Daraceste doua vırfuri nu alt, i vecini decıt extremitat, ile mucgiilor e1 s, i e2. Decis, i ele paart, in ciclului.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 25 / 1

Page 86: Curs 5: Conexitate

CorolarDaca G cu |G| = n ≥ 3 este 2-conex atunci pentru orice doua vırfuriexista un ciclu care le cont, ine.

CorolarDaca G este un bloc cu |G| = n ≥ 3 atunci pentru orice doua muchiiexista un ciclu care le cont, ine.

Demonstratie.Fie e1 s, i e2 doua muchii. Subdividem aceste doua muchii s, i notam vırfurilenoi prin v1 s, i v2. Graful nou la fel este bloc s, i deci putem aplica corolarulde mai sus. Adica exista un cilcu care cont, ine aceste doua vırfuri. Daraceste doua vırfuri nu alt, i vecini decıt extremitat, ile mucgiilor e1 s, i e2. Decis, i ele paart, in ciclului.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 25 / 1

Page 87: Curs 5: Conexitate

Teorema Menger; Versiunea globala

Teorema (Menger-Whitney)Daca |G| ≥ k + 1 este k-conex daca s, i numai daca orice doua vırfuri sıntunite prin cel put, in k lant, uri indepenedente.

R. Dumbraveanu (USARB) Conexitate Balt,i, 2013 26 / 1