Два-граф

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

Два-графы не являются графами, и их не следует путать с другими объектами, которые называются 2-графами в теории графов, в частности, с 2-регулярными графами. Для их различения используется слово «два», а не цифра «2».

Два-графы были введены Хигманом (G. Higman) как естественные объекты, возникающие при работе с некоторыми простыми группами. С тех пор их изучали интенсивно Зайдель, Тэйлор и другие при изучении множеств равноугольных прямых, сильно регулярных графов и других объектов.

Примеры

На множестве вершин {1, ..., 6} следующий неупорядоченный набор троек является два-графом:

123  124  135  146  156  236  245  256  345  346

Этот два-граф является регулярным, поскольку любая пара различных вершин оказывается вместе в точности в трёх тройках.

Если дан обычный граф G = (V, E), то набор троек вершин из V, у которых порождённый подграф имеет нечётное число рёбер, образует два-граф на V. Любой два-граф можно представить в таком виде. Этот пример показывает стандартный путь построения два-графа из обычного графа.

Приведём более сложный пример. Пусть T — дерево с множеством рёбер E. Множество всех троек рёбер, не лежащих на одном пути в T образуют два-граф на множествеt E.

Переключение и графы

Два-граф эквивалентен классу переключения графов, а также (знаковому) классу переключения знаковых полных графов.

Переключение множества вершин в (обычном) графе означает смену смежности каждой пары вершин, одна из которых в множестве, а другая не в множестве — смежная пара становится несмежной, а несмежная пара становится смежной. Рёбра, конечные вершины которых находятся в множестве, или оба конца находятся вне множества, не меняются. Графы являются эквивалентными по переключению, если один может быть получен из другого путём переключения. Класс эквивалентности по переключению называется классом переключения. Переключение было введено Ван Линтом и Зайделем (van Lint, Seidel 1966) и развито Зайделем. Название переключение графов или переключение Зайделя было введено, в частности, чтобы отличить от переключения знаковых графов.

В стандартном построении два-графов из обычного графа, данном выше, два графа дают тот же самый два-граф в том и только том случае, когда они эквивалентны по переключению, то есть, они принадлежат тому же классу переключения.

Пусть Γ — два-граф на множестве X. Для любого элемента x из X определим граф с множеством вершин X, в котором вершины y и z смежны в том и только том случае, когда {x, y, z} принадлежит Γ. В этом графе x будет изолированной вершиной. Это построение обратимо. Если задан обычный граф G, добавим новый элемент x к множеству вершин G и определим два-граф, во всех тройках {x, y, z} которого вершины y и z являются смежными вершинами в G. Этот два-граф на языке блок-схем называется расширением графа G вершиной x. В заданном классе переключения регулярного два-графа пусть Γ_x — единственный граф, имеющий вершину x как изолированную (таковой всегда существует, просто нужно взять любой граф в классе и переключить относительно несмежных x вершин), и не включающий саму вершину x. То есть, два-граф является расширением Γ_x вершиной x. В примере регулярного два-графа Γ_x является циклом из 5 вершин для любого выбора x.

Графу G соответствует знаковый полный граф Σ на том же множестве вершин, рёбра которого отрицательны, если принадлежат G, и положительны, если не принадлежат G. И обратно, G является подграфом Σ и состоит из всех вершин и отрицательных рёбер. Два-граф G можно определить также как множество троек вершин, которые образуют отрицательный треугольник (треугольник с нечётным числом отрицательных рёбер) в Σ. Два знаковых полных графа дают тот же самый два-граф в том и только том случае, если они эквивалентны по переключению.

Переключения G и Σ связаны — переключение одних и тех же вершин даёт граф H и соответствующий ему знаковый полный граф.

Матрица смежности

Матрица смежности два-графа это матрица смежности соответствующего знакового полного графа. То есть, она симметрична, имеет нули на диагонали, и значения вне диагонали равны ±1. Если G является графом, соответствующим знаковому полному графу Σ, эта матрица называется (0, −1, 1) матрицей смежности или матрицей смежности Зайделя графа G. Матрица Зайделя имеет нули на главной диагонали, −1 для элементов, соответствующих смежным вершинам, и +1 для элементов, соответствующих несмежным вершинам.

Если графы G и H находятся в одном классе переключения, мультимножества собственных значений двух матриц смежности Зайделя для G и H совпадают, поскольку матрицы подобны.

Два-граф на множестве V является регулярным в том и только том случае, если её матрица смежности имеет только два различных собственных значения, скажем ρ₁ > 0 > ρ₂, где ρ₁ρ₂ = 1 − |V|.

