Náhradní produkt - Replacement product
v teorie grafů, náhradní produkt dvou grafů je a grafový produkt které lze použít ke snížení stupeň grafu při zachování jeho připojení.[1]
Předpokládat G je d-běžný graf a H je E-pravidelný graf se sadou vrcholů {0,…,d - 1} Nechat R označují náhradní produkt G a H. Sada vrcholů R je kartézský součin PROTI(G) × PROTI(H). Pro každý vrchol u v PROTI(G) a pro každou hranu (i, j) v E(H), vrchol (u, i) sousedí s (u, j) v R. Dále pro každou hranu (u, proti) v E(G), pokud proti je itý soused u a u je jtý soused proti, vrchol (u, i) sousedí s (proti, j) vR.
Li H je E-pravidelný graf, pak R je (E + 1) -pravidelný graf.
Reference
- ^ Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (7. srpna 2006). „Rozšiřovací grafy a jejich aplikace“. Bulletin of the American Mathematical Society. 43 (4): 439–562. doi:10.1090 / S0273-0979-06-01126-8.
externí odkazy
- Trevisan, Luca (7. března 2011). „CS359G Lecture 17: The Zig-Zag Product“. Citováno 16. prosince 2014.
 | Tento kombinatorika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |