Grau (teoria dos grafos): diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
→Seqüência de graus: Edição para uso do AO 1990 |
m Bot: Parsoid bug phab:T107675 |
||
Linha 22:
Frequentemente, se deseja procurar por grafos simples, tornando o problema da seqüência de graus mais desafiador. Obviamente, a sequência (8, 4) não é a seqüência de grau de um grafo simples, pois teríamos a contradição Δ(''G'') > ((número de vértices;− 1). A sequência (3, 3, 3, 1) também não é a sequência de grau de um grafo simples, mas neste caso o motivo é menos óbvio. Encontrar os critérios gerais de seqüências de grau de grafos simples é um problema clássico; soluções têm sido oferecidas por [[Paul Erdös |Erdős]] e [[Tibor Gallai|Gallai]] (1960), [[V. J. Havel]] (1955) e [[S. L. Hakimi]] (1961) e [[S. A. Choudum]].
Por exemplo, o [[Teorema de Erdös-Gallai]] afirma que a seqüência (''d''<sub>''i''</sub>)<sub>''i''=1,...,''n''</sub> sendo ''d''<sub>''i ''</sub>≥''d
: <math>\sum_{i=1}^{k}d_i \leq k(k-1) + \sum_{i=k+1}^n \min(d_i,k) \quad \text{for } k \in \{1,\dots,n\}.</math>
| |||