Перейти до вмісту

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

Матеріал з Вікіпедії — вільної енциклопедії.

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

Визначення

[ред. | ред. код]

Коефіцієнт використовується для порівняння загальної структури циклів зв'язного планарного графа відносно двох крайніх значень. З одного боку є дерева, планарні графи без циклів[1]. Інша крайність — максимальні планарні графи, що мають найбільше можливе число ребер і граней для заданого числа вершин. Нормалізований коефіцієнт сітчастості — це відношення числа циклів до найбільшого можливого числа циклів у графі (з тим самим числом вершин). Відношення набуває значення від 0 для дерев до 1 для будь-якого максимального планарного графа.

Можна показати за допомогою ейлерової характеристики, що всі планарні графи з вершинами мають максимум обмежених граней (одна необмежена грань не враховується) і, якщо є ребер, то кількість обмежених граней дорівнює (що дорівнює контурному рангу графа). Отже, нормалізований коефіцієнт сітчастості можна визначити як відношення двох чисел:

І цей коефіцієнт змінюється від 0 для дерев до 1 для максимальних планарних графів.

Застосування

[ред. | ред. код]

Коефіцієнт сітчастості можна використати для оцінення надмірності мережі. Цей параметр, поряд із алгебричною зв'язністю, яка вимірює надійність мережі, можна використати для вимірювання топологічних аспектів стійкості водогінної мережі[3]; також використовується для опису структури вулиць у містах[4][5][6].

Обмеження

[ред. | ред. код]

У границі для великих графів (число ребер ) сітчастість прямує до такої величини:

,

де  — середній степінь вершин у графі. Таким чином, для великих графів сітчастість не несе більше інформації, ніж середній степінь.

Примітки

[ред. | ред. код]

Література

[ред. | ред. код]