Целый граф

Перейти к навигации Перейти к поиску

Целый граф (целочисленный граф) — граф, спектр матрицы смежности (инвариант графа) которого состоит полностью из целых чисел. Другими словами, граф является целым графом, при условии, что все корни характеристического многочлена его матрицы смежности являются целыми числами^[1]. Понятие ввели в 1974 году Харари и Швенк^[2].

Примеры:

полный граф $K_{n}$ является целым для всех $n$ ;
граф без рёбер ${\bar {K}}_{n}$ является целым для всех $n$ ;
среди кубических симметричных графов целыми являются коммунальный граф, граф Петерсена, граф Науру и граф Дезарга;
целыми являются также граф Хигмана — Симса, граф Холла — Янко, граф Клебша, граф Хоффмана — Синглтона, граф Шрикханде и граф Хоффмана, Граф Госсета;
графы судоку, вершины которых представляют ячейки поля Судоку, а рёбра представляют ячейки, которые не должны быть равны, являются целыми графами^[3].

Регулярный граф является периодическим^[англ.] тогда и только тогда, когда он целый. Граф регулярных блужданий, удовлетворяющий условиям идеальной передачи квантового состояния^[англ.], является целым графом.

Примечания

↑ Weisstein, Eric W. Integral Graph (англ.) на сайте Wolfram MathWorld.
↑ Harary F., Schwenk A. J. Which Graphs have Integral Spectra? // Graphs and Combinatorics / R. Bari и F. Harary. — Berlin: Springer-Verlag, 1974. — С. 45—51.
↑ Torsten Sander. Sudoku graphs are integral // Electronic Journal of Combinatorics. — 2009. — Т. 16, вып. 1. — С. Note 25, 7. Архивировано 15 апреля 2011 года.

Похожие исследовательские статьи

Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.

<span class="mw-page-title-main">Прямое произведение графов</span>

Декартово произведение или прямое произведение G $\text{[math]}$ H графов G и H — это граф, такой, что

множество вершин графа G $\text{[math]}$ H — это прямое произведение V(G) × V(H)
любые две вершины (u,u') и (v,v') смежны в G $\text{[math]}$ H тогда и только тогда, когда
- либо u=v и u' смежна v' в H
- либо u' =v' и u смежна v в G.

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна. Полный граф с $\text{[math]}$ вершинами имеет $\text{[math]}$ рёбер и обозначается $\text{[math]}$ . Является регулярным графом степени $\text{[math]}$ .

<span class="mw-page-title-main">Регулярный граф</span> граф, степени всех вершин которого равны

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

В теории графов изоморфизмом графов $\text{[math]}$ и $\text{[math]}$ называется биекция между множествами вершин графов $\text{[math]}$ такая, что любые две вершины $\text{[math]}$ и $\text{[math]}$ графа $\text{[math]}$ смежны тогда и только тогда, когда вершины $\text{[math]}$ и $\text{[math]}$ смежны в графе $\text{[math]}$ . Здесь графы понимаются неориентированными и не имеющими весов вершин и ребер. В случае, если понятие изоморфизма применяется к ориентированным или взвешенным графам, накладываются дополнительные ограничения на сохранение ориентации дуг и значений весов. Если изоморфизм графов установлен, они называются изоморфными и обозначаются как $\text{[math]}$ .

<span class="mw-page-title-main">Циркулянтный граф</span> неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую верши

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

В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы.

<span class="mw-page-title-main">Дистанционно-транзитивный граф</span> такой граф, что для любых двух заданных вершин v и w, находящихся на расстоянии i, и любых двух вершин x и y, находящихся на том же расстоянии, су

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

<span class="mw-page-title-main">Сильно регулярный граф</span> регулярный граф с v вершинами и степенью k, у которого число общих соседей зависит только от смежности пары вершин

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

<span class="mw-page-title-main">Граф гиперкуба</span> регулярный граф с 2^n вершинами, 2^(n−1)n рёбрами и n рёбрами, сходящимися в одной вершине

В теории графов графом гиперкуба Q_n называется регулярный граф с 2ⁿ вершинами, 2ⁿ⁻¹n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q₃ — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества отличаются только одним элементом.

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

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

Двудольное двойное покрытие неориентированного графа G — это двудольный накрывающий граф графа G с двойным числом вершин по сравнению с G. Покрытие можно построить как тензорное произведение графов, G × K₂. Это покрытие также называется двойным покрытием Кронекера или каноническим двойным покрытием графа G.

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

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

<span class="mw-page-title-main">Тензорное произведение графов</span>

Тензорное произведение $\text{[math]}$ графов $\text{[math]}$ и $\text{[math]}$ — граф, множество вершин которого есть декартово произведение $\text{[math]}$ , причём различные вершины $\text{[math]}$ и $\text{[math]}$ смежны в $\text{[math]}$ тогда и только тогда, когда $\text{[math]}$ смежна с $\text{[math]}$ и $\text{[math]}$ смежна с $\text{[math]}$ .

Линейная древесность неориентированного графа — это наименьшее число линейных лесов, на которые может быть разбит граф. Здесь линейный лес — это ациклический граф с максимальной степенью два, то есть дизъюнктное объединение путей.

Граф судоку — это неориентированный граф, вершины которого представляют ячейки (пустой) головоломки судоку, а рёбра представляют пары ячеек, которые принадлежат той же строке, тому же столбцу или блоку головоломки. Задача головоломки судоку может быть представлена как расширение предварительной раскраски на этом графе. Граф является целочисленным графом Кэли.

Граф Брауэра — Хемерса — 20-регулярный неориентированный граф с 81 вершиной и 810 рёбрами. Это сильно регулярный, дистанционно-транзитивный граф и граф Рамануджана. Хотя его построение является математическим фольклором, он был назван именами Андреаса Брауэра и Уиллема Х. Хемерса, которые доказали его единственность в качестве строго регулярного графа.

Граф Берлекэмпа — ван Линта — Зейделя — это локально линейный сильно регулярный граф с параметрами (243,22,1,2), это означает, что граф имеет 243 вершины, 22 ребра на вершину, в точности одну общую вершину для каждой пары смежных вершин и в точности две общие вершины для любой пары несмежных. Граф построили Элвин Берлекэмп, Дж. Г. ван Линт и Йохан Якоб Зайдель как граф смежности троичных кодов Голея.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.