Graceful graph: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Graceful graph''' --- грациозный граф. A graph <math>G = (V,E)</math> is said to be a '''graceful graph''' if there is an injection <math>f</math>…») |
(нет различий)
|
Текущая версия от 16:05, 16 мая 2011
Graceful graph --- грациозный граф.
A graph [math]\displaystyle{ G = (V,E) }[/math] is said to be a graceful graph if there is an injection [math]\displaystyle{ f }[/math] (labelling)
[math]\displaystyle{ f: \; V(G) \rightarrow \{0,1, \ldots, q\} }[/math]
such that the induced function
[math]\displaystyle{ f^{\ast}: \; E(G) \rightarrow \{1,2, \ldots, q\} }[/math]
defined by
[math]\displaystyle{ f^{\ast}(xy) = |f(x) - f(y)| \mbox{ (for all }xy \in E(G)) }[/math]
is an injection.
The images of [math]\displaystyle{ f }[/math] and [math]\displaystyle{ f^{\ast} }[/math] are called respectively vertex and edge labels.
Graceful labellings were first considered by Rosa in 1966.