Аноним

Упаковка графов: различия между версиями

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


<math>\alpha_{i}^{\ast}(E(G_{i})) \cap \alpha_{j}^{\ast}(E(G_{j})) \neq  
:::::<math>\alpha_{i}^{\ast}(E(G_{i})) \cap \alpha_{j}^{\ast}(E(G_{j})) \neq \emptyset</math> для <math>i \neq j,</math>
\emptyset\mbox{ для } i \neq j,</math>


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