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

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

Определение

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

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

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

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

Приложения

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

Ограничения

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

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

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

Литература

• 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.