Grau (teoria dos grafos): diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 21:
Como conseqüência da fórmula da soma de graus, toda a seqüência com uma soma ímpar, como (3, 3, 1), não pode ser entendida como a seqüência de grau de um grafo. O inverso também é verdadeiro: se uma seqüência tem uma soma par, é a seqüência de grau de um grafo. A construção de um grafo como este é simples: conecte vértices ímpares em pares, e preencha com [[Laço (teoria dos grafos)|laços]] (auto-loops).
Freqüentemente, se deseja procurar por grafos simples, tornando o problema da seqüência de graus mais desafiador. Obviamente, a seqüê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 seqüência (3, 3, 3, 1) também não é a seqüê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), [[S. A. Choudum]] e Sierksma et al. (1991).
Por exemplo, o [[Teorema de Erdös-Gallai]] afirma que a seqüência (''d''<sub>''i''</sub>)<sub>''i''=1,...,''n''</sub> é uma seqüência de grau de um grafo simples [[sse]], a soma da seqüência é par e
<!--▼
: <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>▼
▲<!--
▲: <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>
Havel and Hakimi proved that (''d''<sub>1</sub>, ''d''<sub>2</sub>, ..., ''d''<sub>''n''</sub>) is a degree sequence of a simple graph iff (''d''<sub>2</sub> − 1, ''d''<sub>3</sub> − 1, ..., ''d''<sub>''d''<sub>1</sub>+1</sub> − 1, ''d''<sub>''d''<sub>1</sub>+2</sub>, ''d''<sub>''d''<sub>1</sub>+3</sub>, ..., ''d''<sub>''n''</sub>) is. This fact leads to a simple algorithm (the Havel-Hakimi algorithm) for realizing a simple graph with a given realizable degree sequence: Begin with a graph with no edges. Maintain a list of vertices whose degree requirement has not yet been met in non-increasing order of residual degree requirement. Connect the first vertex to the next ''d''<sub>1</sub> vertices in this list, and then remove it from the list. Re-sort the list and repeat until all degree requirements are met.
| |||