Embedding of a graph: различия между версиями
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>. | ||
Текущая версия от 18:02, 2 июля 2019
Embedding of a graph --- укладка графа, вложение графа.
An embedding of a graph [math]\displaystyle{ G }[/math] (into a complement [math]\displaystyle{ \bar{G} }[/math]) is a permutation [math]\displaystyle{ \sigma }[/math] on [math]\displaystyle{ V(G) }[/math] such that if an edge [math]\displaystyle{ xy }[/math] belongs to [math]\displaystyle{ E(G) }[/math], then [math]\displaystyle{ \sigma(x)\sigma(y) }[/math] does not belong to [math]\displaystyle{ E(G) }[/math]. If there exists an embedding of [math]\displaystyle{ G }[/math], we say that [math]\displaystyle{ G }[/math] is embeddable or that there is a packing of two copies of the graph [math]\displaystyle{ G }[/math] (of order [math]\displaystyle{ n }[/math]) into the complete graph [math]\displaystyle{ K_{n} }[/math].