GRAFOS PLANARES E ÁRVORE

 

GRAFOS PLANARES E ÁRVORE
Teoria dos grafos
A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto.
Grafo é uma estrutura G(V,A) onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas
Grafo com 4 vértices e 6 arestas. É um grafo completo, conexo e planar.
.



    Um grafo diz-se planar se for possível desenhá-lo de tal forma que duas arestas não se intersectem à excepção nos vértices inicial e final. Por exemplo, o cubo é um grafo planar já que pode ser desenhado como:
   


•    Na teoria dos grafos, uma árvore é um grafo conexo (existe caminho entre quaisquer dois de seus vértices) e acíclico (não possui ciclos). Caso o grafo seja acíclico mas não conexo, ele é dito uma floresta. Uma floresta também é definida como uma união disjunta de árvores.
•    Árvores e Grafos são compostos essencialmente por nós e arestas (ou conexões, se assim preferir chamar) entre eles.
•    Um grafo pode conter ciclos (ou seja, há um caminho saindo de um nó que leva, por meio de outros nós, até ele novamente) ou não. Quando um grafo é conexo e acíclico (isto é, sem ciclos), diz-se que se tem uma árvore.


Uma árvore contendo nove nós, sendo o nó 1 o nó-raiz e os nós 3, 5, 6, 7, 8 e 9 nós-folhas
•    Na imagem anterior, podemos dizer que há três níveis: o primeiro, onde se encontra o nó-raiz 1; o segundo, onde se encontram os nós 2, 3 e 4, filhos do nó-raiz; e o terceiro, onde se encontram os nós 5, 6, 7, 8 e 9, filhos dos filhos do nó-raiz.