Оглавление
Декартово произведение графов
-
Определение декартова произведения графов
- Декартово произведение G □ H графов G и H — это граф, где множество вершин G □ H является декартовым произведением V(G) × V(H).
- Вершины u и v могут быть соединены, если u = u’ и v примыкает к v’ в H или v = v’ и u примыкает к u’ в G.
-
Свойства декартова произведения
- Декартово произведение ассоциативно и коммутативно как операция над классами изоморфизма графов.
- Декартово произведение не коммутативно как операция над помеченными графами.
- Декартово произведение может быть разложено на множители, если граф связный.
- Декартово произведение является вершинно-транзитивным, если каждый из его сомножителей равен.
- Декартово произведение является двудольным, если каждый из его сомножителей равен.
-
Алгебраическая теория графов
- Матрица смежности декартова произведения задается формулой, включающей произведение матриц Кронекера.
- Декартово произведение соответствует тензорному произведению категорий.
-
История
- Декартовы произведения графов были определены в 1912 году Уайтхедом и Расселом.
- Позже они неоднократно открывались заново, в частности, Гертом Сабидусси в 1960 году.