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 – $⟨k⟩=2m/n$ – látható, hogy nagy gráfok esetében a határ (élek száma Sablon:Nowrap a behálózottsági együttható tart:

$\alpha \approx \frac{⟨k⟩}{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

• Sablon:Fordítás