Iremos introduzir alguns conceitos ao decorrer deste artigo até chegarmos a árvore geradora mínima em si. E também iremos falar de algumas de suas propriedades.
Subgrafo de custo mínimo
Seja G um grafo com custos nas arestas (os custos podem ser positivos, negativos, ou nulos). O custo de um subgrafo T de G é a soma dos custos das arestas de T. Se U é uma coleção de subgrafos de G, um elemento T de U tem custo mínimo se o custo de T é menor ou igual [note o "ou igual"] que o custo de qualquer outro elemento de U.
Em outras palavras, T tem custo mínimo se nenhum elemento de U tem custo estritamente menor que o de T.
Árvore geradora mínima
Uma árvore geradora mínima (= minimum spanning tree), ou MST, de um grafo com custos nas arestas é qualquer árvore geradora do grafo que tenha custo mínimo.
Problema: Encontrar uma MST de um grafo G com custos nas arestas.
É claro que o problema tem solução se e somente se o grafo G é conexo. Boa pergunta: como encontrar uma MST de um grafo conexo se todas as suas arestas têm o mesmo custo?
A propriedade dos ciclos
A Primeira Propriedade da Troca, discutida no artigo anterior, leva à seguinte condição de otimalidade:
Condição de Otimalidade: Se T é uma MST de um grafo então toda aresta e fora de T tem custo máximo dentre as arestas do único ciclo não-trivial em T+e.
(A recíproca dessa proposição é verdadeira, mas sua demonstração é um pouco mais complexa.)
Exemplo: Seja T a árvore geradora definida pelas 5 arestas "internas" da figura. Seja e a aresta "horizontal" "superior". Como e não é máxima no ciclo não-trivial de T+e, a árvore T não é uma MST.
A propriedade dos cortes
A Segunda Propriedade da Troca, discutida no artigo anterior, leva à seguinte condição de otimalidade:
Condição de Otimalidade: Se T é uma MST de um grafo então cada aresta t de T é uma aresta mínima dentre as que atravessam o corte determinado por T–t.
(A recíproca dessa proposição é verdadeira, mas sua demonstração é um pouco mais complexa.)
Exemplo: Seja T a árvore geradora definida pelas cinco arestas "internas" da figura. Seja t a aresta "horizontal" no meio da figura. Como t não é mínima no corte determinado por T–t, a árvore T não é uma MST.
Fonte: IME
Subgrafo de custo mínimo
Seja G um grafo com custos nas arestas (os custos podem ser positivos, negativos, ou nulos). O custo de um subgrafo T de G é a soma dos custos das arestas de T. Se U é uma coleção de subgrafos de G, um elemento T de U tem custo mínimo se o custo de T é menor ou igual [note o "ou igual"] que o custo de qualquer outro elemento de U.
Em outras palavras, T tem custo mínimo se nenhum elemento de U tem custo estritamente menor que o de T.
Árvore geradora mínima
Uma árvore geradora mínima (= minimum spanning tree), ou MST, de um grafo com custos nas arestas é qualquer árvore geradora do grafo que tenha custo mínimo.
Problema: Encontrar uma MST de um grafo G com custos nas arestas.
É claro que o problema tem solução se e somente se o grafo G é conexo. Boa pergunta: como encontrar uma MST de um grafo conexo se todas as suas arestas têm o mesmo custo?
A propriedade dos ciclos
A Primeira Propriedade da Troca, discutida no artigo anterior, leva à seguinte condição de otimalidade:
Condição de Otimalidade: Se T é uma MST de um grafo então toda aresta e fora de T tem custo máximo dentre as arestas do único ciclo não-trivial em T+e.
(A recíproca dessa proposição é verdadeira, mas sua demonstração é um pouco mais complexa.)
Exemplo: Seja T a árvore geradora definida pelas 5 arestas "internas" da figura. Seja e a aresta "horizontal" "superior". Como e não é máxima no ciclo não-trivial de T+e, a árvore T não é uma MST.
A propriedade dos cortes
A Segunda Propriedade da Troca, discutida no artigo anterior, leva à seguinte condição de otimalidade:
Condição de Otimalidade: Se T é uma MST de um grafo então cada aresta t de T é uma aresta mínima dentre as que atravessam o corte determinado por T–t.
(A recíproca dessa proposição é verdadeira, mas sua demonstração é um pouco mais complexa.)
Exemplo: Seja T a árvore geradora definida pelas cinco arestas "internas" da figura. Seja t a aresta "horizontal" no meio da figura. Como t não é mínima no corte determinado por T–t, a árvore T não é uma MST.
Fonte: IME
