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

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

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

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

Регуля́рный (одноро́дный) графграф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается . Для нерегулярных графов не определено. Регулярные графы представляют особую сложность для многих алгоритмов.

Регулярный граф с вершинами степени называется регулярным графом степени , или ‑регулярным.

Регулярные графы степени не больше двух легко классифицировать: 0-регулярный граф состоит из изолированных вершин (нуль-граф), 1-регулярный — из изолированных рёбер, а 2-регулярный — из разрозненных циклов.

3-регулярный граф известен также как кубический.

Сильно регулярный граф есть регулярный граф, для которого существуют такие и , что любые две смежные вершины имеют общих соседей и любые две несмежные вершины имеют общих соседей. Наименьшие графы, которые регулярны, но не сильно регулярны — циклический граф и циркулянтный граф на шести вершинах.

Полный граф является сильно регулярным для любого .

Теорема Нэш-Вильямса[en] гласит, что каждый k‑регулярный граф на 2k + 1 вершинах имеет гамильтонов цикл.

Алгебраические свойства

Пусть A есть матрица смежности графа. Тогда граф регулярен тогда и только тогда, когда есть собственный вектор A[1]. Его собственное число будет постоянной степенью графа. Собственные векторы, соответствующие другим собственным числам, ортогональны , поэтому для собственных векторов мы имеем .

Регулярный граф степени k связен тогда и только тогда, когда собственное число k имеет единичную кратность[1].

Другой критерий регулярности и связности графа: граф связен и регулярен тогда и только тогда, когда матрица J с находится в алгебре смежности[en] графа[2].


Пусть G есть k-регулярный граф диаметра D и с собственными числами матрицы смежности . Если G не двудолен:

[3] [4]

где

.

Генерация

Регулярный граф можно сгенерировать программой GenReg.[5]

См. также

Примечания

  1. 1 2 Д. М. Цветкович, М. Дуб и Х. Сачс, «Спектр графов: теория и применение», 3-я редакция, Нью-Йорк: Уайли, 1998.
  2. Curtin, Brian (2005), "Algebraic characterizations of graph regularity conditions", Designs, Codes and Cryptography, 34 (2–3): 241—248, doi:10.1007/s10623-004-4857-4, MR 2128333
  3. Gregory Quenell. Spectral diameter estimates for k-regular graphs.
  4. Fan R.K. Chung. Spectral Graph Theory. — American Mathematical Society, 1997. — (CBMS). — ISBN 0821803158.
  5. М. Мерингер, "Теория графов", 1999, 30, 137.

Ссылки

  • Weisstein, Eric W. Regular Graph (англ.) на сайте Wolfram MathWorld.
  • Weisstein, Eric W. Strongly Regular Graph (англ.) на сайте Wolfram MathWorld.
  • GenReg программа и данные Маркуса Мерингера.
  • Nash-Williams, Crispin (1969), "Valency Sequences which force graphs to have Hamiltonian Circuits", University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo
Эта страница в последний раз была отредактирована 17 февраля 2024 в 06:25.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).