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ë  një graf i fundëm i padrejtuar me bashlësi kulmesh  dhe bashkësi brinjësh  . Për një koleksion kulmesh  , 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 ):



Vini re se brinjët janë të pa renditura, dmth.  . Konstantja Çiger e G, e shënuar , përcaktohet nga 



 Shembull: rrjetet kompjuterike 
parapamje| 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  (numri i kompjuterëve në rrjet) është i madh.

Për shembull, merrni parasysh një rrjet unazor prej  kompjuterësh, i menduar si një graf  . 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:



Merrni A si një koleksion i  nga këta kompjuterë në një zinxhir të lidhur:



Pra,



dhe



Ky shembull ofron një kufi të sipërm për konstanten e Çigerit , 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.