Упаковка графов

Материал из WikiGrapp
Перейти к:навигация, поиск

Упаковка графов (Packing of graphs) — Пусть G_{1}, \ldots, G_{k}графы порядка, не превышающего \,n. Говорят, что существует упаковка этих графов в \,K_{n}, если найдутся инъекции \alpha_{i}: \, V_{i} \rightarrow V(K_{n})\, i=1, \ldots, k, такие, что

\alpha_{i}^{\ast}(E(G_{i})) \cap \alpha_{j}^{\ast}(E(G_{j})) \neq \emptyset для i \neq j,

где отображение \alpha_{i}^{\ast}: \, E(G_{i}) \rightarrow E(K_{n}) порождается отображением \,\alpha_{i}. Упаковка \,k копий графа \,G называется \,k-размещением \,G (\,k-placement). Размещение двух копий \,G, т.е. 2-размещение, называется вложением \,G (embedding) (в его дополнение \bar{G}. Вложение графа \,G есть перестановка \,\sigma на \,V(G) такая, что если ребро \,xy принадлежит \,E(G), то \,\sigma(x)\sigma(y) не принадлежит \,E(G).

Литература

  • Wo\acute{z}niak.\,\ Diss.