Граф Мура

Граф Мура — регулярний граф степеня $d$ і діаметра $k$, число вершин якого дорівнює верхній межі

$1+d\sum _{i=0}^{k-1}(d-1{)}^i.$

Еквівалентне визначення графа Мура — це граф діаметра $k$ з обхватом $2k+1$. Ще одне еквівалентне визначення графа Мура $G$ — це граф із обхватом $g=2k+1$, що має рівно $\frac{n}{g}(m-n+1)$ циклів довжини $g$, де $n$, $m$ — число вершин і ребер графа $G$. Графи, фактично, екстремальні щодо числа циклів, довжина яких дорівнює обхвату графаШаблон:Sfn.

Шаблон:Не перекладено і Роберт СінглтонШаблон:Sfn назвали граф ім'ям Едварда Мура, який поставив питання опису та класифікації таких графів.

Маючи максимально можливе число вершин для заданої комбінації степеня і діаметра, графи Мура мають мінімально можливе число вершин для регулярних графів із заданими степенем і обхватом. Таким чином, будь-який граф Мура є кліткоюШаблон:Sfn. Формулу для числа вершин графа Мура можна узагальнити для можливості визначення графів Мура з парним обхватом, і ці графи знову ж є клітками.

Межі числа вершин за степенем і діаметром

Граф Петерсена як граф Мура. Будь-яке дерево пошуку в ширину має $d(d-1{)}^i$ вершин у його i-ому рівні.

Нехай $G$ — будь-який граф із найбільшим степенем $d$ і діаметром $k$, тоді візьмемо дерево, утворене пошуком у ширину, з коренем у вершині $v$. Це дерево має 1 вершину рівня 0 (сама вершина $v$), і максимум $d$ вершин рівня 1 (сусіди вершини $v$). На наступному рівні є максимум $d(d-1)$ вершин — кожен сусід вершини $v$ використовує одне ребро для з'єднання з вершиною $v$, так що має максимум $d-1$ сусідів рівня 2. У загальному випадку подібні доводи показують, що на будь-якому рівні $1\le i\le k$ може бути не більше $d(d-1{)}^i$ вершин. Таким чином, загальне число вершин може бути не більшим від

$1+d\sum _{i=0}^{k-1}(d-1{)}^i.$

Гоффман і СінглтонШаблон:Sfn спочатку визначили граф Мура як граф, для якого ця межа числа вершин досягається. Таким чином, будь-який граф Мура має максимально можливе число вершин серед усіх графів, у яких степінь не перевершує $d$, а діаметр — $k$.

Пізніше СінглтонШаблон:Sfn показав, що графи Мура можна еквівалентно визначити як граф, що має діаметр $k$ і обхват $2k-1$. Ці дві вимоги комбінуються, з чого виводиться d-регулярність графа для деякого $d$.

Графи Мура як клітки

Замість верхньої межі числа вершин у графі в термінах його найбільшого степеня і діаметра ми можемо використовувати нижню межу числа вершин у термінах найменшого степеня і обхватуШаблон:Sfn. Припустимо, що граф $G$ має найменший степінь $d$ і обхват $2k+1$. Виберемо довільну початкову вершину $v$ і, як і раніше, уявимо дерево пошуку в ширину з коренем у $v$. Це дерево повинне мати одну вершину рівня 0 (сама вершина $v$) і щонайменше $d$ вершин на рівні 1. На рівні 2 (для $k>1$), має бути щонайменше $d(d-1)$ вершин, оскільки кожна вершина на рівні $l$ має щонайменше ще $d-1$ зв'язків, і ніякі дві вершини рівня 1 не можуть бути суміжними або мати спільні вершини рівня 2, оскільки утворився б цикл, коротший, ніж обхват. У загальному випадку схожі доводи показують, що на будь-якому рівні $1\le i\le k$ має бути принаймні $d(d-1{)}^i$ вершин. Таким чином, загальне число вершин має бути не менше від

$1+d\sum _{i=0}^{k-1}(d-1{)}^i.$

У графі Мура це число вершин досягається. Кожен граф Мура має обхват рівно $2k+1$ — він не має достатньо вершин, щоб мати більший обхват, а коротший цикл призвів би до нестачі вершин на перших $k$ рівнях деяких дерев пошуку в ширину. Таким чином, будь-який граф Мура має мінімально можливе число вершин серед усіх графів з мінімальним степенем $d$ і діаметром $k$ — він є кліткою.

Для парного обхвату $2k$ можна утворити аналогічне дерево пошуку в ширину, починаючи зі середини одного ребра. Отримуємо межу мінімального числа вершин у графі цього обхвату з мінімальним степенем $d$

$2\sum _{i=0}^{k-1}(d-1{)}^i=1+(d-1{)}^{k-1}+d\sum _{i=0}^{k-2}(d-1{)}^i.$

Таким чином, до графів Мура іноді відносять графи, на яких ця межа досягається. Знову ж, будь-який такий граф є кліткою.

Приклад

Теорема Гоффмана — Сінглтона стверджує, що будь-який граф Мура з обхватом 5 повинен мати степінь 2, 3, 7 або 57. Графами Мура є:

• Повні графи $K_n$ з N > 2 вершинами (діаметр 1, обхват 3, степінь n-1, порядок $n$).
• Непарний цикл $C_{2n+1}$ (діаметр $n$, обхват $2n+1$, степінь 2, порядок 2n+1).
• Граф Петерсена (діаметр 2, обхват 5, степінь 3, порядок 10).
• Граф Гоффмана-Сінглтона (діаметр 2, обхват 5, степінь 7, порядок 50).
• Гіпотетичний граф з діаметром 2, обхватом 5, степенем 57 і порядком 3250, нині невідомо, чи такий існує.

Хіґман показав, що, на відміну від інших графів Мура, невідомий граф не може бути вершинно-транзитивним. Мачай і Ширан пізніше показали, що порядок автоморфізмів такого графа не перевищує 375.

В узагальненому визначенні графів Мура, де дозволяється парний обхват, графи з парним обхватом відповідають графам інцидентності (можливо вироджених) узагальнених багатокутників. Кілька прикладів — парні цикли $C_{2n}$, повні двочасткові графи $K_{n,n}$ з обхватом чотири, граф Хівуда зі степенем 3 і обхватом 6 і граф Татта — Коксетера зі степенем 3 і обхватом 8. ВідомоШаблон:SfnШаблон:Sfn, що всі графи Мура, крім перерахованих вище, повинні мати обхват 5, 6, 8 або 12. Випадок парного обхвату випливає з теореми Фейта — Хіґмана про можливі значення $n$ для узагальнених n-кутників.

Див. також

• Задача степеня — діаметра
• Шаблон:Не перекладено

Література

• Шаблон:Стаття
• Шаблон:Книга.
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття.
• Шаблон:Стаття
• Шаблон:Стаття.
• Шаблон:Стаття

Посилання

• Шаблон:Не перекладено і Віллем Гемерс (Willem H. Haemers): Spectra of graphs Шаблон:Webarchive
• Шаблон:MathWorld
• Шаблон:MathWorld