Коэффициент сетчатости

Коэффициент сетчатости — инвариант планарных графов, измеряющий число ограниченных граней графа по отношению к возможному числу граней других планарных графов с тем же числом вершин. Коэффициент принимает значения от 0 для деревьев до 1 для максимальных планарных графов^{[англ.][1][2]}.

Определение

Коэффициент используется для сравнения общей структуры циклов связного планарного графа по отношению к двум крайним значениям. С одной стороны имеются деревья, планарные графы без циклов^[1]. Другая крайность представлена максимальными планарными графами^[англ.], имеющими наибольшее возможное число рёбер и граней для заданного числа вершин. Нормализованный коэффициент сетчатости — это отношение числа циклов к максимально возможному числу циклов в графе (с тем же числом вершин). Отношение принимает значение от 0 для деревьев до 1 для любого максимального планарного графа.

Вообще говоря, можно показать с помощью эйлеровой характеристики, что все планарные графы с ${\displaystyle n}$ вершинами имеют максимум ${\displaystyle 2n-5}$ ограниченных граней (одна неограниченная грань не считается) и, если имеется ${\displaystyle m}$ рёбер, то число ограниченных граней равно ${\displaystyle m-n+1}$ (что равно контурному рангу графа). Таким образом, нормализованный коэффициент сетчатости можно определить как отношение двух чисел:

${\displaystyle \alpha ={\frac {m-n+1}{2n-5}}.}$

И этот коэффициент меняется от 0 для деревьев до 1 для максимальных планарных графов.

Приложения

Коэффициент сетчатости может быть использован для оценки избыточности сети. Этот параметр, наряду с алгебраической связностью, которая измеряет надёжность сети, может быть использован для измерения топологических аспектов стойкости сети водопровода^[3]; также используется для описания структуры улиц в городах^[4][5][6].

Ограничения

В пределе для больших графов (число рёбер ${\displaystyle n\gg 1}$) сетчатость стремится к следующей величине:

${\displaystyle \alpha \approx {\frac {\langle k\rangle }{4}}-{\frac {1}{2}}}$,

где ${\displaystyle \langle k\rangle =2m/n}$ — средняя степень вершин в графе. Таким образом, для больших графов сетчатость не несёт больше информации, чем средняя степень.

Примечания

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

Литература

• J. Buhl, J. Gautrais, R.V. Sole, P. Kuntz, S. Valverde, J.L. Deneubourg, G. Theraulaz. Efficiency and robustness in ant networks of galleries // The European Physical Journal B-Condensed Matter and Complex Systems. — Springer-Verlag, 2004. — Т. 42, вып. 1. — doi:10.1140/epjb/e2004-00364-9.
• J. Buhl, J. Gautrais, N. Reeves, R.V. Sole, S. Valverde, P. Kuntz, G. Theraulaz. Topological patterns in street networks of self-organized urban settlements // The European Physical Journal B-Condensed Matter and Complex Systems. — EDP Sciences, 2006. — Т. 49, вып. 4. — doi:10.1140/epjb/e2006-00085-1.
• A. Yazdani, P. Jeffrey. Applying Network Theory to Quantify the Redundancy and Structural Robustness of Water Distribution Systems // Journal of Water Resources Planning and Management. — American Society of Civil Engineers, 2012. — Т. 138, вып. 2. — P. 153–161. — doi:10.1061/(ASCE)WR.1943-5452.0000159.
• X. Wang, Y. Jin, M. Abdel-Aty, P.J. Tremont, X. Chen. Macrolevel Model Development for Safety Assessment of Road Network Structures // Transportation Research Record: Journal of the Transportation Research Board. — Transportation Research Board of the National Academies, 2012. — Т. 2280, вып. 1. — doi:10.3141/2280-11.
• T. Courtat, C. Gloaguen, S. Douady. Mathematics and morphogenesis of cities: A geometrical approach // Phys. Rev. E. — American Physical Society, 2011. — Т. 83, вып. 3. — doi:10.1103/PhysRevE.83.036106.
• Y. Rui, Y. Ban, J. Wang, J. Haas. Exploring the patterns and evolution of self-organized urban street networks through modeling // The European Physical Journal B. — Springer-Verlag, 2013. — Т. 86, вып. 3. — doi:10.1140/epjb/e2012-30235-7.
• A. Yazdani, P. Jeffrey. Applying Network Theory to Quantify the Redundancy and Structural Robustness of Water Distribution Systems // Journal of Water Resources Planning and Management. — American Society of Civil Engineers, 2012. — Т. 138, вып. 2. — doi:10.1061/(ASCE)WR.1943-5452.0000159.
• X. Wang, Y. Jin, M. Abdel-Aty, P.J. Tremont, X. Chen. Macrolevel Model Development for Safety Assessment of Road Network Structures // Transportation Research Record: Journal of the Transportation Research Board. — Transportation Research Board of the National Academies, 2012. — Т. 2280, вып. 1. — doi:10.3141/2280-11.
• T. Courtat, C. Gloaguen, S. Douady. Mathematics and morphogenesis of cities: A geometrical approach // Phys. Rev. E. — American Physical Society, 2011. — Т. 83, вып. 3. — doi:10.1103/PhysRevE.83.036106.
• Y. Rui, Y. Ban, J. Wang, J. Haas. Exploring the patterns and evolution of self-organized urban street networks through modeling // The European Physical Journal B. — Springer-Verlag, 2013. — Т. 86, вып. 3. — doi:10.1140/epjb/e2012-30235-7.