Равноугольные прямые

Любой два-граф эквивалентен множеству прямых в некотором многомерном евклидовом пространстве, и угол между любой парой прямых из этого множества один и тот же. Множество прямых можно построить из два-графа с n вершинами следующим образом. Пусть −ρ — наименьшее собственное значение матрицы смежности Зайделя A два-графа, и предположим, что его кратность равна n − d. Тогда матрица ρI + A является положительно полуопределённой матрицей ранга d, и её можно представить как матрицу Грама скалярных произведений n векторов в евклидовом пространстве размерности d. Эти вектора также имеют одну и ту же норму (а именно, <math>\sqrt{\rho}</math>) и попарное скалярное произведение ±1, а угол между любой парой из n прямых, натянутых на эти вектора, равен φ, где cos φ = 1/ρ. Обратно, любое множество неортогональных прямых в евклидовом пространстве, угол между любой парой которых одинаков, даёт два-граф.

В обозначениях, приведённых выше, максимальная мощность n удовлетворяет неравенству n ≤ d(ρ² − 1)/(ρ² − d), и граница достигается в том и только том случае, когда два-граф регулярен.

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

Два-графы на X, состоящие из всех возможных троек из X, и пустые (не имеющие троек) являются регулярными два-графами, но их принято считать тривиальными два-графами и, как правило, они исключаются из рассмотрения.

Нетривиальный два-граф на множестве X является регулярным тогда и только тогда, когда для любого x из X граф Γ_x является сильно регулярным с k = 2μ (степень любой вершины вдвое больше числа вершин, смежных обеим из любой несмежной пары вершин). Если это условие выполняется для одного x из X, оно выполняется для всех элементов из X.

Отсюда следует, что нетривиальный регулярный два-граф имеет чётное число вершин.

Если G является регулярным графом, расширенный два-граф Γ которого имеет n вершин, то Γ является регулярным два-графом в том и только том случае, когда G является строго регулярным графом с собственными значениями k, r и s, для которых выполняется n = 2(k − r) или n = 2(k − s).

Литература

• A. E. Brouwer, A. M. Cohen, A. Neumaier. Параграфы 1.5, 3.8, 7.6C // Distance-Regular Graphs. — Berlin: Springer-Verlag, 1989.

• P. J. Cameron, J. H. van Lint. Designs, Graphs, Codes and their Links. — Cambridge University Press, 1991. — Т. 22. — (London Mathematical Society Student Texts). — ISBN 978-0-521-42385-4.

• Charles J. Colbourn, Jeffrey H. Dinitz. Handbook of Combinatorial Designs. — 2nd. — Boca Raton: Chapman & Hall/ CRC, 2007. — С. 875—882. — ISBN 1-58488-506-8.

• Chris Godsil, Gordon Royle. Глава 11 // Algebraic Graph Theory. — New York: Springer-Verlag, 2001. — Т. 207. — (Graduate Texts in Mathematics).

• J. J. Seidel. Colloquio Internazionale sulle Teorie Combinatorie. — Rome, 1973. — Т. I. — С. 481—511.

• D. E. Taylor. Proceedings of the London Mathematical Society. — 1977. — Т. 35. — С. 257—274.

• J. H. van Lint, J. J. Seidel Equilateral point sets in elliptic geometry // Indagationes Mathematicae. — 1966. — Т. 28. — С. 335—348.

Отрывок, характеризующий Два-граф

