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

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

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

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

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

Высокосимметричный граф Петерсена, который является вершинно-транзитивным, симметричным, дистанционно-транзитивным и дистанционно-регулярным. Диаметр графа равен 2. Группа автоморфизмов графа содержит 120 элементов и, фактически, является симметрической группой .

Алгебраическая теория графов — направление в теории графов, применяющее алгебраические методы к теоретико-графовым задачам (в дополнение к геометрическому[en], комбинаторному и алгоритмическому направлениям). В свою очередь, алгебраическая теория графов подразделяется на три ветви: линейно-алгебраическую[⇨], теоретико-групповую[⇨] и изучающую инварианты графов[⇨].

Граф Кэли для знакопеременной группы A4, образующий Усечённый тетраэдр в трёхмерном пространстве. Все графы Кэли вершинно-транзитивны, но некоторые вершинно-транзитивные графы (например, граф Петерсена) не являются графами Кэли.

Энциклопедичный YouTube

  • 1/3
    Просмотров:
    969
    1 652
    34 251
  • 06 - Основы теории графов. Эйлеровы графы
  • 02 - Основы теории графов. Маршруты, пути, циклы. Понятие связности. Двудольные графы.
  • Операции над множествами

Субтитры

Линейная алгебра

Характерный представитель линейно-алгебраической ветви — спектральная теория графов, в которой изучаются спектры матрицы смежности или матрицы Кирхгофа графа. Для графа Петерсена, например, спектр смежной матрицы равен (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Некоторые теоремы связывают свойства спектра с другими инвариантами графа. В качестве простого примера, связный граф с диаметром будет иметь по меньшей мере различных значений в своём спектре[1]. Свойства спектра графа используются для анализа синхронизуемости сетей[en].

Правильная раскраска вершин графа Петерсена тремя цветами, минимально возможным числом цветов. Из хроматического многочлена следует, что существует 120 таких раскрасок в 3 цвета.

Теория групп

В теорико-групповой ветви используются методы общей алгебры и алгебраической комбинаторики, широко задействуется геометрическая теория групп; одна из основных изучаемых конструкций — автоморфизмы графов (образующие группу). Внимание уделяется различным семействам графов, основанных на симметрии (такие как симметричные графы, вершинно-транзитивные графы, рёберно-транзитивные графы, дистанционно-транзитивные графы, дистанционно-регулярные графы и сильно регулярные графы), и связям между этими семействами. Некоторые из этих категорий имеют малое число графов, так что их можно все перечислить. По теореме Фрухта все группы могут быть представлены как группы автоморфизмов связных графов (более того, кубических графов)[2]. Другая связь с теорией групп — если задана любая группа, могут быть образованы графы, известные как графы Кэли, и они имеют свойства, связанные со структурой графа[1].

Групповая ветвь тесно связана с линейно-алгебраической, поскольку свойства симметрии графа отражаются в его спектре. В частности, спектр графа с высокой симметрией, такого как граф Петерсена, имеет мало различных собственных значений[1] (у графа Петерсена 3 значения, что является минимальным возможным числом для такого графа с диаметром, как у графа Петерсена). Для графов Кэли спектр может быть связан прямо со структурой группы, в частности, с её неприводимыми представлениями[1][3].

Инварианты графов

Алгебраические свойства инвариантов графов, таких, как хроматические многочлены, многочлены Татта, инварианты узлов, позволяют изучать структуру графов алгебраическими средствами. Например, хроматический многочлен графа, подсчитывает число его правильных раскрасок вершин; для графа Петерсена этот многочлен равен:

[1],

в частности, это означает, что граф Петерсена нельзя раскрасить правильно одним или двумя цветами, но тремя цветами его можно раскрасить 120 различными способами. Много работ в этой области связано с попытками доказать теорему о четырёх красках. Остаётся много открытых вопросов, связанных с инвариантами, например, таких, как определение графов, имеющих тот же самый хроматический многочлен, и определение, какие многочлены являются хроматическими.

См. также

Примечания

Литература

  • R. Frucht. Graphs of Degree 3 with given abstract group // Canad. J. Math.. — 1949. — Вып. 3.
  • Norman Biggs. Algebraic Graph Theory. — 2nd. — Cambridge: Cambridge University Press, 1993. — ISBN 0-521-45897-8.
  • L Babai. Handbook of Combinatorics / R Graham, M Grötschel, L Lovász. — Elsevier, 1996.
  • Chris Godsil, Gordon Royle. Algebraic Graph Theory. — New York: Springer-Verlag, 2001. — Т. 207. — (Graduate Texts in Mathematics).
Эта страница в последний раз была отредактирована 25 июля 2021 в 23:25.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).