Сильное произведение графов

Сильное произведение $G\boxtimes H$ графов G и H — это граф, такой, что^[1]:

множество вершин $G\boxtimes H$ является прямым произведением $V(G)\times V(H)$
различные вершины (u,u' ) и (v,v' ) связаны ребром в $G\boxtimes H$ $G\boxtimes H$ тогда и только тогда, когда
- u = v и u' смежна с v' , или
- u' = v' и u смежна с v, или
- u смежна с v и u' смежна с v' .

Сильное произведение является объединением прямого произведения и тензорного произведения.

Сильное произведение называется также нормальным произведением или AND произведением. Произведение впервые ввёл Сабидусси в 1960 году^[2]. Сильное произведение контрастирует со слабым произведением, но эти два произведения отличаются, только если применяются к бесконечным графам.

Например, граф ходов короля, граф, в котором вершинами являются клетки шахматной доски, а рёбра представляют возможные ходы короля, является сильным произведением двух путей^[3].

Следует проявлять осторожность, когда термин встречается в литературе, поскольку сильное произведение используется и для обозначения тензорного произведения^[4].

См. также

Примечания

↑ Imrich, Klavžar, Rall, 2008.
↑ Sabidussi, 1960, с. 446–457.
↑ Berend, Korach, Zucker, 2005, с. 335–341.
↑ Lovász, 1979, с. 2.

Литература

Wilfried Imrich, Sandi Klavžar, Douglas F. Rall. Graphs and their Cartesian Product. — A. K. Peters, 2008. — ISBN 1-56881-429-1.
Sabidussi, G. Graph multiplication // Math. Z.. — 1960. — Т. 72. — С. 446–457. — doi:10.1007/BF01162967.
Daniel Berend, Ephraim Korach, Shira Zucker. Two-anticoloring of planar and related graphs // 2005 International Conference on Analysis of Algorithms. — Nancy: Association for Discrete Mathematics & Theoretical Computer Science, 2005. — С. 335–341. — (Discrete Mathematics & Theoretical Computer Science Proceedings).
László Lovász. On the Shannon Capacity of a Graph // IEEE Transactions on Information Theory. — 1979. — Т. IT-25, вып. 1. — doi:10.1109/TIT.1979.1055985.

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

<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.

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

В теории графов медианным графом называется неориентированный граф, в котором любые три вершины a, b, и c имеют единственную медиану — вершину m(a,b,c), которая принадлежит кратчайшим путям между каждой парой вершин a, b и c.

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

Произведение графов — это бинарная операция на графах. Конкретнее, это операция, которая двум графам G₁ и G₂ сопоставляет граф H со следующими свойствами:

Множество вершин графа H — это прямое произведение V(G₁) × V(G₂), где V(G₁) и V(G₂) являются множествами вершин G₁ и G₂ соответственно.
Две вершины (u₁, u₂) и (v₁, v₂) графа H соединены ребром тогда и только тогда, когда вершины u₁, u₂, v₁, v₂ удовлетворяют определённым условиям, соответствующим типу произведения (смотрите ниже).

Число пересечений графа — наименьшее число элементов в представлении данного графа как графа пересечений конечных множеств, или, эквивалентно, наименьшее число клик, необходимых для покрытия всех рёбер графа.

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

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

Графы Хэмминга — специальный класс графов, названных именем Ричарда Хэмминга и используемых в некоторых областях математики и информатики.

Число Ловаса графа — вещественное число, которое является верхней границей ёмкости Шеннона этого графа. Число Ловаса известно также под именем тета-функция Ловаса и обычно обозначается как $\text{[math]}$ . Это число впервые ввёл Ласло Ловас в статье 1979 года «On the Shannon Capacity of a Graph».

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

Неориентированный граф G называется строго хордальным, если он является хордальным и любой цикл чётной длины в G имеет нечётную хорду, то есть ребро, которое соединяет две вершины цикла на нечётном расстоянии (>1) друг от друга.

Гипотеза Хедетниеми — математическая гипотеза, в общем случае опровергнутая, предположение о связи между раскраской графов и тензорным произведением графов:

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

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

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

Косое разбиение графа — разбиение его вершин на два подмножества в виде несвязного порождённого подграфа и дополнения; играет важную роль в теории совершенных графов.

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

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

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

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

<span class="mw-page-title-main">Теорема Петерсена</span> теорема теории графов

Теорема Петерсена — одна из самых ранних теорем теории графов, названная в честь Юлиуса Петерсена. Определение теоремы может быть сформулировано следующим образом:

Теорема Петерсена. Любой кубический двусвязный граф содержит в себе совершенное паросочетание.

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