Retikulationsfaktor

Nätfaktorn  är en invariant av plana grafer som mäter antalet avgränsade grafytor i förhållande till det möjliga antalet ytor av andra plana grafer med samma antal hörn. Koefficienten tar värden från 0 för träd till 1 för maximala plana grafer [1] [2] .

Definition

Koefficienten används för att jämföra den övergripande cykelstrukturen för en sammankopplad plan graf med avseende på två extremvärden. Å ena sidan finns det träd , plana grafer utan cykler [1] . Den andra ytterligheten representeras av maximala plana grafer som har största möjliga antal kanter och ytor för ett givet antal hörn. Den normaliserade maskfaktorn är förhållandet mellan antalet cykler och det maximalt möjliga antalet cykler i grafen (med samma antal hörn). Förhållandet tar ett värde från 0 för träd till 1 för en maximal plan graf.

Generellt sett kan det visas med hjälp av Euler-karakteristiken att alla plana grafer med hörn har maximalt avgränsade ytor (en obegränsad yta räknas inte) och om det finns kanter så är antalet avgränsade ytor lika (vilket är lika med grafens konturrang ). Således kan den normaliserade mesh-faktorn definieras som förhållandet mellan två tal:

Och denna koefficient varierar från 0 för träd till 1 för maximala plana grafer.

Applikationer

Mesh-faktorn kan användas för att utvärdera redundansen i ett nätverk. Denna parameter, tillsammans med algebraisk anslutning , som mäter ett nätverks tillförlitlighet, kan användas för att mäta de topologiska aspekterna av motståndskraften hos ett vattenförsörjningsnät [3] ; används också för att beskriva strukturen på gator i städer [4] [5] [6] .

Begränsningar

I gränsen för stora grafer (antalet kanter ) tenderar nätet till följande värde:

,

var är den genomsnittliga graden av hörn i grafen. Således, för stora grafer, ger retikulering inte mer information än den genomsnittliga graden.

Anteckningar

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

Litteratur