Förening av grafer

Grafunion är en operation på grafer som resulterar i en graf vars vertex- och kantuppsättningar är sammansättningar av spets- och kantuppsättningarna för de ursprungliga graferna. Med andra ord inkluderar den resulterande grafen alla kanter och hörn som finns i de ursprungliga graferna [1] .

Operationen med att kombinera grafer, såväl som en liknande operation för uppsättningar, betecknas vanligtvis med symbolen : $\kopp$

\ G = G_1 \kopp G_2.

Alltså om

\ G_1 = \left \{ V_1, E_1 \right \}, G_2 = \left \{ V_2, E_2 \right \},

sedan

\ G = \left \{ V_1 \cup V_2, E_1 \cup E_2\right \},

där är uppsättningen av hörn, är uppsättningen av kanter på grafen. $\V$ $\E$

Se även

Ordlista över grafteoretiska termer
grafteori
Graf skärningspunkt

Anteckningar

↑ Swami M. (1984), sid. 21.

Länkar

Swami M., Thulasiraman K. Grafer, nätverk, algoritmer: Per. från engelska. — M.: Mir, 1984. — 455 sid.
Harari F. Grafteori. — M.: Mir , 1973.
Diskret matematik: Algoritmer, grafvisualisering, applets