Yedek ürün - Replacement product
İçinde grafik teorisi, yedek ürün iki grafiğin bir grafik ürünü azaltmak için kullanılabilir derece bir grafiğin bağlantı.[1]
Varsayalım G bir d-normal grafik ve H bir e- köşe grubu {0,…, ile düzenli grafikd - 1}. İzin Vermek R ikame ürününü belirtmek G ve H. Köşe kümesi R ... Kartezyen ürün V(G) × V(H). Her köşe için sen içinde V(G) ve her kenar için (ben, j) içinde E(H), köşe (sen, ben) bitişiktir (sen, j) içinde R. Ayrıca her kenar için (sen, v) içinde E(G), Eğer v ... benkomşusu sen ve sen ... jkomşusu vtepe noktası (sen, ben) bitişiktir (v, j) içindeR.
Eğer H bir e-düzenli grafik, sonra R bir (e + 1) -düzenli grafik.
Referanslar
- ^ Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (7 Ağustos 2006). "Genişletici grafikler ve uygulamaları". Amerikan Matematik Derneği Bülteni. 43 (4): 439–562. doi:10.1090 / S0273-0979-06-01126-8.
Dış bağlantılar
- Trevisan, Luca (7 Mart 2011). "CS359G Ders 17: Zig-Zag Ürünü". Alındı 16 Aralık 2014.
 | Bu kombinatorik ile ilgili makale bir Taslak. Wikipedia'ya şu şekilde yardım edebilirsiniz: genişletmek. |