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űveletekSzerkesztés

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

Elemi unáris gráfműveletekSzerkesztés

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űveletekSzerkesztés

Bináris gráfműveletekSzerkesztés

A bináris (vagy binér) gráfműveletek gráfpárokhoz rendelnek hozzá gráfokat. Legyenek   gráfok.

  • gráfok uniója: G1G2 = (V1V2, E1E2). Ha V1 és V2 diszjunktak, diszjunkt unióról beszélünk, jelölése G1G2;[1] a diszjunkt gráfunió kommutatív és asszociatív.[2]
  • gráfok metszete (intersection): G1G2 = (V1V2, E1E2);[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:  . 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ásokSzerkesztés

  1. a b Graph Theory, Graduate Texts in Mathematics. Springer, 29. o. (2008. január 15.). ISBN 978-1-84628-969-9 
  2. a b Frank Harary. Graph Theory. Reading, MA: Addison-Wesley, 1994.