Упаковка графов: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>\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}) | |||
\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 | |||
где отображение <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> | |||
Текущая версия от 12:53, 22 сентября 2011
Упаковка графов (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]