Коэффициент сетчатости
Коэффициент сетчатости — инвариант планарных графов, измеряющий число ограниченных граней графа по отношению к возможному числу граней других планарных графов с тем же числом вершин. Коэффициент принимает значения от 0 для деревьев до 1 для Шаблон:Не переведено 5Шаблон:SfnШаблон:Sfn.
Определение
Коэффициент используется для сравнения общей структуры циклов связного планарного графа по отношению к двум крайним значениям. С одной стороны имеются деревья, планарные графы без цикловШаблон:Sfn. Другая крайность представлена Шаблон:Не переведено 5, имеющими наибольшее возможное число рёбер и граней для заданного числа вершин. Нормализованный коэффициент сетчатости — это отношение числа циклов к максимально возможному числу циклов в графе (с тем же числом вершин). Отношение принимает значение от 0 для деревьев до 1 для любого максимального планарного графа.
Вообще говоря, можно показать с помощью эйлеровой характеристики, что все планарные графы с вершинами имеют максимум ограниченных граней (одна неограниченная грань не считается) и, если имеется рёбер, то число ограниченных граней равно (что равно контурному рангу графа). Таким образом, нормализованный коэффициент сетчатости можно определить как отношение двух чисел:
И этот коэффициент меняется от 0 для деревьев до 1 для максимальных планарных графов.
Приложения
Коэффициент сетчатости может быть использован для оценки избыточности сети. Этот параметр, наряду с алгебраической связностью, которая измеряет надёжность сети, может быть использован для измерения топологических аспектов стойкости сети водопроводаШаблон:Sfn; также используется для описания структуры улиц в городахШаблон:SfnШаблон:SfnШаблон:Sfn.
Ограничения
В пределе для больших графов (число рёбер Шаблон:Nowrap сетчатость стремится к следующей величине:
- ,
где — средняя степень вершин в графе. Таким образом, для больших графов сетчатость не несёт больше информации, чем средняя степень.