Главная
Новости
Строительство
Ремонт
Дизайн и интерьер

















Яндекс.Метрика





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

Коэффициент сетчатости — инвариант планарных графов, измеряющий число ограниченных граней графа по отношению к возможному числу граней других планарных графов с тем же числом вершин. Коэффициент принимает значения от 0 для деревьев до 1 для максимальных планарных графов.

Определение

Коэффициент используется для сравнения общей структуры циклов связного планарного графа по отношению к двум крайним значениям. С одной стороны имеются деревья, планарные графы без циклов. Другая крайность представлена максимальными планарными графами, имеющими наибольшее возможное число рёбер и граней для заданного числа вершин. Нормализованный коэффициент сетчатости — это отношение числа циклов к максимально возможному числу циклов в графе (с тем же числом вершин). Отношение принимает значение от 0 для деревьев до 1 для любого максимального планарного графа.

Вообще говоря, можно показать с помощью эйлеровой характеристики, что все планарные графы с n {displaystyle n} вершинами имеют максимум 2 n − 5 {displaystyle 2n-5} ограниченных граней (одна неограниченная грань не считается) и, если имеется m {displaystyle m} рёбер, то число ограниченных граней равно m − n + 1 {displaystyle m-n+1} (что равно контурному рангу графа). Таким образом, нормализованный коэффициент сетчатости можно определить как отношение двух чисел:

α = m − n + 1 2 n − 5 . {displaystyle alpha ={frac {m-n+1}{2n-5}}.}

И этот коэффициент меняется от 0 для деревьев до 1 для максимальных планарных графов.

Приложения

Коэффициент сетчатости может быть использован для оценки избыточности сети. Этот параметр, наряду с алгебраической связностью, которая измеряет надёжность сети, может быть использован для измерения топологических аспектов стойкости сети водопровода; также используется для описания структуры улиц в городах.

Ограничения

В пределе для больших графов (число рёбер n ≫ 1 {displaystyle ngg 1} ) сетчатость стремится к следующей величине:

α ≈ ⟨ k ⟩ 4 − 1 2 {displaystyle alpha approx {frac {langle k angle }{4}}-{frac {1}{2}}} ,

где ⟨ k ⟩ = 2 m / n {displaystyle langle k angle =2m/n} — средняя степень вершин в графе. Таким образом, для больших графов сетчатость не несёт больше информации, чем средняя степень.