Grau (teoria dos grafos)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Um grafo com vértices rotulados por grau

Na teoria dos grafos, o grau (ou valência) de um vértice de um grafo é o número de arestas incidentes para com o vértice, com os laços contados duas vezes. [1] [2] Ou de forma análoga, o número de vértices adjacentes a ele.[3] O grau de um vértice v é denotado \deg(v). O grau máximo de um grafo G, denotado por Δ(G), e o grau mínimo de um grafo, denotado por δ(G), são os graus máximos e mínimos de seus vértices. No grafo à direita, o grau máximo é 3 e o mínimo é 0. Em um grafo regular, todos os graus são os mesmos, e assim podemos falar de o grau do gráfico.

Lema do aperto de mãos[editar | editar código-fonte]

A fórmula da soma dos graus afirma que, dado um grafo G=(V, E),

\sum_{v \in V} \deg(v) = 2|E|\, .

A fórmula implica que em qualquer grafo, o número de vértices de grau ímpar é par. Esta afirmação (bem como a fórmula de soma grau) é conhecida como o Lema do aperto de mãos (em inglês, handshaking lemma). O último nome vem de um problema matemático popular, para provar que, em qualquer grupo de pessoas o número de pessoas que apertam as mãos com um número ímpar de outras pessoas do grupo é par.

Seqüência de graus[editar | editar código-fonte]

Dois grafos não isomorfos com a mesma seqüência de graus (3, 2, 2, 2, 2, 1, 1, 1).

A seqüência de grau de um grafo não-direcionado é a seqüência não crescente dos seus graus de vértices; [4] para o gráfico acima, é (3, 3, 3, 2, 2, 1, 0). A seqüência de grau é um grafo invariável logo grafos isomorfos têm a mesma seqüência. No entanto, a seqüência de grau, em geral, não identifica unicamente um grafo; em alguns casos, os grafos não isomorfos têm o mesmo grau de seqüência.

O problema da seqüência de graus, é o problema de encontrar alguns ou todos os grafos com a seqüência de grau sendo uma dada seqüência não crescente de números inteiros positivos. Zeros finais podem ser ignorados, uma vez que são trivialmente efetuados pela adição de um número adequado de vértices isolados do grafo.

O problema de encontrar ou estimar o número de grafos com uma seqüência de determinado grau é um problema do campo da enumeração de grafos.

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ç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 Erdős e 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 (di)i=1,...,n sendo didi+1 é uma seqüência de grau de um grafo simples sse, a soma da seqüência é par e

\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\}.

Havel e Hakimi provaram que (d1d2, ..., dn) é uma seqüência de grau de um grafo simples sse (d2 − 1, d3 − 1, ..., dd1+1 − 1, dd1+2, dd1+3, ..., dn) é. Este fato leva a um algoritmo simples (o algoritmo Havel-Hakimi) para a realização de um grafo simples, com uma seqüência de determinado grau de realização: Comece com um grafo sem bordas. Mantenha uma lista de vértices cujo grau de exigência não tenha ainda sido atingido em ordem não-crescente de exigência de grau residual. Conecte o primeiro vértice com os próximos d1 vértices na lista, e depois remova-o da lista. Re-ordene a lista e repita até que todas as exigências do grau estejam cumpridas.

Valores especiais[editar | editar código-fonte]

Um grafo não-direcionado com nodos-folha 4, 5, 6, 7, 10, 11, e 12
  • Um vértice com grau 0 é chamado de vértice isolado.
  • Um vértice com grau 1 é chamado de vértice folha e a aresta conectada a este vértice é chamada de aresta pendente. No grafo à direita, {3,5} é uma aresta pendente. Esta terminologia é comum no estudo de árvores em teoria dos grafos e em especial árvores como estrutura de dados.

Propriedades globais[editar | editar código-fonte]

  • Se cada vértice do grafo tem o mesmo grau k o grafo é chamado de um grafo k-regular e o próprio grafo é dito ter grau k.
  • Um grafo conexo, não-direcionado, tem um caminho euleriano se e somente se ele tem 0 ou 2 vértices de grau ímpar. Se tem 0 vértices de grau ímpar, o caminho Euleriano é um circuito Euleriano.
  • Um grafo direcionado é uma pseudofloresta se e somente se se cada vértice tem um grau de saída no máximo 1. Um grafo funcional é um caso especial de um pseudofloresta em que cada vértice tem exatamente um grau de saída 1.
  • Pelo Teorema de Brooks, qualquer grafo que não seja um clique ou um ciclo ímpar tem um número cromático, de no máximo Δ, e pelo Teorema de Vizing, um grafo tem um índice cromático de no máximo Δ + 1.

Referências

  1. Diestel. Título não preenchido. Favor adicionar. 3ª. ed. Berlin, New York: Springer-Verlag, 2005. ISBN 978-3-540-26183-4. .
  2. Even, Shimon. Graph Algorithms. Rockville, Maryland: Computer Science Press, 1979. 249 pp. ISBN 0-914894-21-8.
  3. Szwarcfiter, Jayme Luiz. Grafos e algoritmos computacionais. Rio de Janeiro: Campus, 1988. ISBN 85-7001-341-8.
  4. Diestel p.278