Gráfszorzás

A Wikipédiából, a szabad enciklopédiából

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

Definíciók[szerkesztés | forrásszöveg szerkesztése]

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)