Пересечение графов

Пересечение графов — операция над графами, в результате которой получается граф, множества вершин и рёбер которого являются пересечениями множеств вершин и рёбер исходных графов. Иными словами, в результирующий граф входят только те рёбра и те вершины, которые присутствуют во всех исходных графах.

Операцию пересечения графов, как и аналогичную операцию для множеств, принято обозначать символом [math]\displaystyle{ \cap }[/math]:

[math]\displaystyle{ \ G = G_1 \cap G_2. }[/math]

Таким образом, если

[math]\displaystyle{ \ G_1 = \left \{ V_1, E_1 \right \}, G_2 = \left \{ V_2, E_2 \right \}, }[/math]

то

[math]\displaystyle{ \ G = \left \{ V_1 \cap V_2, E_1 \cap E_2\right \}, }[/math]

где [math]\displaystyle{ \ V }[/math] — множество вершин, [math]\displaystyle{ \ E }[/math] — множество рёбер графа.

См. также

• Словарь терминов теории графов
• Теория графов
• Объединение графов

Ссылки

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