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 műveletnek tekintjük valamely él vagy csúcs törlését, csúcsok összevonását és szétválasztását.

Élgrá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.
Gráf transzponáltja avagy megfordítása
Gráfújraírás
Mediális gráf
Mycielski-konstrukció;
delta-csillag átalakítás (Δ-Y-átalakítás, Δ-Y-transzformáció)

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.

gráfok uniója: G₁ ∪ G₂ = (V₁ ∪ V₂, E₁ ∪ E₂). Ha V₁ és V₂ diszjunktak, diszjunkt unióról beszélünk, jelölése G₁ ⊕ G₂;^[1] a diszjunkt gráfunió kommutatív és asszociatív.^[2]
gráfok metszete (intersection): G₁ ∩ G₂ = (V₁ ∩ V₂, E₁ ∩ E₂);^[1]
gráfok összekapcsolása (join): az első gráf összes csúcsát a második gráf összes csúcsának összekötésével kapott gráf. Címkézetlen gráfok esetében kommutatív művelet.^[2]
A gráfszorzások esetében a szorzatgráf csúcshalmaza az operandusok csúcshalmazának Descartes-szorzata: $V=V_{1}\times V_{2}$ $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.
soros-párhuzamos gráf képzése
Hajós-konstrukció

↑ ^a ^b Graph Theory, Graduate Texts in Mathematics. Springer, 29. o. (2008. november 27.). ISBN 978-1-84628-969-9
↑ ^a ^b Frank Harary. Graph Theory. Reading, MA: Addison-Wesley, 1994.