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:
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 – – látható, hogy nagy gráfok esetében a határ (élek száma a behálózottsági együttható tart:
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
Jegyzetek
Kategória:Gráfinvariánsok Kategória:Síkgráfok