Сильно нерегулярный график - Highly irregular graph

В теория графов, а сильно нерегулярный график это график в котором для каждой вершины все соседи этой вершины имеют различные градусы.

История

Первоначально нерегулярные графики характеризовались Юсеф Алави, Гэри Чартранд, Фань Чанг, Пол Эрдёш, Рональд Грэм, и Ортруд Оеллерманн.[1] Они были заинтересованы в определении «противоположности» регулярный график, концепция, которая была тщательно изучена и хорошо изучена.

Местность и регулярность

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

Таким образом, теоретики графов обратились к проблеме локальной регулярности. Граф локально регулярен в вершине v если все вершины, смежные с v иметь степень р. Таким образом, граф является локально нерегулярным, если для каждой вершины v из грамм соседи v имеют различные степени, поэтому эти графы называются сильно нерегулярными графами.[1]

Свойства нерегулярных графов

Некоторые факты о крайне нерегулярных графиках, изложенные Алави и другие.:[3]

  • Если v - вершина максимальной степени d в очень нерегулярном графике ЧАС, тогда v смежна ровно с одной вершиной степени 1, 2, ...,d.[3]
  • Наибольшая степень в сильно нерегулярном графе составляет не более половины числа вершин.[3]
  • Если ЧАС очень нерегулярный график с максимальной степенью d, можно построить сильно нерегулярный граф степени d+1, взяв две копии ЧАС и добавив ребро между двумя вершинами степениd.[3]
  • ЧАС(п)/грамм(п) стремится к 0 при п экспоненциально быстро уходит в бесконечность, где ЧАС(п) - количество (неизоморфных) сильно нерегулярных графов с п вершины и грамм(п) - общее количество графов с п вершины.[3]
  • Для каждого графика грамм, существует очень нерегулярный граф ЧАС содержащий грамм как индуцированный подграф.[3]

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

Заявления о нарушениях

Определения нерегулярности были важны при изучении неоднородности сети, которая имеет значение в сетях, встречающихся в биологии, экологии, технологиях и экономике.[4] Было предложено несколько статистических данных графов, многие из которых основаны на количестве вершин в графе и их степенях. Характеристика сильно нерегулярных графов также применялась к вопросу о неоднородности, но все они не смогли пролить достаточно света на реальные ситуации. Продолжаются попытки найти подходящие способы количественной оценки неоднородности сети.[4]

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

  1. ^ а б [1] Чартран, Гэри, Пол Эрдош и Ортруд Р. Оллерманн. «Как определить нерегулярный график». College Math. J 19.1 (1988): 36–42.
  2. ^ Бехзад, Мехди и Гэри Чартранд. «Нет идеального графика». American Mathematical Monthly (1967): 962–963.
  3. ^ а б c d е ж грамм [2] Алави, Юсеф и др. «Сильно нерегулярные графики». Журнал теории графов 11.2 (1987): 235–249.
  4. ^ а б [3] Эстрада, Эрнесто. «Количественная оценка неоднородности сети». Physical Review E 82.6 (2010): 066102.