Конференсный граф

Конференсный граф — сильно регулярный граф с параметрами v, k = (v − 1)/2, λ = (v − 5)/4, и μ = (v − 1)/4. Этот граф соответствует симметричной конференсной матрице, и, следовательно, его порядок v должен быть сравним с 1 по модулю 4 и быть суммой двух квадратов.

Известно, что конференсные графы существуют для всех малых значений v, удовлетворяющих ограничениям, например, v = 5, 9, 13, 17, 25, 29, и (графы Пэли) для всех степеней простых чисел, сравнимых с 1 по модулю 4. Однако существует много значений v, для которых ограничения выполняются, но существуют ли конференсные графы, неизвестно.

Собственные значения конференсных графов не обязательно целые числа, что необычно для сильно регулярных графов. Если граф связан, одно собственное значение равно k и два других,

{\frac {-1\pm {\sqrt {v}}}{2}},

каждое из которых повторяется (v − 1)/2 раз.

Литература

Brouwer, A. E., Cohen, A. M., Neumaier, A. Distance Regular Graphs. — Berlin, New York: Springer-Verlag, 1989. — ISBN 3-540-50619-5, 0-387-50619-5.

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

Изоморфи́зм — соотношение между математическими объектами, выражающее общность их строения; используется в разных разделах математики и в каждом из них определяется в зависимости от структурных свойств изучаемых объектов. Обычно изоморфизм определяется для множеств, наделённых некоторой структурой, например, для групп, колец, линейных пространств; в этом случае он определяется как обратимое отображение (биекция) между двумя множествами со структурой, сохраняющее эту структуру, то есть показывающее, что объекты «одинаково устроены» в смысле этой структуры. Если между объектами существует изоморфизм, то они называются изоморфными. Изоморфизм всегда задаёт отношение эквивалентности на классе таких структур.

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

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

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

Ко́мпле́ксный ана́лиз, тео́рия фу́нкций ко́мпле́ксного переме́нного — раздел математического анализа, в котором рассматриваются и изучаются функции комплексного аргумента.

<span class="mw-page-title-main">Графен</span> двумерная модификация углерода

Графе́н — двумерная аллотропная модификация углерода, образованная слоем атомов углерода толщиной в один атом. Атомы углерода находятся в sp²-гибридизации и соединены посредством σ- и π-связей в гексагональную двумерную кристаллическую решётку. Его можно представить как одну плоскость слоистого графита, отделённую от объёмного кристалла. По оценкам, графен обладает большой механической жёсткостью и рекордно большой теплопроводностью. Высокая подвижность носителей заряда, которая оказывается максимальной среди всех известных материалов, делает его перспективным материалом для использования в самых различных приложениях, в частности, как будущую основу наноэлектроники и возможную замену кремния в интегральных микросхемах.

<span class="mw-page-title-main">Алгоритм Флойда — Уоршелла</span> алгоритм поиска кратчайшего расстояния между парами вершин во взвешенном графе

Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. При этом алгоритм впервые разработал и опубликовал Бернард Рой в 1959 году.

Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна. Полный граф с $\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]}$ .

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

Экспандер — сильносвязный разреженный граф, при этом связность может определяться по вершинам, дугам или спектру.

Полный двудольный граф (биклика) — специальный вид двудольного графа, у которого любая вершина первой доли соединена со всеми вершинами второй доли вершин.

Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в $\text{[math]}$ различных цветов для заданного значения $\text{[math]}$ или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.

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

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

Дистанционно-регулярный граф — такой регулярный граф, у которого для двух любых вершин $\text{[math]}$ и $\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> регулярный граф с v вершинами и степенью k, у которого число общих соседей зависит только от смежности пары вершин

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

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

Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.

<span class="mw-page-title-main">Локально линейный граф</span>

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

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