4625
правок
Упаковка графов: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Упаковка графов''' (''Packing of graphs'') - Пусть <math>G_{1}, \ldots, G_{k}</math>--- графы порядка, ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Упаковка графов''' (''Packing of graphs'') - | '''Упаковка графов''' (''[[Packing of graphs]]'') - | ||
Пусть <math>G_{1}, \ldots, G_{k}</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\ | [<math>Wo\acute{z}niak.\,\ Diss.</math>] | ||