“Meshedness coefficient”的意思、由来-开放百科全书

In graph theory, the meshedness coefficient is a graph invariant of planar graphs that measures the number of bounded faces of the graph, as a fraction of the possible number of faces for other planar graphs with the same number of vertices. It ranges from 0 for trees to 1 for maximal planar graphs.^[1]

Definition

The meshedness coefficient is used to compare the general cycle structure of a connected planar graph to two extreme relevant references. In one end, there are trees, planar graphs with no cycle.^[1] The other extreme is represented by maximal planar graphs, planar graphs with the highest possible number of edges and faces for a given number of vertices. The normalized meshedness coefficient is the ratio of available face cycles to the maximum possible number of face cycles in the graph. This ratio is 0 for a tree and 1 for any maximal planar graph.

More generally, it can be shown using the Euler characteristic that all n-vertex planar graphs have at most 2n − 5 bounded faces (not counting the one unbounded face)

and that if there are m edges then the number of bounded faces is m − n + 1 (the same as the circuit rank of the graph).

Therefore, a normalized meshedness coefficient can be defined as the ratio of these two numbers:

Applications

The meshedness coefficient can be used to estimate the redundancy of a network. This parameter along with the algebraic connectivity which measures the robustness of the network, may be used to quantify the topological aspect of network resilience in water distribution networks.^[3] It has also been used to characterize the network structure of streets in urban areas.^[4]^[5]^[6]

Limitations

Using the definition of the average degree

, one can see that in the limit of large graphs (number of edges {{nowrap|1=

)}} the meshedness tends to

Thus, for large graphs, the meshedness does not carry more information than the average degree.

References

1. ^¹{{cite journal|last = Buhl| first = J.| last2 = Gautrais| first2 = J.| last3 = Sole | first3 = R.V.| last4 = Kuntz| first4 = P.| last5 = Valverde| first5 = S.| last6 = Deneubourg| first6 = J.L.| last7 = Theraulaz| first7 = G.| year = 2004| title = Efficiency and robustness in ant networks of galleries| journal = The European Physical Journal B| volume = 42| issue = 1| pages = 123–129| doi = 10.1140/epjb/e2004-00364-9}}
2. ^{{cite journal|last = Buhl| first = J.| last2 = Gautrais| first2 = J.| last3 = Reeves | first3 = N.| last4 = Sole | first4 = R.V.| last5 = Valverde| first5 = S.| last6 = Kuntz| first6 = P.| last7 = Theraulaz| first7 = G.| year = 2006| title = Topological patterns in street networks of self-organized urban settlements| journal = The European Physical Journal B| volume = 49| issue = 4| pages = 513–522| doi = 10.1140/epjb/e2006-00085-1}}
3. ^{{cite journal|last = Yazdani | first = A.| last2 = Jeffrey| first2 = P.| year = 2012| title = Applying Network Theory to Quantify the Redundancy and Structural Robustness of Water Distribution Systems| journal = Journal of Water Resources Planning and Management| volume = 138| issue = 2| pages = 153–161| doi = 10.1061/(ASCE)WR.1943-5452.0000159}}
4. ^{{cite journal |last = Wang |first = X. |last2 = Jin |first2 = Y. |last3 = Abdel-Aty |first3 = M. |last4 = Tremont |first4 = P.J. |last5 = Chen |first5 = X. |year = 2012 |title = Macrolevel Model Development for Safety Assessment of Road Network Structures |url = http://trb.metapress.com/content/N284113734V14P55 |journal = Transportation Research Record: Journal of the Transportation Research Board |volume = 2280 |issue = 1 |pages = 100–109 |doi = 10.3141/2280-11 |deadurl = yes |archiveurl = https://archive.is/20141121202721/http://trb.metapress.com/content/N284113734V14P55 |archivedate = 2014-11-21 |df = }}
5. ^{{cite journal|last = Courtat| first = T.| last2 = Gloaguen| first2 = C.| last3 = Douady | first3 = S.| year = 2011| title = Mathematics and morphogenesis of cities: A geometrical approach| journal = Phys. Rev. E| volume = 83| issue = 3| pages = 036106| doi = 10.1103/PhysRevE.83.036106| pmid = 21517557| arxiv = 1010.1762}}
6. ^{{cite journal|last = Rui| first = Y.| last2 = Ban| first2 = Y.| last3 = Wang | first3 = J.| last4 = Haas | first4 = J.| year = 2013| title = Exploring the patterns and evolution of self-organized urban street networks through modeling| journal = The European Physical Journal B| volume = 86| issue = 3| pages = 036106| doi = 10.1140/epjb/e2012-30235-7}}