Árvore (grafo): diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: Adicionando: ru:Дерево (теория графов) |
|||
Linha 4:
Toda árvore é um grafo, mas nem todo grafo é uma árvore.
Toda árvore é um grafo bipartido e planar.▼
Todo grafo conexo possui pelo menos uma árvore de extensão associada, composta de todos os seus vértices e algumas de suas arestas.▼
== Propriedades ==
Em uma árvore, há ''exatamente'' um caminho entre dois vértices quaisquer. Já em uma floresta, há ''no máximo'' um caminho entre dois vértices, devido à não-conectividade.▼
Seja G um grafo. G é uma árvore se satisfaz as seguintes condições:
▲Toda árvore é um grafo bipartido e planar.
▲
▲Todo grafo conexo possui pelo menos uma árvore de extensão associada, composta de todos os seus vértices e algumas de suas arestas.
*''G'' é acíclico, e um simples ciclo é formado se qualquer aresta for adicionada a G.
*''G'' é conexo, e deixará de ser conexo se qualquer aresta for removida de G.
*''G'' é conexo, acíclico e tem ''n'' − 1 arestas.
{{esboço-informática}} {{esboço-matemática}}
| |||