Behálózottsági együttható

A matematika, azon belül a gráfelmélet területén a behálózottsági együttható vagy ciklomatikus együttható (meshedness coefficient) síkbarajzolható gráfok olyan gráfinvariánsa, ami a gráf korlátos tartományainak számát méri az ugyanannyi csúcson előállítható síkbarajzolható gráfok lehetséges tartományai számának arányában. Minimális értéke 0, amit fák esetében, maximális értéke 1, amit maximális síkgráfokon vesz fel.

Meghatározás

A behálózottsági együttható egy összefüggő síkgráf körszerkezetét hasonlítja össze két extrém példával. Az egyik véglet a fa, a körrel nem rendelkező síkgráf. A másik végletet a maximális síkgráfok, tehát az adott csúcs esetében maximális számú éllel és tartománnyal rendelkező síkbarajzolható gráfok képviselik. A normalizált behálózottsági együttható a rendelkezésre álló tartomány-körök és a maximálisan lehetséges tartomány-körök aránya.

Általánosabban, az Euler-karakterisztika használatával megmutatható, hogy minden n-csúcsú síkbarajzolható gráf legfeljebb 2n − 5 korlátos tartománnyal rendelkezik (nem számolva tehát a korlátlan tartományt) és ha m az élek számát jelöli, akkor a korlátos tartományok száma m − n + 1 (éppen annyi, mint a gráf ciklikus rangja). Így a normalizált ciklomatikus együttható ezen két szám arányaként írható fel:

$\alpha ={\frac {m-n+1}{2n-5}}.$

Az arány fák esetében 0, maximális síkgráfok esetében 1.

Alkalmazások

A behálózottsági együtthatóval becsülni lehet egy hálózat redundanciáját. Ez a paraméter, a hálózat robusztusságát mérő algebrai összefüggőséggel együtt jól használható vízelosztási hálózatok hálózati ellenálló képessége topológiai aspektusának számszerűsítésére. Városi területek utcaszerkezetének jellemzésére is felhasználták.

Korlátai

Az átlagos fokszám definícióját használva – $\langle k\rangle =2m/n$ – látható, hogy nagy gráfok esetében a határ (élek száma $n\gg 1$) a behálózottsági együttható tart:

$\alpha \approx {\frac {\langle k\rangle }{4}}-{\frac {1}{2}}$

Tehát nagy gráfok esetében a behálózottság nem hordoz több információt, mint az átlagos fokszám.

Fordítás

• Ez a szócikk részben vagy egészben a Meshedness coefficient című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.