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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

то

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

Примечания

[править | править код]
  1. Свами М. (1984), с. 21.