Konstantja Çiger (teoria e grafeve)

Në matematikë, konstanta e Çigerit e një grafi është një masë numerike nëse një grafik ka ose jo një "lëfytje". Konstanta e Çigerit si një masë e "bllokut të ngushtë" është me interes të madh në shumë fusha: për shembull, ndërtimi i rrjeteve të lidhura mirë të kompjuterëve, shkartisja e kartave . Nocioni teorik i grafit e ka origjinën tek konstantja izoperimetrike Çiger e një durthi kompakt Rimanian .

Përkufizimi

Le të jetë G një graf i fundëm i padrejtuar me bashlësi kulmesh V(G) dhe bashkësi brinjësh A ⊆ V(G) . Për një koleksion kulmesh A ⊆ V(G) , le të ∂A të tregojë koleksionin i të gjitha brinjëve që shkojnë nga një kulm në A në një kulm jashtë A (ndonjëherë quhet kufiri i skajit të A ):

$\partial A:=\{\{x,y\}\in E(G)\ :\ x\in A,y\in V(G)\setminus A\}.$

Vini re se brinjët janë të pa renditura, dmth. $\{x,y\}=\{y,x\}$ . Konstantja Çiger e G, e shënuar h(G), përcaktohet nga

$h(G):=\min \left\{{\frac {|\partial A|}{|A|}}\ :\ A\subseteq V(G),0<|A|\leq {\tfrac {1}{2}}|V(G)|\right\}.$

Shembull: rrjetet kompjuterike

Paraqitja e rrjetit të tipit unazë

Në zbatimet e shkencën kompjuterike teorike, dëshirohet të krijohen konfigurime rrjeti për të cilat konstantja e Çigerit është e lartë (të paktën, e kufizuar nga zero) edhe kur |V(G)| (numri i kompjuterëve në rrjet) është i madh.

Për shembull, merrni parasysh një rrjet unazor prej N ≥ 3 kompjuterësh, i menduar si një graf G_N. Numëroni kompjuterët 1, 2, ... , N në drejtim të akrepave të orës rreth unazës. Matematikisht, bashkësia e kulmeve dhe bashkësi e brinjëve jepen nga:

${\begin{aligned}V(G_{N})&=\{1,2,\cdots ,N-1,N\}\\E(G_{N})&={\big \{}\{1,2\},\{2,3\},\cdots ,\{N-1,N\},\{N,1\}{\big \}}\end{aligned}}$

Merrni A si një koleksion i $\left\lfloor {\tfrac {N}{2}}\right\rfloor$ nga këta kompjuterë në një zinxhir të lidhur:

$A=\left\{1,2,\cdots ,\left\lfloor {\tfrac {N}{2}}\right\rfloor \right\}.$

Pra,

$\partial A=\left\{\left\{\left\lfloor {\tfrac {N}{2}}\right\rfloor ,\left\lfloor {\tfrac {N}{2}}\right\rfloor +1\right\},\{N,1\}\right\},$

dhe

${\frac {|\partial A|}{|A|}}={\frac {2}{\left\lfloor {\tfrac {N}{2}}\right\rfloor }}\to 0{\mbox{ teksa }}N\to \infty .$

Ky shembull ofron një kufi të sipërm për konstanten e Çigerit h(G_N), e cila gjithashtu tenton drejt zeros kur N → ∞ . Rrjedhimisht, ne do ta konsideronim një rrjet unazash si shumë "të ngushtë" për N të mëdha, dhe kjo është shumë e padëshirueshme në aspektin praktik. Do të na duhej vetëm një nga kompjuterët në rrjet që të dështonte dhe performanca e rrjetit do të reduktohej shumë. Nëse dy kompjuterë jo ngjitur do të dështonin, rrjeti do të ndahej në dy komponentë të shkëputur.