Ожидая уведомления о зачислении его в члены комитета, князь Андрей возобновил старые знакомства особенно с теми лицами, которые, он знал, были в силе и могли быть нужны ему. Он испытывал теперь в Петербурге чувство, подобное тому, какое он испытывал накануне сражения, когда его томило беспокойное любопытство и непреодолимо тянуло в высшие сферы, туда, где готовилось будущее, от которого зависели судьбы миллионов. Он чувствовал по озлоблению стариков, по любопытству непосвященных, по сдержанности посвященных, по торопливости, озабоченности всех, по бесчисленному количеству комитетов, комиссий, о существовании которых он вновь узнавал каждый день, что теперь, в 1809 м году, готовилось здесь, в Петербурге, какое то огромное гражданское сражение, которого главнокомандующим было неизвестное ему, таинственное и представлявшееся ему гениальным, лицо – Сперанский. И самое ему смутно известное дело преобразования, и Сперанский – главный деятель, начинали так страстно интересовать его, что дело воинского устава очень скоро стало переходить в сознании его на второстепенное место.
Князь Андрей находился в одном из самых выгодных положений для того, чтобы быть хорошо принятым во все самые разнообразные и высшие круги тогдашнего петербургского общества. Партия преобразователей радушно принимала и заманивала его, во первых потому, что он имел репутацию ума и большой начитанности, во вторых потому, что он своим отпущением крестьян на волю сделал уже себе репутацию либерала. Партия стариков недовольных, прямо как к сыну своего отца, обращалась к нему за сочувствием, осуждая преобразования. Женское общество, свет , радушно принимали его, потому что он был жених, богатый и знатный, и почти новое лицо с ореолом романической истории о его мнимой смерти и трагической кончине жены. Кроме того, общий голос о нем всех, которые знали его прежде, был тот, что он много переменился к лучшему в эти пять лет, смягчился и возмужал, что не было в нем прежнего притворства, гордости и насмешливости, и было то спокойствие, которое приобретается годами. О нем заговорили, им интересовались и все желали его видеть.
На другой день после посещения графа Аракчеева князь Андрей был вечером у графа Кочубея. Он рассказал графу свое свидание с Силой Андреичем (Кочубей так называл Аракчеева с той же неопределенной над чем то насмешкой, которую заметил князь Андрей в приемной военного министра).
– Mon cher, [Дорогой мой,] даже в этом деле вы не минуете Михаил Михайловича. C'est le grand faiseur. [Всё делается им.] Я скажу ему. Он обещался приехать вечером…
– Какое же дело Сперанскому до военных уставов? – спросил князь Андрей.
Кочубей, улыбнувшись, покачал головой, как бы удивляясь наивности Болконского.
– Мы с ним говорили про вас на днях, – продолжал Кочубей, – о ваших вольных хлебопашцах…
– Да, это вы, князь, отпустили своих мужиков? – сказал Екатерининский старик, презрительно обернувшись на Болконского.
– Маленькое именье ничего не приносило дохода, – отвечал Болконский, чтобы напрасно не раздражать старика, стараясь смягчить перед ним свой поступок.
– Vous craignez d'etre en retard, [Боитесь опоздать,] – сказал старик, глядя на Кочубея.
– Я одного не понимаю, – продолжал старик – кто будет землю пахать, коли им волю дать? Легко законы писать, а управлять трудно. Всё равно как теперь, я вас спрашиваю, граф, кто будет начальником палат, когда всем экзамены держать?
– Те, кто выдержат экзамены, я думаю, – отвечал Кочубей, закидывая ногу на ногу и оглядываясь.
– Вот у меня служит Пряничников, славный человек, золото человек, а ему 60 лет, разве он пойдет на экзамены?…
– Да, это затруднительно, понеже образование весьма мало распространено, но… – Граф Кочубей не договорил, он поднялся и, взяв за руку князя Андрея, пошел навстречу входящему высокому, лысому, белокурому человеку, лет сорока, с большим открытым лбом и необычайной, странной белизной продолговатого лица. На вошедшем был синий фрак, крест на шее и звезда на левой стороне груди. Это был Сперанский. Князь Андрей тотчас узнал его и в душе его что то дрогнуло, как это бывает в важные минуты жизни. Было ли это уважение, зависть, ожидание – он не знал. Вся фигура Сперанского имела особенный тип, по которому сейчас можно было узнать его. Ни у кого из того общества, в котором жил князь Андрей, он не видал этого спокойствия и самоуверенности неловких и тупых движений, ни у кого он не видал такого твердого и вместе мягкого взгляда полузакрытых и несколько влажных глаз, не видал такой твердости ничего незначащей улыбки, такого тонкого, ровного, тихого голоса, и, главное, такой нежной белизны лица и особенно рук, несколько широких, но необыкновенно пухлых, нежных и белых. Такую белизну и нежность лица князь Андрей видал только у солдат, долго пробывших в госпитале. Это был Сперанский, государственный секретарь, докладчик государя и спутник его в Эрфурте, где он не раз виделся и говорил с Наполеоном.
Сперанский не перебегал глазами с одного лица на другое, как это невольно делается при входе в большое общество, и не торопился говорить. Он говорил тихо, с уверенностью, что будут слушать его, и смотрел только на то лицо, с которым говорил.
Князь Андрей особенно внимательно следил за каждым словом и движением Сперанского. Как это бывает с людьми, особенно с теми, которые строго судят своих ближних, князь Андрей, встречаясь с новым лицом, особенно с таким, как Сперанский, которого он знал по репутации, всегда ждал найти в нем полное совершенство человеческих достоинств.
Сперанский сказал Кочубею, что жалеет о том, что не мог приехать раньше, потому что его задержали во дворце. Он не сказал, что его задержал государь. И эту аффектацию скромности заметил князь Андрей. Когда Кочубей назвал ему князя Андрея, Сперанский медленно перевел свои глаза на Болконского с той же улыбкой и молча стал смотреть на него.
– Я очень рад с вами познакомиться, я слышал о вас, как и все, – сказал он.
Кочубей сказал несколько слов о приеме, сделанном Болконскому Аракчеевым. Сперанский больше улыбнулся.
– Директором комиссии военных уставов мой хороший приятель – господин Магницкий, – сказал он, договаривая каждый слог и каждое слово, – и ежели вы того пожелаете, я могу свести вас с ним. (Он помолчал на точке.) Я надеюсь, что вы найдете в нем сочувствие и желание содействовать всему разумному.
Около Сперанского тотчас же составился кружок и тот старик, который говорил о своем чиновнике, Пряничникове, тоже с вопросом обратился к Сперанскому.
Князь Андрей, не вступая в разговор, наблюдал все движения Сперанского, этого человека, недавно ничтожного семинариста и теперь в руках своих, – этих белых, пухлых руках, имевшего судьбу России, как думал Болконский. Князя Андрея поразило необычайное, презрительное спокойствие, с которым Сперанский отвечал старику. Он, казалось, с неизмеримой высоты обращал к нему свое снисходительное слово. Когда старик стал говорить слишком громко, Сперанский улыбнулся и сказал, что он не может судить о выгоде или невыгоде того, что угодно было государю.
Поговорив несколько времени в общем кругу, Сперанский встал и, подойдя к князю Андрею, отозвал его с собой на другой конец комнаты. Видно было, что он считал нужным заняться Болконским.
– Я не успел поговорить с вами, князь, среди того одушевленного разговора, в который был вовлечен этим почтенным старцем, – сказал он, кротко презрительно улыбаясь и этой улыбкой как бы признавая, что он вместе с князем Андреем понимает ничтожность тех людей, с которыми он только что говорил. Это обращение польстило князю Андрею. – Я вас знаю давно: во первых, по делу вашему о ваших крестьянах, это наш первый пример, которому так желательно бы было больше последователей; а во вторых, потому что вы один из тех камергеров, которые не сочли себя обиженными новым указом о придворных чинах, вызывающим такие толки и пересуды.
– Да, – сказал князь Андрей, – отец не хотел, чтобы я пользовался этим правом; я начал службу с нижних чинов.
– Ваш батюшка, человек старого века, очевидно стоит выше наших современников, которые так осуждают эту меру, восстановляющую только естественную справедливость.
– Я думаю однако, что есть основание и в этих осуждениях… – сказал князь Андрей, стараясь бороться с влиянием Сперанского, которое он начинал чувствовать. Ему неприятно было во всем соглашаться с ним: он хотел противоречить. Князь Андрей, обыкновенно говоривший легко и хорошо, чувствовал теперь затруднение выражаться, говоря с Сперанским. Его слишком занимали наблюдения над личностью знаменитого человека.
– Основание для личного честолюбия может быть, – тихо вставил свое слово Сперанский.
– Отчасти и для государства, – сказал князь Андрей.
– Как вы разумеете?… – сказал Сперанский, тихо опустив глаза.
– Я почитатель Montesquieu, – сказал князь Андрей. – И его мысль о том, что le рrincipe des monarchies est l'honneur, me parait incontestable. Certains droits еt privileges de la noblesse me paraissent etre des moyens de soutenir ce sentiment. [основа монархий есть честь, мне кажется несомненной. Некоторые права и привилегии дворянства мне кажутся средствами для поддержания этого чувства.]
Улыбка исчезла на белом лице Сперанского и физиономия его много выиграла от этого. Вероятно мысль князя Андрея показалась ему занимательною.
– Si vous envisagez la question sous ce point de vue, [Если вы так смотрите на предмет,] – начал он, с очевидным затруднением выговаривая по французски и говоря еще медленнее, чем по русски, но совершенно спокойно. Он сказал, что честь, l'honneur, не может поддерживаться преимуществами вредными для хода службы, что честь, l'honneur, есть или: отрицательное понятие неделанья предосудительных поступков, или известный источник соревнования для получения одобрения и наград, выражающих его.