Коефіцієнт сітчастості

Коефіціє́нт сітча́стості — інваріант планарних графів, що вимірює кількість обмежених граней графа відносно можливого числа граней інших планарних графів з тим самим числом вершин. Коефіцієнт набуває значення від 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. — С. 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.