Průsečík grafu

Průnik grafu je operace s grafy , jejímž výsledkem je graf, jehož sady vrcholů a hran jsou průsečíky sad vrcholů a hran původních grafů. Jinými slovy, výsledný graf zahrnuje pouze ty hrany a ty vrcholy, které jsou přítomny ve všech původních grafech [1] .

Operace průniku grafů, stejně jako podobná operace pro množiny, se obvykle označuje symbolem : $\víčko$

\G=G_1 \cap G_2.

Pokud tedy

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

pak

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

kde je množina vrcholů, je množina hran grafu. $\PROTI$ $\E$

Viz také

Slovník pojmů teorie grafů
teorie grafů
Unie grafů

Poznámky

↑ Svámí M. (1984), s. 21.

Odkazy

Swami M., Thulasiraman K. Grafy, sítě, algoritmy: Per. z angličtiny. — M.: Mir, 1984. — 455 s.
Harari F. Teorie grafů. — M.: Mir , 1973.
Diskrétní matematika: Algoritmy, vizualizace grafů, applety