Коефіцієнт сітчастості
Коефіціє́нт сітча́стості — інваріант планарних графів, що вимірює кількість обмежених граней графа відносно можливого числа граней інших планарних графів з тим самим числом вершин. Коефіцієнт набуває значення від 0 для дерев до 1 для максимальних планарних графів [1] [2] .
Визначення[ред. | ред. код]
Коефіцієнт використовується для порівняння загальної структури циклів зв'язного планарного графа відносно двох крайніх значень. З одного боку є дерева, планарні графи без циклів[1]. Інша крайність — максимальні планарні графи, що мають найбільше можливе число ребер і граней для заданого числа вершин. Нормалізований коефіцієнт сітчастості — це відношення числа циклів до найбільшого можливого числа циклів у графі (з тим самим числом вершин). Відношення набуває значення від 0 для дерев до 1 для будь-якого максимального планарного графа.
Можна показати за допомогою ейлерової характеристики, що всі планарні графи з вершинами мають максимум обмежених граней (одна необмежена грань не враховується) і, якщо є ребер, то кількість обмежених граней дорівнює (що дорівнює контурному рангу графа). Отже, нормалізований коефіцієнт сітчастості можна визначити як відношення двох чисел:
І цей коефіцієнт змінюється від 0 для дерев до 1 для максимальних планарних графів.
Застосування[ред. | ред. код]
Коефіцієнт сітчастості можна використати для оцінення надмірності мережі. Цей параметр, поряд із алгебричною зв'язністю, яка вимірює надійність мережі, можна використати для вимірювання топологічних аспектів стійкості водогінної мережі[3]; також використовується для опису структури вулиць у містах[4][5][6].
Обмеження[ред. | ред. код]
У границі для великих графів (число ребер ) сітчастість прямує до такої величини:
- ,
де — середній степінь вершин у графі. Таким чином, для великих графів сітчастість не несе більше інформації, ніж середній степінь.
Примітки[ред. | ред. код]
- ↑ а б Buhl, Gautrais, Sole и др., 2004, с. 123–129.
- ↑ Buhl, Gautrais, Reeves и др., 2006, с. 513–522.
- ↑ Yazdani, Jeffrey, 2012, с. 153–161.
- ↑ Wang, Jin, Abdel-Aty др., 2012, с. 100–109.
- ↑ Courtat, Gloaguen, Douady, 2011, с. 036106.
- ↑ 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: .
- 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: .
- 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: .
- 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: .
- T. Courtat, C. Gloaguen, S. Douady. Mathematics and morphogenesis of cities: A geometrical approach // Phys. Rev. E. — American Physical Society, 2011. — Т. 83, вип. 3. — DOI: .
- 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: .
- 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: .
- 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: .
- T. Courtat, C. Gloaguen, S. Douady. Mathematics and morphogenesis of cities: A geometrical approach // Phys. Rev. E. — American Physical Society, 2011. — Т. 83, вип. 3. — DOI: .
- 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: .