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]

Legyenek és gráfok. Jelölje , ha valamely gráfban az csúcsok szomszédosak. Ekkor

  • A szorzatgráf csúcshalmaza az operandusok csúcshalmazainak Descartes-szorzata:
  • A szorzatgráf élhalmazát illetően több eltérő definíció is használatos:
    1. (Tenzor szorzat)
    2. (Lexikografikus szorzat)
    3. (Normál szorzat)
    4. (Diszjunktív szorzat)