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

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