? Kartezyen Çarpım Grafiği Nedir?
Kartezyen çarpım grafiği, iki veya daha fazla grafin Kartezyen çarpımı ile oluşturulan yeni bir graftır. Bu kavram, matematikteki Kartezyen çarpım işleminin graflara uygulanmış halidir.
? Tanım ve Temel Kavramlar
İki graf \( G = (V_1, E_1) \) ve \( H = (V_2, E_2) \) olsun. Bu grafların Kartezyen çarpımı olan \( G \square H \) grafı şu şekilde tanımlanır:
- ? Köşe kümesi: \( V(G \square H) = V(G) \times V(H) \)
- ? Kenar kümesi: İki köşe \((u, v)\) ve \((u', v')\) arasında kenar vardır ancak ve ancak:
- ✅ \( u = u' \) ve \( v \) ile \( v' \), \( H \) grafında komşu ise, VEYA
- ✅ \( v = v' \) ve \( u \) ile \( u' \), \( G \) grafında komşu ise
? Örnek: İki Yol Grafının Çarpımı
\( P_2 \) ve \( P_3 \) yol graflarını ele alalım:
- ➡️ \( P_2 \): Köşeler {1, 2}, kenar: 1-2
- ➡️ \( P_3 \): Köşeler {a, b, c}, kenarlar: a-b, b-c
\( P_2 \square P_3 \) grafının köşeleri:
- ? (1,a), (1,b), (1,c)
- ? (2,a), (2,b), (2,c)
Kenar bağlantıları:
- ? \( P_2 \) yönünde: (1,a)-(2,a), (1,b)-(2,b), (1,c)-(2,c)
- ? \( P_3 \) yönünde: (1,a)-(1,b), (1,b)-(1,c), (2,a)-(2,b), (2,b)-(2,c)
✨ Özellikleri
- ? Boyut: \( |V(G \square H)| = |V(G)| \times |V(H)| \)
- ? Kenar sayısı: \( |E(G \square H)| = |V(G)| \cdot |E(H)| + |V(H)| \cdot |E(G)| \)
- ? Çap: \( \text{diam}(G \square H) = \text{diam}(G) + \text{diam}(H) \)
- ? Bağlantılılık: \( G \square H \) ancak ve ancak hem \( G \) hem de \( H \) bağlantılı ise bağlantılıdır
? Uygulama Alanları
- ?️ Ağ tasarımı: Paralel bilgisayar ağlarının tasarımında kullanılır
- ? Oyun teorisi: Çok boyutlu oyun tahtalarının modellenmesi
- ? Kimyasal yapılar: Moleküler grafların analizinde
- ? Veri yapıları: Çok boyutlu dizilerin grafik temsili
? Önemli Notlar
- Kartezyen çarpım değişmeli ve birleşmeli bir işlemdir
- Kartezyen çarpım grafları, düzenli (regular) grafların oluşturulmasında kullanılır
- Hiperküp grafları, Kartezyen çarpımın özel bir halidir: \( Q_n = K_2 \square Q_{n-1} \)
