Maskighetskoefficient
I grafteorin är meshness -koefficienten en graf som är invariant av plana grafer som mäter antalet avgränsade ytor av grafen, som en bråkdel av det möjliga antalet ytor för andra plana grafer med samma antal hörn. Den sträcker sig från 0 för träd till 1 för maximala plana grafer .
Definition
Meshness koefficienten används för att jämföra den allmänna cykelstrukturen för en sammankopplad plan graf med två extremt relevanta referenser. I ena änden finns det träd , plana grafer utan cykel. Den andra ytterligheten representeras av maximala plana grafer , plana grafer med högsta möjliga antal kanter och ytor för ett givet antal hörn. Den normaliserade meshness-koefficienten är förhållandet mellan tillgängliga ansiktscykler och maximalt möjliga antal ansiktscykler i grafen. Detta förhållande är 0 för ett träd och 1 för en maximal plan graf.
Mer allmänt kan det visas med hjälp av Euler-karakteristiken att alla n -vertex plana grafer har högst 2 n − 5 avgränsade ytor (den ena obegränsade ytan räknas inte med) och att om det finns m kanter så är antalet avgränsade ytor m − n + 1 (samma som kretsrankningen för grafen). Därför kan en normaliserad meshness-koefficient definieras som förhållandet mellan dessa två siffror:
Den varierar från 0 för träd till 1 för maximala plana grafer.
Ansökningar
Meshness-koefficienten kan användas för att uppskatta redundansen för ett nätverk. Denna parameter tillsammans med den algebraiska anslutningen som mäter nätverkets robusthet kan användas för att kvantifiera den topologiska aspekten av nätverksresiliens i vattendistributionsnätverk. Den har också använts för att karakterisera nätverksstrukturen på gator i tätorter.
Begränsningar
Med hjälp av definitionen av medelgraden , kan man se att i gränsen för stora grafer (antal kanter ) maskigheten tenderar att
Således, för stora grafer, innehåller maskvidden inte mer information än den genomsnittliga graden.