Gráfművelet

A Wikipédiából, a szabad enciklopédiából

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 unáris gráfműveletek[szerkeszté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űveletek[szerkesztés]

Bináris gráfműveletek[szerkesztés]

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

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

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

  • A gráfszorzás 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.

Hivatkozások[szerkesztés]

  1. Frank Harary. Graph Theory. Reading, MA: Addison-Wesley, 1994.