Gráfszorzás

A gráfszorzás egy kétoperandusú gráfművelet. Több definíciója létezik.

Definíciók

Legyenek $G_1=(V_1, E_1)$ és $G_2=(V_2, E_2)$ gráfok. Jelölje $u \sim v$, ha valamely gráfban az $u, v$ csúcsok szomszédosak. Ekkor

• A szorzatgráf csúcshalmaza az operandusok csúcshalmazainak Descartes szorzata: $V = V_1 \times V_2$
• A szorzatgráf élhalmazát illetően több eltérő definíció is használatos:
  1. $(u_1, u_2) \sim (v_1, v_2) \Leftrightarrow u_1=v_1 \and u_2 \sim v_2 \or u_2=v_2 \and u_1 \sim v_1$
  2. $(u_1, u_2) \sim (v_1, v_2) \Leftrightarrow u_2 \sim v_2 \and u_1 \sim v_1$ (Tenzor szorzat)
  3. $(u_1, u_2) \sim (v_1, v_2) \Leftrightarrow u_1 \sim v_1 \or u_1=v_1 \and u_2 \sim v_2$ (Lexikografikus szorzat)
  4. $(u_1, u_2) \sim (v_1, v_2) \Leftrightarrow u_1=v_1 \and u_2 \sim v_2 \or u_2=v_2 \and u_1 \sim v_1 \or u_1 \sim v_1 \and u_2 \sim v_2$ (Normál szorzat)
  5. $(u_1, u_2) \sim (v_1, v_2) \Leftrightarrow u_1 \sim v_1 \or u_2 \sim v_2$ (Diszjunktív szorzat)