Codiameter: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Codiameter''' --- кодиаметр. Let <math>u,v \in V(G)</math> be any two distinct vertices. We denote by <math>p(u,v)</math> the length of the longest pat…») |
KEV (обсуждение | вклад) Нет описания правки |
||
Строка 1: | Строка 1: | ||
'''Codiameter''' | '''Codiameter''' — ''[[кодиаметр]].'' | ||
Let <math>u,v \in V(G)</math> be any two distinct vertices. We denote by <math>p(u,v)</math> | Let <math>\,u,v \in V(G)</math> be any two distinct [[vertex|vertices]]. We denote by <math>\,p(u,v)</math> the length of the longest [[path]] connecting <math>\,u</math> and <math>\,v</math>. The '''codiameter''' of <math>\,G</math>, denoted by <math>\,d^{\ast}</math>, is defined to be | ||
the length of the longest path connecting <math>u</math> and <math>v</math>. The '''codiameter''' of <math>G</math>, denoted by <math>d^{\ast}</math>, is defined to be | <math>\min\{p(u,v) | \; u,v \in V(G)\}</math>. A [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math> of order <math>\,n</math> is said to be '''[[Hamiltonian connected graph|Hamilton-connected]]''' if <math>d^{\ast}(G) = n-1</math>, i.e. every two distinct vertices are joined by a ''[[Hamiltonian path]]'' | ||
<math>\min\{p(u,v) | \; u,v \in V(G)\}</math>. A graph <math>G</math> of order <math>n</math> is said | |||
to be '''Hamilton-connected''' if <math>d^{\ast}(G) = n-1</math>, i.e. every two | ==Литература== | ||
distinct vertices are joined by a ''Hamiltonian path'' | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. |
Текущая версия от 19:40, 12 ноября 2013
Codiameter — кодиаметр.
Let [math]\displaystyle{ \,u,v \in V(G) }[/math] be any two distinct vertices. We denote by [math]\displaystyle{ \,p(u,v) }[/math] the length of the longest path connecting [math]\displaystyle{ \,u }[/math] and [math]\displaystyle{ \,v }[/math]. The codiameter of [math]\displaystyle{ \,G }[/math], denoted by [math]\displaystyle{ \,d^{\ast} }[/math], is defined to be [math]\displaystyle{ \min\{p(u,v) | \; u,v \in V(G)\} }[/math]. A graph [math]\displaystyle{ \,G }[/math] of order [math]\displaystyle{ \,n }[/math] is said to be Hamilton-connected if [math]\displaystyle{ d^{\ast}(G) = n-1 }[/math], i.e. every two distinct vertices are joined by a Hamiltonian path
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.