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

Пере́тин графів — операція над графами, в результаті якої виходить граф, множини вершин і ребер якого є перетинами множин вершин і ребер вихідних графів. Іншими словами, в результуючий граф входять тільки ті ребра і ті вершини, які присутні у всіх вихідних графах [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}$ — множина ребер графу.