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