Teoria dos grafos - Árvores
Árvores são gráficos que não contêm nem mesmo um único ciclo. Eles representam a estrutura hierárquica de forma gráfica. As árvores pertencem à classe mais simples de gráficos. Apesar de sua simplicidade, eles possuem uma estrutura rica.
As árvores fornecem uma gama de aplicações úteis, tão simples como uma árvore genealógica a tão complexas quanto árvores em estruturas de dados de ciência da computação.
Árvore
UMA connected acyclic graphé chamado de árvore. Em outras palavras, um gráfico conectado sem ciclos é chamado de árvore.
As bordas de uma árvore são conhecidas como branches. Os elementos das árvores são chamados de nós. Os nós sem nós filhos são chamadosleaf nodes.
Uma árvore com 'n' vértices possui 'n-1' arestas. Se ele tiver mais uma aresta extra do que 'n-1', então a aresta extra deve obviamente emparelhar com dois vértices que levam a formar um ciclo. Então, ele se torna um gráfico cíclico, o que é uma violação do gráfico da árvore.
Example 1
O gráfico mostrado aqui é uma árvore porque não tem ciclos e está conectado. Possui quatro vértices e três arestas, ou seja, para 'n' vértices 'n-1' arestas conforme mencionado na definição.
Note - Cada árvore possui pelo menos dois vértices de grau um.
Example 2
No exemplo acima, os vértices 'a' e 'd' possuem grau um. E os outros dois vértices 'b' e 'c' têm grau dois. Isso é possível porque, para não formar um ciclo, deve haver pelo menos duas arestas únicas em qualquer lugar do gráfico. Não são nada além de duas arestas com grau de um.
Floresta
UMA disconnected acyclic graphé chamado de floresta. Em outras palavras, uma coleção desconexa de árvores é chamada de floresta.
Example
O gráfico a seguir se parece com dois subgráficos; mas é um único gráfico desconectado. Não há ciclos neste gráfico. Portanto, claramente é uma floresta.
Árvores Medidas
Seja G um grafo conectado, então o subgráfico H de G é chamado de árvore geradora de G se -
- H é uma árvore
- H contém todos os vértices de G.
Uma árvore geradora T de um grafo não direcionado G é um subgrafo que inclui todos os vértices de G.
Example
No exemplo acima, G é um gráfico conectado e H é um subgráfico de G.
É claro que o grafo H não tem ciclos, é uma árvore com seis arestas que é um a menos que o número total de vértices. Portanto, H é a árvore de abrangência de G.
Classificação do circuito
Seja 'G' um gráfico conectado com 'n' vértices e 'm' arestas. Uma árvore geradora 'T' de G contém (n-1) arestas.
Portanto, o número de arestas que você precisa excluir de 'G' para obter uma árvore geradora = m- (n-1), que é chamada de classificação de circuito de G.
Esta fórmula é verdadeira, porque em uma árvore abrangente você precisa ter 'n-1' arestas. Fora das 'm' arestas, você precisa manter 'n – 1' arestas no gráfico.
Portanto, deletar 'n – 1' arestas de 'm' fornece as arestas a serem removidas do gráfico para obter uma árvore geradora, que não deve formar um ciclo.
Example
Dê uma olhada no gráfico a seguir -
Para o gráfico dado no exemplo acima, você tem m = 7 arestas en = 5 vértices.
Então, a classificação do circuito é -
Example
Seja 'G' um grafo conectado com seis vértices e o grau de cada vértice é três. Encontre a classificação do circuito de 'G'.
Pela soma do teorema do grau dos vértices,
Teorema de Kirchoff
O teorema de Kirchoff é útil para encontrar o número de árvores geradoras que podem ser formadas a partir de um grafo conectado.
Example
A matriz 'A' deve ser preenchida como, se houver uma aresta entre dois vértices, ela deve ser fornecida como '1', caso contrário, '0'.
$$ A = \ begin {vmatrix} 0 & a & b & c & d \\ a & 0 & 1 & 1 & 1 \\ b & 1 & 0 & 0 & 1 \\ c & 1 & 0 & 1 \\ d & 1 & 1 & 1 & 0 \ end {vmatrix} = \ begin {vmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 e 1 e 1 e 0 \ end {vmatrix} $$Usando o teorema de Kirchoff, ele deve ser alterado substituindo os valores principais da diagonal pelo grau dos vértices e todos os outros elementos por -1.A
$$ = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = M $$ $$ M = \ begin {vmatrix} 3 & -1 & -1 & -1 \\ - 1 & 2 & 0 & -1 \\ - 1 & 0 & 2 & -1 \\ - 1 & -1 & -1 & 3 \ end {vmatrix} = 8 $$ $$ Co \: \: fator \: \: of \: \: m1 \: \: = \ begin {vmatrix } 2 & 0 & -1 \\ 0 & 2 & -1 \\ - 1 & -1 & 3 \ end {vmatrix} $$Portanto, o número de árvores abrangentes = 8.