Граф Мура: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Спасено источников — 1, отмечено мёртвыми — 0. #IABot (v2.0beta) |
Kalendar (обсуждение | вклад) оформление |
||
Строка 11:
== Границы числа вершин по степени и диаметру ==
[[Файл:Petersen-as-Moore.svg|thumb| [[Граф Петерсена]] как граф Мура. Любое дерево [[Поиск в ширину|поиска в ширину]] имеет <math>d(d-1)^i</math> вершин в его ''i''-ом уровне.]]
Пусть <math>G</math> — любой граф с максимальной степенью <math>d</math> и диаметром <math>k</math>, тогда возьмём дерево, образованное [[Поиск в ширину|поиском в ширину]], с корнем в вершине <math>v</math>. Это дерево имеет 1 вершину уровня 0 (сама вершина <math>v</math>), и максимум <math>d</math> вершин уровня 1
(соседи вершины <math>v</math>). На следующем уровне имеется максимум <math>d(d-1)</math> вершин — каждый сосед вершины <math>v</math> использует одно ребро для соединения с вершиной <math>v</math>, так что имеет максимум <math>d-1</math> соседей уровня 2. В общем случае подобные доводы показывают, что на любом уровне <math>1\leq{i}\leq{k}</math> может быть не больше <math>d(d-1)^i</math> вершин. Таким образом, общее число вершин может быть не больше
: <math>1+d\sum_{i=0}^{k-1}(d-1)^i.</math>
Строка 22:
: <math>1+d\sum_{i=0}^{k-1}(d-1)^i.</math>
В графе Мура это число вершин достигается. Каждый граф Мура имеет обхват в точности <math>2k+1</math> — он не имеет достаточно вершин, чтобы иметь больший обхват, а более короткий цикл привёл бы к недостатку вершин в первых <math>k</math> уровнях некоторых деревьев поиска в ширину.
Таким образом, любой граф Мура имеет минимально возможное число вершин среди всех графов с минимальной степенью <math>d</math> и диаметром <math>k</math> — он является [[Клетка (теория графов)|клеткой
Для чётного обхвата <math>2k</math> можно образовать аналогичное дерево поиска в ширину, начиная с середины одного ребра. Получаем границу минимального числа вершин в графе этого обхвата с минимальной степенью <math>d</math>
Строка 37:
* Гипотетический граф с диаметром 2, обхватом 5, степенью 57 и порядком 3250, в настоящее время неизвестно, существует ли такой.
В обобщённом определении графов Мура, где разрешается чётный обхват, графы с чётным обхватом соответствуют графам инцидентности (возможно вырожденных) [[Обобщённый многоугольник|обобщённых многоугольников]]. Несколько примеров — чётные циклы <math> C_{2n} </math>, [[Полный двудольный граф|полные двудольные графы]] <math> K_{n,n} </math> с обхватом четыре, [[граф Хивуда]] со степенью 3 и обхватом 6 и [[граф Татта — Коксетера]] со степенью 3 и обхватом 8. Известно{{sfn|Bannai, Ito|1973}}{{sfn|Damerell|1973}}), что все графы Мура, кроме перечисленных выше, должны иметь обхват 5, 6, 8 или 12. Случай чётного обхвата следует из теоремы Фейта-Хигмана о возможных значениях <math>n</math> для обобщённых n-угольников.
| |||