Декартів добуток графів
бінарна операція на графах / З Вікіпедії, безкоштовно encyclopedia
Шановний Wikiwand AI, Давайте зробимо це простіше, відповівши на ключові запитання:
Чи можете ви надати найпопулярніші факти та статистику про Декартів добуток графів?
Підсумуйте цю статтю для 10-річної дитини
Декартів добуток або прямий добуток[1] G H графів G і H — це граф, такий, що
- множина вершин графу G H — це декартів добуток V(G) × V(H)
- будь-які дві вершини (u, u') і (v, v') суміжні в G H тоді і тільки тоді, коли
- або u=v і u' суміжна v' в H
- або u' =v' і u суміжна v в G.
Декартів добуток можна розпізнати ефективно за лінійний час[2]. Операція є комутативною як операція на класах ізоморфізмів графів, і строгіше, графи G H і H G природно ізоморфні, але операція не є комутативною як операція на розмічених графах. Операція є також асоціативною, оскільки графи (F G) H і F (G H) природно ізоморфні.
Позначення G × H часом використовується і для декартового добутку графів, але частіше воно використовується для іншої конструкції, відомої як тензорний добуток графів. Символ квадратика частіше використовується і є недвозначним для декартового добутку графів. Він показує візуально чотири ребра, що виходять внаслідок декартового добутку двох ребер.[3]