Сильний добуток графів
Перейти до навігації
Перейти до пошуку
Сильний добуток графів G і H - це граф, такий, щоШаблон:Sfn:
- множина вершин є прямим добутком
- різні вершини (u, u ') і (v, v') пов'язані ребром у тоді і тільки тоді, коли
- u = v і u' суміжна з v', або
- u' = v' і u суміжна з v, або
- u суміжна з v і u' суміжна з v'.
Сильний добуток є об'єднанням прямого добутку і тензорного добутку.
Сильний добуток називається також нормальним добутком або AND добутком. Добуток уперше ввів Сабідуссі 1960 рокуШаблон:Sfn. Сильний добуток контрастує зі слабким добутком, але ці два добутки відрізняються, тільки якщо застосовуються до нескінченних графів.
Наприклад, граф ходів короля, граф, у якому вершинами є клітинки шахової дошки, а ребра представляють можливі ходи короля, є сильним добутком двох шляхівШаблон:Sfn.
Слід бути обережним, коли термін зустрічається в літературі, оскільки назву сильний добуток використовують і для позначення тензорного добуткуШаблон:Sfn.