Degree sequence: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Degree sequence''' --- степенная последовательность. For a graph <math>G</math>, its '''degree sequence''' <math>d_{1} \geq d_{2} \ge…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Degree sequence''' | '''Degree sequence''' — степенная последовательность. | ||
For a graph <math>G</math>, its '''degree sequence''' <math>d_{1} \geq d_{2} \geq \ldots \geq d_{n}</math> | For a graph <math>G</math>, its '''degree sequence''' <math>d_{1} \geq d_{2} \geq \ldots \geq d_{n}</math> | ||
| Строка 7: | Строка 7: | ||
\ldots, d_{n}</math> as its degree sequence. | \ldots, d_{n}</math> as its degree sequence. | ||
==See also== | ==See also== | ||
*''Havel | * ''Havel — Hakimi criterion, <math>Erd\ddot{o}s</math> — Gallai criterion.'' | ||
Текущая версия от 17:30, 3 мая 2011
Degree sequence — степенная последовательность.
For a graph [math]\displaystyle{ G }[/math], its degree sequence [math]\displaystyle{ d_{1} \geq d_{2} \geq \ldots \geq d_{n} }[/math] is the ordered sequence of the degrees of its vertices. A sequence [math]\displaystyle{ d_{1} \geq d_{2} \geq \ldots \geq d_{n} }[/math] with [math]\displaystyle{ n-1 \geq d_{1} }[/math] is a graphic sequence of numbers if there is a graph having [math]\displaystyle{ D_{1}, \ldots, d_{n} }[/math] as its degree sequence.
See also
- Havel — Hakimi criterion, [math]\displaystyle{ Erd\ddot{o}s }[/math] — Gallai criterion.