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

Упаковка графов (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})\, i=1, \ldots, k }[/math], такие, что

[math]\displaystyle{ \alpha_{i}^{\ast}(E(G_{i})) \cap \alpha_{j}^{\ast}(E(G_{j})) \neq \emptyset }[/math] для [math]\displaystyle{ 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].

Литература

• [math]\displaystyle{ Wo\acute{z}niak.\,\ Diss. }[/math]