📊 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} \)
