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 É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ó)
Bináris gráfműveletek A bináris (vagy binér) gráfműveletek gráfpárokhoz rendelnek hozzá gráfokat. Legyenek gráfok. gráfok uniója: . Ha V1 és V2 diszjunktak, diszjunkt unióról beszélünk, jelölése ; a diszjunkt gráfunió kommutatív és asszociatív.Frank Harary. Graph Theory. Reading, MA: Addison-Wesley, 1994. gráfok metszete (intersection): ; 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. A gráfszorzások esetében a szorzatgráf csúcshalmaza az operandusok csúcshalmazának Descartes-szorzata: . 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ó
Hivatkozások
Kategória:Gráfelmélet