| Wikipédia em português - A enciclop... |
Grau (teoria dos grafos)
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. para o grafo acima, é (3, 3, 3, 2, 2, 1, 0). A seqüência de grau é um grafo invariável logo grafos isomorfos têm a mesma sequência. No entanto, a sequê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 sequência.
O problema da sequência de graus, é o problema de encontrar alguns ou todos os grafos com a seqüência de grau sendo uma dada sequê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.
| Veja mais na Wikipédia.org... |
© Esse artigo usa material da Wikipédia® sob a licença Licença GNU de Documentação Livre e sob nos termos da licença Creative Commons Attribution-ShareAlike
