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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Упаковка графов''' (''Packing of graphs'') - Пусть <math>G_{1}, \ldots, G_{k}</math>--- графы порядка, ...)
 
Нет описания правки
Строка 1: Строка 1:
'''Упаковка графов''' (''Packing of graphs'') -  
'''Упаковка графов''' (''[[Packing of graphs]]'') -  
Пусть <math>G_{1}, \ldots, G_{k}</math>--- графы порядка, не превышающего <math>n</math>.
Пусть <math>G_{1}, \ldots, G_{k}</math> - [[граф|графы]] [[порядок группы графа|порядка]], не превышающего <math>n</math>.
Говорят, что существует упаковка этих графов в <math>K_{n}</math> если
Говорят, что существует упаковка этих графов в <math>K_{n}</math>, если
найдутся инъекции <math>\alpha_{i}: \, V_{i} \rightarrow V(K_{n})</math> <math>i=1,
найдутся инъекции <math>\alpha_{i}: \, V_{i} \rightarrow V(K_{n})</math> <math>i=1,
\ldots, k</math>, такие, что
\ldots, k</math>, такие, что
Строка 10: Строка 10:
где отображение <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>
называется ''<math>k</math>-размещением'' <math>G</math> (<math>k</math>-placement).
называется ''[[k-Размещение|<math>k</math>-размещением]]'' <math>G</math> ([[k-placement|<math>k</math>-placement]]).
Размещение двух копий <math>G</math>, т.е.
Размещение двух копий <math>G</math>, т.е.
2-размещение, называется ''вложением'' <math>G</math> (embedding)
2-размещение, называется ''[[вложение графов|вложением]]'' <math>G</math> ([[embedding]])
(в его дополнение <math>\bar{G}</math>.
(в его дополнение <math>\bar{G}</math>.
Вложение графа <math>G</math> есть перестановка <math>\sigma</math> на <math>V(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>xy</math> принадлежит <math>E(G)</math>, то <math>\sigma(x)\sigma(y)</math> не
принадлежит <math>E(G)</math>.
принадлежит <math>E(G)</math>.
==Литература==
==Литература==
[Wo\'{z}niak. Diss.]
[<math>Wo\acute{z}niak.\,\ Diss.</math>]

Версия от 12:44, 17 февраля 2010

Упаковка графов (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].

Литература

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