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.

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

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