O'zgartirish mahsuloti - Replacement product
Yilda grafik nazariyasi, almashtirish mahsuloti ikkita grafadan a grafik mahsulot kamaytirish uchun ishlatilishi mumkin daraja grafigini saqlab turganda ulanish.[1]
Aytaylik G a d-muntazam grafik va H bu e- tepalik to'plami {0,…, bilan muntazam grafikd - 1}. Ruxsat bering R o'rnini bosuvchi mahsulotni belgilang G va H. Vertex to'plami R bo'ladi Dekart mahsuloti V(G) × V(H). Har bir tepalik uchun siz yilda V(G) va har bir chekka uchun (men, j) ichida E(H), tepalik (siz, men) ga qo'shni (siz, j) ichida R. Bundan tashqari, har bir chekka uchun (siz, v) ichida E(G), agar v bo'ladi menning qo'shnisi siz va siz bo'ladi jning qo'shnisi v, tepalik (siz, men) ga qo'shni (v, j) ichidaR.
Agar H bu e- muntazam grafik, keyin R bu (e + 1) - muntazam grafik.
Adabiyotlar
- ^ Hoory, Shlomo; Linial, Natan; Wigderson, Avi (2006 yil 7-avgust). "Kengaytiruvchi grafikalar va ularning qo'llanilishi". Amerika Matematik Jamiyati Axborotnomasi. 43 (4): 439–562. doi:10.1090 / S0273-0979-06-01126-8.
Tashqi havolalar
- Trevisan, Luka (2011 yil 7 mart). "CS359G 17-maruza: Zig-Zag mahsuloti". Olingan 16 dekabr 2014.
 | Bu kombinatorika bilan bog'liq maqola a naycha. Siz Vikipediyaga yordam berishingiz mumkin uni kengaytirish. |