1023
правки
Embedding of a graph: различия между версиями
Материал из WEGA
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''Embedding of a graph''' --- укладка графа, вложение графа. An '''embedding''' of a graph <math>G</math> (into a ''complement'' <math>\b…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 2: | Строка 2: | ||
An '''embedding''' of a graph <math>G</math> (into a ''complement'' <math>\bar{G}</math>) is a | An '''embedding''' of a graph <math>G</math> (into a ''complement'' <math>\bar{G}</math>) is a | ||
permutation <math>\sigma</math> on <math>V(G)</math> such that if an edge <math>xy</math> belongs to | |||
<math>E(G)</math>, then <math>\sigma(x)\sigma(y)</math> does not belong to <math>E(G)</math>. If there | <math>E(G)</math>, then <math>\sigma(x)\sigma(y)</math> does not belong to <math>E(G)</math>. If there | ||
exists an embedding of <math>G</math>, we say that <math>G</math> is embeddable or that there | exists an embedding of <math>G</math>, we say that <math>G</math> is embeddable or that there | ||
is a '''packing''' of two copies of the graph <math>G</math> (of order <math>n</math>) into | is a '''packing''' of two copies of the graph <math>G</math> (of order <math>n</math>) into | ||
the complete graph <math>K_{n}</math>. | the complete graph <math>K_{n}</math>. | ||
