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

Алгебраическая теория графов — это ветвь математики, в которой применяются алгебраические методы к задачам с графами. Другие подходы к задачам с графами – это геометрический, комбинаторный и алгоритмический. Существует три основные ветви алгебраической теории графов — две ветви используют линейную алгебру и теорию групп, а одна ветвь изучает инварианты графа.

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

Использующие линейную алгебру

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

Использующие теорию групп

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

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

Изучение инвариантов графа

Наконец, третья ветвь алгебраической теории графов работает с алгебраическими свойствами инвариантов графов, в частности, с хроматическими многочленами, многочленами Татта и инвариантами узлов. Хроматический многочлен графа, например, подсчитывает число его правильных раскрасок вершин. Для графа Петерсена этот многочлен равен <math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math> . В частности, это означает, что граф Петерсена нельзя раскрасить правильно одним или двумя цветами, но тремя цветами его можно раскрасить 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).

Отрывок, характеризующий Алгебраическая теория графов

Пьер с искренностью отвечал Анне Павловне утвердительно на вопрос ее об искусстве Элен держать себя. Ежели он когда нибудь думал об Элен, то думал именно о ее красоте и о том не обыкновенном ее спокойном уменьи быть молчаливо достойною в свете.
Тетушка приняла в свой уголок двух молодых людей, но, казалось, желала скрыть свое обожание к Элен и желала более выразить страх перед Анной Павловной. Она взглядывала на племянницу, как бы спрашивая, что ей делать с этими людьми. Отходя от них, Анна Павловна опять тронула пальчиком рукав Пьера и проговорила:
– J'espere, que vous ne direz plus qu'on s'ennuie chez moi, [Надеюсь, вы не скажете другой раз, что у меня скучают,] – и взглянула на Элен.
Элен улыбнулась с таким видом, который говорил, что она не допускала возможности, чтобы кто либо мог видеть ее и не быть восхищенным. Тетушка прокашлялась, проглотила слюни и по французски сказала, что она очень рада видеть Элен; потом обратилась к Пьеру с тем же приветствием и с той же миной. В середине скучливого и спотыкающегося разговора Элен оглянулась на Пьера и улыбнулась ему той улыбкой, ясной, красивой, которой она улыбалась всем. Пьер так привык к этой улыбке, так мало она выражала для него, что он не обратил на нее никакого внимания. Тетушка говорила в это время о коллекции табакерок, которая была у покойного отца Пьера, графа Безухого, и показала свою табакерку. Княжна Элен попросила посмотреть портрет мужа тетушки, который был сделан на этой табакерке.
– Это, верно, делано Винесом, – сказал Пьер, называя известного миниатюриста, нагибаясь к столу, чтоб взять в руки табакерку, и прислушиваясь к разговору за другим столом.
Он привстал, желая обойти, но тетушка подала табакерку прямо через Элен, позади ее. Элен нагнулась вперед, чтобы дать место, и, улыбаясь, оглянулась. Она была, как и всегда на вечерах, в весьма открытом по тогдашней моде спереди и сзади платье. Ее бюст, казавшийся всегда мраморным Пьеру, находился в таком близком расстоянии от его глаз, что он своими близорукими глазами невольно различал живую прелесть ее плеч и шеи, и так близко от его губ, что ему стоило немного нагнуться, чтобы прикоснуться до нее. Он слышал тепло ее тела, запах духов и скрып ее корсета при движении. Он видел не ее мраморную красоту, составлявшую одно целое с ее платьем, он видел и чувствовал всю прелесть ее тела, которое было закрыто только одеждой. И, раз увидав это, он не мог видеть иначе, как мы не можем возвратиться к раз объясненному обману.
«Так вы до сих пор не замечали, как я прекрасна? – как будто сказала Элен. – Вы не замечали, что я женщина? Да, я женщина, которая может принадлежать всякому и вам тоже», сказал ее взгляд. И в ту же минуту Пьер почувствовал, что Элен не только могла, но должна была быть его женою, что это не может быть иначе.
Он знал это в эту минуту так же верно, как бы он знал это, стоя под венцом с нею. Как это будет? и когда? он не знал; не знал даже, хорошо ли это будет (ему даже чувствовалось, что это нехорошо почему то), но он знал, что это будет.
Пьер опустил глаза, опять поднял их и снова хотел увидеть ее такою дальнею, чужою для себя красавицею, какою он видал ее каждый день прежде; но он не мог уже этого сделать. Не мог, как не может человек, прежде смотревший в тумане на былинку бурьяна и видевший в ней дерево, увидав былинку, снова увидеть в ней дерево. Она была страшно близка ему. Она имела уже власть над ним. И между ним и ею не было уже никаких преград, кроме преград его собственной воли.
– Bon, je vous laisse dans votre petit coin. Je vois, que vous y etes tres bien, [Хорошо, я вас оставлю в вашем уголке. Я вижу, вам там хорошо,] – сказал голос Анны Павловны.
И Пьер, со страхом вспоминая, не сделал ли он чего нибудь предосудительного, краснея, оглянулся вокруг себя. Ему казалось, что все знают, так же как и он, про то, что с ним случилось.
Через несколько времени, когда он подошел к большому кружку, Анна Павловна сказала ему:
– On dit que vous embellissez votre maison de Petersbourg. [Говорят, вы отделываете свой петербургский дом.]
(Это была правда: архитектор сказал, что это нужно ему, и Пьер, сам не зная, зачем, отделывал свой огромный дом в Петербурге.)
– C'est bien, mais ne demenagez pas de chez le prince Ваsile. Il est bon d'avoir un ami comme le prince, – сказала она, улыбаясь князю Василию. – J'en sais quelque chose. N'est ce pas? [Это хорошо, но не переезжайте от князя Василия. Хорошо иметь такого друга. Я кое что об этом знаю. Не правда ли?] А вы еще так молоды. Вам нужны советы. Вы не сердитесь на меня, что я пользуюсь правами старух. – Она замолчала, как молчат всегда женщины, чего то ожидая после того, как скажут про свои года. – Если вы женитесь, то другое дело. – И она соединила их в один взгляд. Пьер не смотрел на Элен, и она на него. Но она была всё так же страшно близка ему. Он промычал что то и покраснел.
Вернувшись домой, Пьер долго не мог заснуть, думая о том, что с ним случилось. Что же случилось с ним? Ничего. Он только понял, что женщина, которую он знал ребенком, про которую он рассеянно говорил: «да, хороша», когда ему говорили, что Элен красавица, он понял, что эта женщина может принадлежать ему.
«Но она глупа, я сам говорил, что она глупа, – думал он. – Что то гадкое есть в том чувстве, которое она возбудила во мне, что то запрещенное. Мне говорили, что ее брат Анатоль был влюблен в нее, и она влюблена в него, что была целая история, и что от этого услали Анатоля. Брат ее – Ипполит… Отец ее – князь Василий… Это нехорошо», думал он; и в то же время как он рассуждал так (еще рассуждения эти оставались неоконченными), он заставал себя улыбающимся и сознавал, что другой ряд рассуждений всплывал из за первых, что он в одно и то же время думал о ее ничтожестве и мечтал о том, как она будет его женой, как она может полюбить его, как она может быть совсем другою, и как всё то, что он об ней думал и слышал, может быть неправдою. И он опять видел ее не какою то дочерью князя Василья, а видел всё ее тело, только прикрытое серым платьем. «Но нет, отчего же прежде не приходила мне в голову эта мысль?» И опять он говорил себе, что это невозможно; что что то гадкое, противоестественное, как ему казалось, нечестное было бы в этом браке. Он вспоминал ее прежние слова, взгляды, и слова и взгляды тех, кто их видал вместе. Он вспомнил слова и взгляды Анны Павловны, когда она говорила ему о доме, вспомнил тысячи таких намеков со стороны князя Василья и других, и на него нашел ужас, не связал ли он уж себя чем нибудь в исполнении такого дела, которое, очевидно, нехорошо и которое он не должен делать. Но в то же время, как он сам себе выражал это решение, с другой стороны души всплывал ее образ со всею своею женственной красотою.