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

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

Определение

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

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

\alpha ={\frac {m-n+1}{2n-5}}.

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

Приложения

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

Ограничения

Используя определение средней степени $\langle k\rangle =2m/n$ , видно, что в пределе больших графов (количество ребер $n\gg 1$ ) сетчатость имеет тенденцию

\alpha \approx {\frac {\langle k\rangle }{4}}-{\frac {1}{2}}

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

Ссылки

^ Jump up to: ^а ^б Буль, Дж.; Готре, Ж.; Соле, Р.В.; Кунц, П.; Вальверде, С.; Денебур, JL; Тераулаз, Г. (2004). «Эффективность и надежность в муравьиных сетях галерей». Европейский физический журнал Б. 42 (1): 123–129. Бибкод : 2004EPJB...42..123B . дои : 10.1140/epjb/e2004-00364-9 . S2CID 14975826 .
^ Буль, Дж.; Готре, Ж.; Ривз, Н.; Соле, Р.В.; Вальверде, С.; Кунц, П.; Тераулаз, Г. (2006). «Топологические закономерности уличных сетей самоорганизующихся городских поселений». Европейский физический журнал Б. 49 (4): 513–522. Бибкод : 2006EPJB...49..513B . дои : 10.1140/epjb/e2006-00085-1 . S2CID 9862922 .
^ Яздани, А.; Джеффри, П. (2012). «Применение сетевой теории для количественной оценки избыточности и структурной устойчивости систем водоснабжения». Журнал планирования и управления водными ресурсами . 138 (2): 153–161. doi : 10.1061/(ASCE)WR.1943-5452.0000159 .
^ Ван, X.; Джин, Ю.; Абдель-Аты, М.; Тремонт, П.Дж.; Чен, X. (2012). «Разработка модели макроуровня для оценки безопасности конструкций дорожной сети» . Отчет о транспортных исследованиях: Журнал Совета по транспортным исследованиям . 2280 (1): 100–109. дои : 10.3141/2280-11 . S2CID 110263962 . Архивировано из оригинала 21 ноября 2014 г.
^ Курта, Т.; Глоаген, К.; Дуади, С. (2011). «Математика и морфогенез городов: геометрический подход». Физ. Преподобный Е. 83 (3): 036106. arXiv : 1010.1762 . Бибкод : 2011PhRvE..83c6106C . дои : 10.1103/PhysRevE.83.036106 . ПМИД 21517557 . S2CID 808585 .
^ Руи, Ю.; Бан, Ю.; Ван, Дж.; Хаас, Дж. (2013). «Изучение закономерностей и эволюции самоорганизующихся городских уличных сетей посредством моделирования». Европейский физический журнал Б. 86 (3): 036106. Бибкод : 2013EPJB...86...74R . дои : 10.1140/epjb/e2012-30235-7 . S2CID 254118471 .

[first-1] Jump up to: ^а ^б Буль, Дж.; Готре, Ж.; Соле, Р.В.; Кунц, П.; Вальверде, С.; Денебур, JL; Тераулаз, Г. (2004). «Эффективность и надежность в муравьиных сетях галерей». Европейский физический журнал Б. 42 (1): 123–129. Бибкод : 2004EPJB...42..123B . дои : 10.1140/epjb/e2004-00364-9 . S2CID 14975826 .

[Second-2] Буль, Дж.; Готре, Ж.; Ривз, Н.; Соле, Р.В.; Вальверде, С.; Кунц, П.; Тераулаз, Г. (2006). «Топологические закономерности уличных сетей самоорганизующихся городских поселений». Европейский физический журнал Б. 49 (4): 513–522. Бибкод : 2006EPJB...49..513B . дои : 10.1140/epjb/e2006-00085-1 . S2CID 9862922 .

[Third-3] Яздани, А.; Джеффри, П. (2012). «Применение сетевой теории для количественной оценки избыточности и структурной устойчивости систем водоснабжения». Журнал планирования и управления водными ресурсами . 138 (2): 153–161. doi : 10.1061/(ASCE)WR.1943-5452.0000159 .

[Fourth-4] Ван, X.; Джин, Ю.; Абдель-Аты, М.; Тремонт, П.Дж.; Чен, X. (2012). «Разработка модели макроуровня для оценки безопасности конструкций дорожной сети» . Отчет о транспортных исследованиях: Журнал Совета по транспортным исследованиям . 2280 (1): 100–109. дои : 10.3141/2280-11 . S2CID 110263962 . Архивировано из оригинала 21 ноября 2014 г.

[Fifth-5] Курта, Т.; Глоаген, К.; Дуади, С. (2011). «Математика и морфогенез городов: геометрический подход». Физ. Преподобный Е. 83 (3): 036106. arXiv : 1010.1762 . Бибкод : 2011PhRvE..83c6106C . дои : 10.1103/PhysRevE.83.036106 . ПМИД 21517557 . S2CID 808585 .

[Sixth-6] Руи, Ю.; Бан, Ю.; Ван, Дж.; Хаас, Дж. (2013). «Изучение закономерностей и эволюции самоорганизующихся городских уличных сетей посредством моделирования». Европейский физический журнал Б. 86 (3): 036106. Бибкод : 2013EPJB...86...74R . дои : 10.1140/epjb/e2012-30235-7 . S2CID 254118471 .

[1]

[2]

[3]

[4]

[5]

[6]