Gráfművelet

A gráfműveletek olyan műveletek, melyek gráfokhoz rendelnek gráfokat. Kategorizálhatóak például az operandusok száma szerint.

Unáris gráfműveletek

Az unáris gráfműveletek, vagyis gráftranszformációk egyoperandusú műveletek.

Elemi unáris gráfműveletek

Elemi műveletnek tekintjük valamely él vagy csúcs törlését, csúcsok összevonását és szétválasztását.

Összetett unáris gráfműveletek

• Vonalgráf
• Duális gráf
• Komplementer gráf
• Gráf minora
• Gráfhatvány: Valamely G=(V,E) gráf k-adik hatványa az a (V,F) gráf, amely tartalmazza élként azokat a csúcspárokat, amelyek távolsága a G gráfban legfeljebb k. Valamely gráf második hatványát nevezik a gráf négyzetének is.

Bináris gráfműveletek

A bináris (vagy binér) gráfműveletek gráfpárokhoz rendelnek hozzá gráfokat. Legyenek $G_1=(V_1, E_1), G_2=(V_2, E_2)$ gráfok.

• A diszjunkt unió akkor értelmezett, ha $V_1, V_2$ diszjunktak. Ekkor

$G_1 \cup G_2 := (V_1 \cup V_2, E_1 \cup E_2)$

A diszjunkt gráfunió kommutatív és asszociatív.

• A gráfszorzás esetében a szorzatgráf csúcshalmaza az operandusok csúcshalmazának Descartes szorzata: $V = V_1 \times V_2$. Az élhalmaz a szorzat típusától függ.
  • A lexikografikus gráfszorzás nem kommutatív és nem asszociatív.
  • A tenzor gráfszorzás kommutatív művelet.