4624
правки
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. |