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

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

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

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

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

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

то

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

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