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[szerkesztés]

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. április 4.). ISBN 978-1-84628-969-9
↑ ^a ^b Frank Harary. Graph Theory. Reading, MA: Addison-Wesley, 1994.