Коефіцієнт сітчастості
Коефіціє́нт сітча́стості — інваріант планарних графів, що вимірює кількість обмежених граней графа відносно можливого числа граней інших планарних графів з тим самим числом вершин. Коефіцієнт набуває значення від 0 для дерев до 1 для максимальних планарних графів Шаблон:Sfn Шаблон:Sfn .
Визначення
Коефіцієнт використовується для порівняння загальної структури циклів зв'язного планарного графа відносно двох крайніх значень. З одного боку є дерева, планарні графи без циклівШаблон:Sfn. Інша крайність — максимальні планарні графи, що мають найбільше можливе число ребер і граней для заданого числа вершин. Нормалізований коефіцієнт сітчастості — це відношення числа циклів до найбільшого можливого числа циклів у графі (з тим самим числом вершин). Відношення набуває значення від 0 для дерев до 1 для будь-якого максимального планарного графа.
Можна показати за допомогою ейлерової характеристики, що всі планарні графи з вершинами мають максимум обмежених граней (одна необмежена грань не враховується) і, якщо є ребер, то кількість обмежених граней дорівнює (що дорівнює контурному рангу графа). Отже, нормалізований коефіцієнт сітчастості можна визначити як відношення двох чисел:
І цей коефіцієнт змінюється від 0 для дерев до 1 для максимальних планарних графів.
Застосування
Коефіцієнт сітчастості можна використати для оцінення надмірності мережі. Цей параметр, поряд із алгебричною зв'язністю, яка вимірює надійність мережі, можна використати для вимірювання топологічних аспектів стійкості водогінної мережіШаблон:Sfn; також використовується для опису структури вулиць у містахШаблон:SfnШаблон:SfnШаблон:Sfn.
Обмеження
У границі для великих графів (число ребер Шаблон:Nobr сітчастість прямує до такої величини:
- ,
де — середній степінь вершин у графі. Таким чином, для великих графів сітчастість не несе більше інформації, ніж середній степінь.