Page 37 - MATINF Nr. 3

˘
ARTICOLE SI NOTE DE INFORMATICA
,

Grafuri neorientate 2-neconexe echilibrate

Ion Alexandru Popescu 1

ˆ
In acest articol ne propunem s˘a introducem un caz particular de graf neorientat numit graf
2-neconex echilibrat. Apoi vom prezenta cˆateva rezultate teoretice ˆımpreun˘a cu algoritmi ce
verific˘a anumite propriet˘at , i legate de aceast˘a categorie de grafuri neorientate.

Notiuni introductive
,

Definit , ia 1. Fie G = (X, U) un graf neorientat, X mult , imea nodurilor, iar U mult , imea
muchiilor. G se numes , te graf 2-neconex echilibrat dac˘a verific˘a urm˘atoarele propriet˘at , i:

1) G cont , ine exact dou˘a componente conexe G 1 = (X 1 , U 1 ), G 2 = (X 2 , U 2 );
2) card(X 1 ) = card(X 2 ).

Exemplul 1. Fie G = (X, U), cu X = {1, 2, 3, 4, 5, 6}, U = {[1, 3], [2, 6], [1, 5], [4, 6]}. G 1 =
(X 1 , U 1 ), X 1 = {1, 3, 5}, U 1 = {[1, 3], [1, 5]}. G 2 = (X 2 , U 2 ), X 2 = {2, 4, 6}, U 2 = {[2, 6], [4, 6]}.
G 1 s , i G 2 sunt componente conexe s , i card(X 1 ) = card(X 2 ) = 3. Astfel G verific˘a proriet˘at , ile 1),
ˆ
2) s , i este 2-neconex echilibrat. In Figura 1 este reprezentat grafic graful G.

1 3 2

5 4 4 6

Fig. 1: Exemplu de graf neorientat 2-neconex echilibrat.

Propozit , ia 1. Dac˘a G = (X, U) este un graf neorientat cu card(X) num˘ar impar, atunci G
nu este 2-neconex echilibrat.

Demonstrat¸ie. Presupunem prin absurd c˘a exist˘a un graf neorientat G = (X, U) cu card(X)
num˘ar impar, care este 2-neconex echilibrat. G fiind 2-neconex echilibrat, rezult˘a, din proprietatea
1) egalitatea card(X) = card(X 1 ) + card(X 2 ), iar din 2) egalitatea card(X 1 ) = card(X 2 ) = k.
Astfel, obt , inem card(X) = 2k, adic˘a num˘ar par, deci contradict , ie cu card(X) = num˘ar
impar.
1
Student, Universitatea din Pites , ti s , i A.S.E. Bucures , ti, alexionpopescu@gmail.com

37