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.[1] [2]
Meghatározás szerkeszté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.[1] 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 szerkesztés
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.[3] Városi területek utcaszerkezetének jellemzésére is felhasználták.[4][5][6]
Korlátai szerkesztés
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 szerkeszté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.
Jegyzetek szerkesztés
- ↑ a b Buhl, J. (2004). „Efficiency and robustness in ant networks of galleries”. The European Physical Journal B 42 (1), 123–129. o, Kiadó: Springer-Verlag. DOI:10.1140/epjb/e2004-00364-9.
- ↑ Buhl, J. (2006). „Topological patterns in street networks of self-organized urban settlements”. The European Physical Journal B 49 (4), 513–522. o, Kiadó: EDP Sciences. DOI:10.1140/epjb/e2006-00085-1.
- ↑ Yazdani, A. (2012). „Applying Network Theory to Quantify the Redundancy and Structural Robustness of Water Distribution Systems”. Journal of Water Resources Planning and Management 138 (2), 153–161. o, Kiadó: American Society of Civil Engineers. DOI:10.1061/(ASCE)WR.1943-5452.0000159.
- ↑ Wang, X. (2012). „Macrolevel Model Development for Safety Assessment of Road Network Structures”. Transportation Research Record: Journal of the Transportation Research Board 2280 (1), 100–109. o, Kiadó: Transportation Research Board of the National Academies. [2014. november 21-i dátummal az eredetiből archiválva]. DOI:10.3141/2280-11.
- ↑ Courtat, T. (2011). „Mathematics and morphogenesis of cities: A geometrical approach”. Phys. Rev. E 83 (3), 036106. o, Kiadó: American Physical Society. DOI:10.1103/PhysRevE.83.036106.
- ↑ Rui, Y. (2013). „Exploring the patterns and evolution of self-organized urban street networks through modeling”. The European Physical Journal B 86 (3), 036106. o, Kiadó: Springer-Verlag. DOI:10.1140/epjb/e2012-30235-7.