Kaavion leikkauspiste

Graafin leikkaus on kaavioita koskeva operaatio, jonka tuloksena saadaan graafi, jonka kärki- ja reunajoukot ovat alkuperäisten graafien kärki- ja reunajoukkojen leikkauspisteitä. Toisin sanoen tuloksena oleva graafi sisältää vain ne reunat ja kärjet, jotka ovat läsnä kaikissa alkuperäisissä graafisissa [1] .

Graafeiden leikkausoperaatio, samoin kuin vastaava operaatio joukkoille, on yleensä merkitty symbolilla :

Eli jos

sitten

missä on pisteiden joukko, on graafin reunojen joukko.

Katso myös

• Graafiteorian termien sanasto
• graafiteoria
• Graafisten liitto

Muistiinpanot

1. ↑ Swami M. (1984), s. 21.

Linkit

• Swami M., Thulasiraman K. Graafit, verkot, algoritmit: Per. englannista. - M.: Mir, 1984. - 455 s.
• Harari F. Graafiteoria. - M.: Mir , 1973.
• Diskreetti matematiikka: algoritmit, grafiikan visualisointi, sovelmat