Árvore geradora
Uma subárvore de um grafo G é qualquer árvore T que seja subgrafo de G. Em outras palavras, um árvore T é subárvore de G se todo vértice de T é vértice de G e toda aresta de T é aresta de G.
Uma subárvore geradora ou árvore geradora (= spanning tree) de um grafo G é qualquer subárvore de G que contenha todos os vértices de G.
É claro que somente grafos conexos têm árvores geradoras. Reciprocamente, todo grafo conexo tem uma árvore geradora. (Em geral, um grafo conexo tem muitas árvores geradoras diferentes.)
Algoritmos que calculam árvores geradoras
É fácil calcular uma árvore geradora de um grafo conexo: a busca em profundidade e a busca em largura fazem isso. Mais precisamente, qualquer das duas buscas calcula uma arborescência que contém um dos arcos de cada aresta de uma árvore geradora do grafo.
Primeira propriedade da troca de arestas
Seja G um grafo e H um subgrafo gerador de G. Para qualquer aresta h de H, vamos denotar por H–h o grafo que se obtém quando h é removida de H. Para qualquer aresta e de G, vamos denotar por H+e o grafo que se obtém quando e é inserida em H.
Primeira Propriedade da Troca: Seja T uma árvore geradora de um grafo G. Para qualquer aresta e de G que não esteja em T, o grafo T + e tem um único ciclo não-trivial. Para qualquer aresta t desse ciclo, o grafo T + e – t é uma árvore geradora de G.
Exemplo: Seja T a árvore geradora definida pelas cinco arestas "internas" da figura. Seja e a aresta 0-1. O único ciclo não-trivial de T+e é 0-1-5-4-0. Para qualquer aresta t desse ciclo, T+e–t é uma árvore geradora.
Segunda propriedade da troca de arestas
Seja T uma árvore geradora de um grafo G. Para toda aresta t de T, as duas componentes de T–t definem um corte em G. Diremos que esse é o corte determinado por T–t. A única aresta de T que atravessa o corte é t.
Segunda Propriedade da Troca: Seja T uma árvore geradora de um grafo G. Para qualquer aresta t de T e qualquer aresta e de G que atravesse o corte determinado por T–t, o grafo T – t + e é uma árvore geradora de G.
Exemplo: Seja T a árvore geradora definida pelas cinco arestas "internas" da figura. Seja t a aresta 4-5. O corte determinado por T–t tem três arestas: 0-1, 4-5 e 3-2. Se e é uma qualquer dessas arestas então T–t+e é uma árvore geradora.
Fonte: IME
Uma subárvore de um grafo G é qualquer árvore T que seja subgrafo de G. Em outras palavras, um árvore T é subárvore de G se todo vértice de T é vértice de G e toda aresta de T é aresta de G.
Uma subárvore geradora ou árvore geradora (= spanning tree) de um grafo G é qualquer subárvore de G que contenha todos os vértices de G.
É claro que somente grafos conexos têm árvores geradoras. Reciprocamente, todo grafo conexo tem uma árvore geradora. (Em geral, um grafo conexo tem muitas árvores geradoras diferentes.)
Algoritmos que calculam árvores geradoras
É fácil calcular uma árvore geradora de um grafo conexo: a busca em profundidade e a busca em largura fazem isso. Mais precisamente, qualquer das duas buscas calcula uma arborescência que contém um dos arcos de cada aresta de uma árvore geradora do grafo.
Primeira propriedade da troca de arestas
Seja G um grafo e H um subgrafo gerador de G. Para qualquer aresta h de H, vamos denotar por H–h o grafo que se obtém quando h é removida de H. Para qualquer aresta e de G, vamos denotar por H+e o grafo que se obtém quando e é inserida em H.
Primeira Propriedade da Troca: Seja T uma árvore geradora de um grafo G. Para qualquer aresta e de G que não esteja em T, o grafo T + e tem um único ciclo não-trivial. Para qualquer aresta t desse ciclo, o grafo T + e – t é uma árvore geradora de G.
Exemplo: Seja T a árvore geradora definida pelas cinco arestas "internas" da figura. Seja e a aresta 0-1. O único ciclo não-trivial de T+e é 0-1-5-4-0. Para qualquer aresta t desse ciclo, T+e–t é uma árvore geradora.
Segunda propriedade da troca de arestas
Seja T uma árvore geradora de um grafo G. Para toda aresta t de T, as duas componentes de T–t definem um corte em G. Diremos que esse é o corte determinado por T–t. A única aresta de T que atravessa o corte é t.
Segunda Propriedade da Troca: Seja T uma árvore geradora de um grafo G. Para qualquer aresta t de T e qualquer aresta e de G que atravesse o corte determinado por T–t, o grafo T – t + e é uma árvore geradora de G.
Exemplo: Seja T a árvore geradora definida pelas cinco arestas "internas" da figura. Seja t a aresta 4-5. O corte determinado por T–t tem três arestas: 0-1, 4-5 e 3-2. Se e é uma qualquer dessas arestas então T–t+e é uma árvore geradora.
Fonte: IME
