Retikulációs tényező

A hálótényező  a síkgráfok invariánsa, amely a korlátos gráflapok számát méri más, azonos számú csúcsú síkgráfok lehetséges lapjaihoz viszonyítva. A fák együtthatója 0- tól 1-ig terjed a maximális síkgráfoknál [1] [2] .

Definíció

Az együtthatót arra használják, hogy összehasonlítsák egy összefüggő síkgráf teljes ciklusszerkezetét két szélső értékkel. Egyrészt léteznek fák , síkgráfok ciklusok nélkül [1] . A másik végletet a maximális síkgráfok képviselik , amelyek adott számú csúcshoz a lehető legtöbb éllel és lappal rendelkeznek. A normalizált hálótényező a ciklusok számának és a gráfban lehetséges maximális ciklusszámnak az aránya (azonos számú csúcs mellett). A fák aránya 0-tól 1-ig terjed bármely maximális síkgráf esetén.

Általánosságban elmondható, hogy az Euler-karakterisztikával kimutatható, hogy minden csúcsú síkgráfnak maximum korlátos lapja van (egy korlátlan lap nem számít), és ha vannak élek, akkor a korlátos lapok száma egyenlő (ami egyenlő a gráf kontúrrangja ). Így a normalizált hálótényező két szám arányaként definiálható:

És ez az együttható a fák 0-tól a maximális síkgráfok esetében 1-ig változik.

Alkalmazások

A hálótényező használható a hálózat redundanciájának értékelésére. Ez a paraméter a hálózat megbízhatóságát mérő algebrai összeköttetéssel együtt felhasználható a vízellátó hálózat rugalmasságának topológiai szempontjainak mérésére [3] ; városi utcák szerkezetének leírására is használják [4] [5] [6] .

Korlátozások

A nagy grafikonok határértékében (az élek száma ) a háló a következő értékre hajlik:

,

ahol a gráf csúcsainak átlagos foka. Így a nagy gráfok esetében a retikuláció nem hordoz több információt, mint az átlagos mérték.

Jegyzetek

  1. ↑ 1 2 Buhl, Gautrais, Sole et al., 2004 , p. 123–129.
  2. ↑ Buhl, Gautrais, Reeves et al., 2006 , p. 513–522.
  3. ↑ Yazdani, Jeffrey, 2012 , p. 153–161.
  4. ↑ Wang, Jin, Abdel-Aty et al., 2012 , p. 100–109.
  5. ↑ Courtat, Gloaguen, Douady, 2011 , p. 036106.
  6. ↑ Rui, Ban, Wang, Haas, 2013 , p. 036106.

Irodalom