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 | forrásszöveg szerkesztése]

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

Elemi unáris gráfműveletek[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

Bináris gráfműveletek[szerkesztés | forrásszöveg szerkesztése]

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.

  • A diszjunkt unió akkor értelmezett, ha V_1, V_2 diszjunktak. Ekkor
G_1 \cup G_2 := (V_1 \cup V_2, E_1 \cup E_2)

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: V = V_1 \times V_2. Az élhalmaz a szorzat típusától függ.

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

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