Teoremas de Grafos Conexos
Classificado em Formação e Orientação para o Emprego
Escrito em em
português com um tamanho de 3,59 KB
Teorema 3
Seja G(V,A) um grafo não orientado e conexo com n vértices. Então, G contém pelo menos n-1 arestas.
Prova por indução estrutural:
Assuma que G(V,A) é um grafo não orientado e conexo com n vértices. Seja P a propriedade de que G tenha pelo menos n-1 arestas.
- Base: G(1,0) tem um vértice e nenhuma aresta. Logo, a propriedade P é verdadeira.
- Passo de indução: Seja G(V,A) um grafo não orientado e conexo com a propriedade P acima, e G' um grafo obtido a partir de G por uma das operações que se seguem:
Inserção de vértice: Para que o grafo G' permaneça conexo, ao se inserir um novo vértice em G', faz-se necessário inserir uma nova aresta que o conecte a algum outro vértice de G'. Logo, a propriedade P é mantida em G'.
Inserção
... Continue a ler "Teoremas de Grafos Conexos" »