В теории графов , то сильный продукт G ⊠ Н графов G и Н представляет собой график , таким образом, что [1]
- множество вершин графа G ⊠ H - это декартово произведение V ( G ) × V ( H ); а также
- различные вершины ( u, u ' ) и ( v, v' ) смежны в G ⊠ H тогда и только тогда, когда:
- u = v и u ' смежно с v' , или
- u ' = v' и u смежно с v , или
- u смежна с v, а u ' смежна с v' .
Это объединение декартова произведения и тензорного произведения .
Сильный продукт также называется нормальным продуктом или и продукт . [ необходимая цитата ] Впервые он был введен Сабидусси в 1960 году. [2] В этом контексте сильный продукт противопоставляется слабому , но они отличаются только в применении к бесконечному множеству факторов.
Например, граф короля , граф, вершинами которого являются квадраты шахматной доски, а ребра представляют возможные ходы шахматного короля, является сильным произведением двух графов путей . [3]
Следует проявлять осторожность, когда в литературе встречается термин сильное произведение , поскольку он также использовался для обозначения тензорного произведения графов . [4]
См. Также [ править ]
Ссылки [ править ]
- ^ Имрих, Вильфрид; Клавжар, Санди; Ралл, Дуглас Ф. (2008), Графы и их декартово произведение , AK Peters, ISBN 978-1-56881-429-2.
- ^ Сабидусси, G. (1960). «Умножение графа». Математика. Z . 72 : 446–457. DOI : 10.1007 / BF01162967 . hdl : 10338.dmlcz / 102459 . Руководство по ремонту 0209177 .
- ^ Беренд, Дэниел; Корах, Ефрем; Цукер, Шира (2005 г.), «Два антикрашивания плоских и связанных графов» (PDF) , Международная конференция 2005 г. по анализу алгоритмов , дискретной математике и трудностям теоретической информатики, Нэнси: Ассоциация дискретной математики и теоретической информатики, стр. 335–341, MR 2193130 .
- ^ См стр 2 из Lovász, Ласло (1979), "О пропускной способности Шеннона в графике", IEEE Transactions по теории информации , IT-25 (1): 1-7, DOI : 10,1109 / TIT.1979.1055985 CS1 maint: обескураженный параметр ( ссылка ).
