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

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

[math]\displaystyle{ \alpha_{i}^{\ast}(E(G_{i})) \cap \alpha_{j}^{\ast}(E(G_{j})) \neq \emptyset\mbox{ для } i \neq j, }[/math]

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

Литература

[Wo\'{z}niak. Diss.]