Перетин графів

Шаблон:Не плутати Пере́тин графів — операція над графами, в результаті якої виходить граф, множини вершин і ребер якого є перетинами множин вершин і ребер вихідних графів. Іншими словами, в результуючий граф входять тільки ті ребра і ті вершини, які присутні у всіх вихідних графах .

Операцію перетину графів, як і аналогічну операцію для множин, прийнято позначати символом $\cap$:

$G=G_1\cap G_2.$

Таким чином, якщо

$G_1=\{V_1,E_1\},G_2=\{V_2,E_2\},$

то

$G=\{V_1\cap V_2,E_1\cap E_2\},$

де $V$ — множина вершин, $E$ — множина ребер графу.

Див. також

• Словник термінів теорії графів
• Теорія графів
• Об'єднання графів

Посилання

• Свами М., Тхуласираман К. Графы, сети, алгоритмы: Пер. с англ. — М.: Мир, 1984. — 455 с.
• Харари Ф. Теория графов. — М.: Мир, 1973.
• Дискретная математика: алгоритмы, визуализация графов, апплеты