Graf skärningspunkt

Grafskärning är en operation på grafer som resulterar i en graf vars vertex- och kantuppsättningar är skärningspunkterna för de ursprungliga grafernas spets- och kantuppsättningar. Med andra ord inkluderar den resulterande grafen endast de kanter och de hörn som finns i alla ursprungliga grafer [1] .

Operationen för skärningspunkten av grafer, såväl som en liknande operation för uppsättningar, betecknas vanligtvis med symbolen : $\keps$

\G=G_1 \cap 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 \cap V_2, E_1 \cap 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
Förening av grafer

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