Сильно нерегулярный график
В теории графов сильно нерегулярный граф — это граф , в котором для каждой вершины все соседи этой вершины имеют разные степени .
История [ править ]
Нерегулярные графы первоначально были охарактеризованы Юсефом Алави , Гэри Чартрандом , Фан Чунгом , Полом Эрдёшем , Рональдом Грэмом и Ортрудой Оллерманн . [1] Они были мотивированы определить «противоположность» регулярного графа — концепцию, которая была тщательно изучена и хорошо понята.
Локальность и регулярность [ править ]
Определение «нерегулярного графа» не было сразу очевидным. В k -регулярном графе все вершины имеют степень k . В любом графе G с более чем одной вершиной две вершины в G должны иметь одинаковую степень, поэтому нерегулярный граф нельзя определить как граф, все вершины которого имеют разные степени. Тогда может возникнуть соблазн определить нерегулярный граф как имеющий все вершины различных степеней, кроме двух, но эти типы графов также хорошо изучены и, следовательно, не интересны. [2]
Таким образом, теоретики графов обратились к проблеме локальной регулярности. Граф локально регулярен в вершине v вершины , если все смежные с v имеют степень r . Таким образом, граф является локально нерегулярным, если для каждой вершины v из G соседи v имеют разные степени, и поэтому такие графы называются сильно нерегулярными графами. [1]
Свойства нерегулярных графов [ править ]
Некоторые факты о сильно нерегулярных графах, изложенные Алави и др. : [3]
- Если v — вершина максимальной степени d в сильно нерегулярном графе H , то v смежна ровно с одной вершиной степени 1, 2, ..., d . [3]
- Наибольшая степень в сильно нерегулярном графе составляет не более половины числа вершин. [3]
- Если H — сильно нерегулярный граф с максимальной степенью d , можно построить сильно нерегулярный граф степени d +1, взяв две копии H и добавив ребро между двумя вершинами степени d . [3]
- H ( n )/ G ( n ) стремится к 0, когда n экспоненциально быстро стремится к бесконечности, где H ( n ) — количество (неизоморфных) сильно нерегулярных графов с n вершинами, а G ( n ) — общее количество графов с n вершинами. [3]
- Для каждого графа G существует сильно нерегулярный граф H, содержащий G в качестве индуцированного подграфа . [3]
Это последнее наблюдение можно считать аналогичным результату Денеша Кёнига , который утверждает, что если H — граф с наибольшей степенью r , то существует граф G , который является r -регулярным и содержит H как индуцированный подграф. [3]
Заявления о нарушениях [ править ]
Определения нерегулярности сыграли важную роль в изучении сетевой гетерогенности, которая имеет последствия для сетей, встречающихся в биологии, экологии, технологиях и экономике. [4] Было предложено несколько статистических данных графов, многие из которых основаны на количестве вершин в графе и их степенях. Характеристика сильно нерегулярных графов также применялась к вопросу неоднородности, однако все они не смогли пролить достаточно света на реальные ситуации. Продолжаются попытки найти подходящие способы количественной оценки неоднородности сети. [4]
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б Шартран, Гэри; Эрдеш, Пол; Оллерманн, Ортруда Р. (1988). «Как определить нерегулярный график». Математический журнал колледжа . 19 (1). Информа Великобритания Лимитед: 36–42. дои : 10.1080/07468342.1988.11973088 . ISSN 0746-8342 .
- ^ Бехзад, Мехди; Чартран, Гэри (1967). «Ни один график не идеален». Американский математический ежемесячник . 74 (8). JSTOR: 962. doi : 10.2307/2315277 . ISSN 0002-9890 .
- ↑ Перейти обратно: Перейти обратно: а б с д и ж г Алави, Юсеф; Шартран, Гэри; Чанг, Франция; Эрдеш, Пол; Грэм, РЛ; Оллерманн, Ортруда Р. (1987). «Сильно нерегулярные графики» (PDF) . Журнал теории графов . 11 (2). Уайли: 235–249. дои : 10.1002/jgt.3190110214 . ISSN 0364-9024 .
- ↑ Перейти обратно: Перейти обратно: а б Эстрада, Эрнесто (2 декабря 2010 г.). «Количественная оценка неоднородности сети». Физический обзор E . 82 (6). Американское физическое общество (APS): 066102. doi : 10.1103/physreve.82.066102 . ISSN 1539-3755 .