Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Сильно регулярный граф

Из Википедии — свободной энциклопедии

Граф Пэли 13-го порядка, сильно регулярный граф с параметрами srg(13,6,2,3).

Сильно регулярный граф — вариация понятия регулярный граф.

Определение

Пусть регулярный граф с вершинами и степенью . Говорят, что является сильно регулярным, если существуют целые и такие, что:

  • Любые две несмежные вершины имеют общих соседей.

Замечания

  • Графы описанного типа иногда обозначаются как .

Свойства

  • Сильно регулярный граф является дистанционно-регулярным с диаметром , только в том случае, когда .
  • Четыре параметра в не являются независимыми и должны удовлетворять следующему условию:

Это условие можно получить очень просто, если подсчитать аргументы следующим образом:

  • Представим вершины графа лежащими на трёх уровнях. Выберем любую вершину как корень, уровень . Тогда её соседних вершин лежат на уровне , а все оставшиеся лежат на уровне .
  • Вершины уровня связаны непосредственно с корнем, а потому они должны иметь других соседей, являющихся соседями корня, и эти соседи должны также лежать на уровне . Поскольку каждая вершина имеет степень , имеется рёбер, соединяющих каждую вершину уровня с уровнем .
  • Вершины уровня не связаны непосредственно с корнем, а потому они должны иметь общих соседей с корнем, и все эти соседи должны лежать на уровне . Таким образом, вершин уровня связаны с каждой вершиной уровня и каждая из вершин на уровне 1 связана с вершин на уровне . Получаем, что число вершин на уровне равно .
  • Полное число вершин на всех трёх уровнях, таким образом, равно и после преобразования, получим .
  • Пусть обозначает единичную матрицу (порядка ) и пусть обозначает матрицу, все элементы которой равны . Матрица смежности сильно регулярного графа имеет следующие свойства:

    • (Это тривиальное перефразирование требования равенства степени вершин числу ).

    • (Первый член, , даёт число двухшаговых путей из любой вершины ко всем вершинам. Второй член, , соответствует непосредственно связанным рёбрам. Третий член,, соответствует тривиальным парам, когда вершины в паре те же самые).
  • Граф имеет в точности три собственных значения:
    • , кратность[en] которого равна 1
    • , кратность которого равна
    • , кратность которого равна
  • Сильно регулярные графы, для которых , называются конференсными ввиду их связи с симметричными конференсными матрицами. Число независимых параметров этих графов сокращается до одного — .
  • Сильно регулярные графы, для которых , имеют целочисленные собственные значения с неравными кратностями.
  • Дополнение также сильно регулярно — это .

Примеры

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

Графы Мура

Сильно регулярные графы с не содержат треугольников. Кроме полных графов с числом вершин меньше 3 и всех полных двудольных графов семь приведённых выше — это все известные графы этого вида. Сильно регулярные графы с и являются графами Мура с обхватом 5. Опять, три графа, приведённые выше, с параметрами , и , являются единственными известными графами этого вида. Единственное другое возможное множество параметров, соответствующее графам Мура — это . Неизвестно, существует ли такой граф, и если существует, единственный ли он.

См. также

  • Матрица смежности Зайделя[en]

Примечания

  1. Brouwer, 2012, с. 101.
  2. Godsil, 2001, с. 218.
  3. Weisstein, Eric W. Schläfli graph (англ.) на сайте Wolfram MathWorld.

Литература

  • Brouwer A.E., Cohen A.M., Neumaier A. Distance Regular Graphs (англ.). — Berlin, New York: Springer-Verlag, 1989. — ISBN 3-540-50619-5.
  • Brouwer A.E., Haemers W.H. Spectra of Graphs (англ.). — New York: Springer-Verlag, 2012. — Vol. 418. — (Universitext). — ISBN 978-1-4614-1938-9.
  • Godsil C., Royle G. Algebraic Graph Theory (англ.). — New York: Springer-Verlag, 2001. — ISBN 0-387-95241-1.

Ссылки

Эта страница в последний раз была отредактирована 11 ноября 2022 в 10:47.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).