Antimagic graph: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Antimagic graph''' --- антимагический граф. An '''antimagic graph''' is a graph whose edges can be labeled with inte...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Antimagic graph''' | '''Antimagic graph''' — ''[[антимагический граф]].'' | ||
An '''antimagic graph''' is a | An '''antimagic graph''' is a [[graph, undirected graph, nonoriented graph|graph]] whose [[edge|edges]] can be labeled with integers <math>1,2, \ldots, e</math> so that the sum of the labels at any given [[vertex]] is different from the sum of the labels of any other vertex, that is, no two vertices have the same sum. Hartsfield and Ringel conjecture that every [[tree]] other | ||
graph whose edges can be labeled with integers <math>1,2, \ldots, e</math> so | than <math>\,K_{2}</math> is antimagic and, more strongly, that every [[connected graph]] other than <math>\,K_{2}</math> is antimagic. | ||
that the sum of the labels at any given vertex is different from the | |||
sum of the labels of any other vertex, that is, no two vertices have | |||
the same sum. | |||
than <math>K_{2}</math> is antimagic and, more strongly, that every connected | |||
graph other than <math>K_{2}</math> is antimagic. | |||
A special case is an <math>(a,d)</math>-'''antimagic graph'''. The weight <math>w(x)</math> | A special case is an <math>\,(a,d)</math>-'''antimagic graph'''. The [[weight (of a vertex)|weight]] <math>\,w(x)</math> of a vertex <math>x \in V(G)</math> under an edge labeling <math>f: \; E \rightarrow \{1,2, \ldots,e\}</math> is the sum of values <math>\,f(xy)</math> assigned to all edges incident with a given vertex <math>\,x</math>. A connected graph <math>\,G = (V,E)</math> is said to be <math>\,(a,d)</math>-'''antimagic''' if there exist positive integers <math>\,a,d</math> and a bijection <math>f: \; E \rightarrow \{1,2, \ldots, e\}</math> such that the induced mapping <math>g_{f}: \; V(G) \rightarrow W</math> is also bijection, | ||
of a vertex <math>x \in V(G)</math> under an edge labeling <math>f: \; E \rightarrow | |||
\{1,2, \ldots,e\}</math> is the sum of values <math>f(xy)</math> assigned to all edges | |||
incident with a given vertex <math>x</math>. A connected graph <math>G = (V,E)</math> is said | |||
to be <math>(a,d)</math>-'''antimagic''' if there exist positive integers <math>a,d</math> | |||
and a bijection <math>f: \; E \rightarrow \{1,2, \ldots, e\}</math> such that the | |||
induced mapping <math>g_{f}: \; V(G) \rightarrow W</math> is also bijection, | |||
where <math>W = \{w(x); x \in V(G)\} = \{a, a+d, a+2d, \ldots, a+(v-1)D\}</math> is | where <math>W = \{w(x); x \in V(G)\} = \{a, a+d, a+2d, \ldots, a+(v-1)D\}</math> is | ||
the set of the weights of vertices. | the set of the weights of vertices. | ||
Текущая версия от 13:51, 2 декабря 2011
Antimagic graph — антимагический граф.
An antimagic graph is a graph whose edges can be labeled with integers [math]\displaystyle{ 1,2, \ldots, e }[/math] so that the sum of the labels at any given vertex is different from the sum of the labels of any other vertex, that is, no two vertices have the same sum. Hartsfield and Ringel conjecture that every tree other than [math]\displaystyle{ \,K_{2} }[/math] is antimagic and, more strongly, that every connected graph other than [math]\displaystyle{ \,K_{2} }[/math] is antimagic.
A special case is an [math]\displaystyle{ \,(a,d) }[/math]-antimagic graph. The weight [math]\displaystyle{ \,w(x) }[/math] of a vertex [math]\displaystyle{ x \in V(G) }[/math] under an edge labeling [math]\displaystyle{ f: \; E \rightarrow \{1,2, \ldots,e\} }[/math] is the sum of values [math]\displaystyle{ \,f(xy) }[/math] assigned to all edges incident with a given vertex [math]\displaystyle{ \,x }[/math]. A connected graph [math]\displaystyle{ \,G = (V,E) }[/math] is said to be [math]\displaystyle{ \,(a,d) }[/math]-antimagic if there exist positive integers [math]\displaystyle{ \,a,d }[/math] and a bijection [math]\displaystyle{ f: \; E \rightarrow \{1,2, \ldots, e\} }[/math] such that the induced mapping [math]\displaystyle{ g_{f}: \; V(G) \rightarrow W }[/math] is also bijection, where [math]\displaystyle{ W = \{w(x); x \in V(G)\} = \{a, a+d, a+2d, \ldots, a+(v-1)D\} }[/math] is the set of the weights of vertices.