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

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

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

$\ G=G_{1}\cap G_{2}.$

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

$\ G_{1}=\left\{V_{1},E_{1}\right\},G_{2}=\left\{V_{2},E_{2}\right\},$

то

$\ G=\left\{V_{1}\cap V_{2},E_{1}\cap E_{2}\right\},$

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

См. также

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

Ссылки

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