Коэффициент сетчатости - Википедия - Meshedness coefficient

В теория графов, то коэффициент решетчатости это инвариант графа из планарные графы который измеряет количество ограниченных граней графа как долю от возможного количества граней для других плоских графов с таким же количеством вершин. Он колеблется от 0 для деревья до 1 для максимальные планарные графы.[1][2]

Определение

Коэффициент сетчатости используется для сравнения общей структуры цикла связного плоского графа с двумя крайними релевантными ссылками. С одной стороны, есть деревья, планарные графы без цикла.[1] Другая крайность представлена максимальные планарные графы, планарные графы с максимально возможным числом ребер и граней для заданного числа вершин. Нормализованный коэффициент сетки - это отношение доступных циклов граней к максимально возможному количеству циклов граней на графике. Это отношение равно 0 для дерева и 1 для любого максимального плоского графа.

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

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

Приложения

Коэффициент ячеистости можно использовать для оценки избыточности сети. Этот параметр вместе с алгебраическая связность который измеряет надежность сети, может использоваться для количественной оценки топологического аспекта устойчивости сети в сетях распределения воды.[3] Он также использовался для характеристики сетевой структуры улиц в городских районах.[4][5][6]

Ограничения

Используя определение средней степени , видно, что в пределе больших графов (число ребер ) сетка имеет тенденцию к

Таким образом, для больших графов сетчатость не несет больше информации, чем средняя степень.

Рекомендации

  1. ^ а б Buhl, J .; Gautrais, J .; Sole, R.V .; Kuntz, P .; Valverde, S .; Deneubourg, J.L .; Тераулаз, Г. (2004). «Эффективность и надежность в муравьиных сетях галерей». Европейский физический журнал B. 42 (1): 123–129. Дои:10.1140 / epjb / e2004-00364-9.
  2. ^ Buhl, J .; Gautrais, J .; Ривз, Н .; Sole, R.V .; Valverde, S .; Kuntz, P .; Тераулаз, Г. (2006). «Топологические закономерности уличных сетей самоорганизованных городских поселений». Европейский физический журнал B. 49 (4): 513–522. Дои:10.1140 / epjb / e2006-00085-1.
  3. ^ Яздани, А .; Джеффри, П. (2012). «Применение сетевой теории для количественной оценки избыточности и структурной устойчивости систем распределения воды». Журнал планирования и управления водными ресурсами. 138 (2): 153–161. Дои:10.1061 / (ASCE) WR.1943-5452.0000159.
  4. ^ Ван, X .; Jin, Y .; Абдель-Аты, М .; Tremont, P.J .; Чен, X. (2012). «Разработка макроуровневой модели для оценки безопасности конструкций дорожной сети». Отчет о транспортных исследованиях: журнал Совета по исследованиям в области транспорта. 2280 (1): 100–109. Дои:10.3141/2280-11. Архивировано из оригинал 2014-11-21.
  5. ^ Courtat, T .; Gloaguen, C .; Дуади, С. (2011). «Математика и морфогенез городов: геометрический подход». Phys. Ред. E. 83 (3): 036106. arXiv:1010.1762. Дои:10.1103 / PhysRevE.83.036106. PMID  21517557.
  6. ^ Rui, Y .; Ban, Y .; Wang, J .; Хаас, Дж. (2013). «Изучение закономерностей и эволюции самоорганизующихся городских уличных сетей посредством моделирования». Европейский физический журнал B. 86 (3): 036106. Дои:10.1140 / epjb / e2012-30235-7.