Корневое произведение

В теории графов корневое произведение графа G и корневого графа H определяется следующим образом: возьмём |V(G)| копий графа H и для каждой вершины $v_{i}$ графа G, отождествляем $v_{i}$ с корневой вершиной i-ой копии H.

Более формально. Предположим, что V(G) = {g₁, ..., g_n}, V(H) = {h₁, ..., h_m} и что корнем графа H является $h_{1}$ . Определим произведение

G\circ H:=(V,E)

где

V=\left\{(g_{i},h_{j}):1\leq i\leq n,1\leq j\leq m\right\}

E=\left\{((g_{i},h_{1}),(g_{k},h_{1})):(g_{i},g_{k})\in E(G)\right\}\cup \bigcup _{i=1}^{n}\left\{((g_{i},h_{j}),(g_{i},h_{k})):(h_{j},h_{k})\in E(H)\right\}

Если граф G является также корневым с корнем g₁, можно рассматривать произведение само как корневой граф с корнем (g₁, h₁). Корневое произведение является подграфом прямого произведения тех же самых двух графов.

Приложения

Корневое произведение особенно актуально для деревьев, поскольку корневое произведение двух деревьев снова будет деревом. Например, Кох и др. (1980) использовали корневые произведения для поиска грациозной нумерации для широкого семейства деревьев.

Если H — полный граф с двумя вершинами K₂, то для любого графа G корневое произведение графов G и H имеет число доминирования, равное ровно половине числа его вершин. Любой связный граф, в котором число доминирования равно половине вершин, получается таким образом, за исключением цикла с четырьмя вершинами. Эти графы можно использовать для генерации примеров, в которых для прямого произведения графов достигается граница из гипотезы Визинга, недоказанного неравенства между числом доминирования графов в различных произведениях графов^[1].

Примечания

↑ Fink, Jacobson, Kinch, Roberts, 1985.

Литература

C. D. Godsil, B. D. McKay. A new graph product and its spectrum // Bull. Austral. Math. Soc.. — 1978. — Т. 18, вып. 1. — С. 21–28. — doi:10.1017/S0004972700007760.
J. F. Fink, M. S. Jacobson, L. F. Kinch, J. Roberts. On graphs having domination number half their order // Period. Math. Hungar.. — 1985. — Т. 16, вып. 4. — С. 287–293. — doi:10.1007/BF01848079.
K. M. Koh, D. G. Rogers, T. Tan. Products of graceful trees // Discrete Mathematics. — 1980. — Т. 31, вып. 3. — С. 279–292. — doi:10.1016/0012-365X(80)90139-9.

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

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

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

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

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

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

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

Дерево Фенвика — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году. Дерево Фенвика напоминает дерево отрезков, однако проще в реализации.

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

ACE — набор программных средств, реализующих шифрование в режиме схемы шифрования с открытым ключом, а также в режиме цифровой подписи. Соответствующие названия этих режимов — «ACE Encrypt» и «ACE Sign». Схемы являются вариантами реализации схем Крамера-Шоупа. Внесённые изменения нацелены на достижение наилучшего баланса между производительностью и безопасностью всей системы шифрования.

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

Операции над графами образуют новые графы из старых. Операции можно разделить на следующие основные категории.

<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]}$ .

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

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

Гипотеза Визинга — предположение о связи доминирующего множества и прямого произведения графов, не подтверждённое по состоянию на 2017 год, при этом гипотеза доказана для ряда частных случаев.

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

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

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

GMR — криптографический алгоритм, используемый для создания цифровой подписи. Назван по первым буквам создателей — Рональда Ривеста, Сильвио Микали и Шафи Гольдвассер.

Спектральный радиус — понятие в математике, определяемое для квадратной матрицы как максимум абсолютных значений её собственных значений. В более общем случае, спектральный радиус линейного ограниченного оператора — это точная верхняя граница абсолютных значений элементов его спектра. Спектральный радиус часто обозначается ρ(·).

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