O algoritmo de Kruskal - a construção do esqueleto ideal

No início do século 19, o geômetra de Berlim, Jacob Steinerdefiniu a tarefa de como conectar as três aldeias de modo que seu comprimento fosse o mais curto. Posteriormente, ele generalizou esse problema: é necessário encontrar um ponto no plano de tal forma que a distância dele a outros pontos fosse menor. No século 20, os trabalhos sobre esse tema continuaram. Foi decidido tirar vários pontos e conectá-los de tal forma que a distância entre eles fosse a mais curta. Isso tudo é um caso especial do problema em estudo.

Algoritmos gananciosos

O algoritmo Kruskal refere-se a algoritmos "gulosos"(eles também são chamados de gradiente). A essência deles - a maior vitória em cada etapa. Nem sempre os algoritmos "gananciosos" oferecem a melhor solução para a tarefa. Existe uma teoria que mostra que quando aplicados a problemas específicos, eles fornecem a solução ideal. Esta é a teoria dos matróides. O algoritmo de Kruskal relaciona-se com tais problemas.

Encontrando o esqueleto do peso mínimo

O algoritmo em consideração constrói um ótimoo esqueleto do gráfico. O problema é o seguinte. Um gráfico não direcionado sem múltiplas arestas e loops é dado, e em seu conjunto de arestas é dada uma função de peso w que atribui a cada aresta e um número - o peso da aresta - w (e). O peso de cada subconjunto do conjunto de arestas é determinado pela soma dos pesos de suas arestas. É necessário encontrar o esqueleto do menor peso.

Descrição

O algoritmo Kruskal funciona assim. Primeiro, todas as arestas do gráfico original são organizadas em ordem crescente de pesos. Inicialmente, a estrutura não contém arestas, mas inclui todos os vértices do gráfico. Após a próxima etapa do algoritmo, uma borda é adicionada à parte já construída da estrutura, que é uma floresta de expansão. Não é escolhido arbitrariamente. Todas as arestas do gráfico que não pertencem ao esqueleto podem ser chamadas de vermelho e verde. Os vértices de cada costela vermelha estão em um componente da conectividade da floresta que está sendo construída, e os vértices do verde estão em diferentes componentes. Portanto, se você adicionar uma borda vermelha nesse ponto, um ciclo será exibido e, se for o verde, na etapa de floresta resultante, o componente de conectividade será reduzido em um. Assim, nenhuma borda vermelha pode ser adicionada à construção resultante, mas qualquer borda verde pode ser adicionada para obter a floresta. E uma costela verde com um peso mínimo é adicionada. Como resultado, o esqueleto do menor peso é obtido.

Implementação

Denote a floresta atual F. Ele divide o conjunto de vértices do gráfico em domínios conectados (suas formas de união F e eles não se cruzam em pares). As bordas vermelhas têm ambos os vértices em uma parte. Part (x) é uma função que retorna o nome da parte à qual x pertence para cada vértice x. Unite (x, y) é um procedimento que constrói uma nova partição que consiste na união das partes x e y e todas as outras partes. Seja n o número de arestas do gráfico. Todos esses conceitos estão incluídos no algoritmo Kruskal. Implementação:

1. Organize todas as arestas do gráfico do 1º ao nono peso ascendente. (ai, bi são os vértices da aresta com índice i).

2. para i = 1 para n fazer.

3. x: = parte (ai).

4. y: = parte (bi).

5. Se x não for igual a y, então Unite (x, y), inclua a aresta com o número i em F.

Correção

Seja T o esqueleto do grafo original construído usando o algoritmo Kruskal, e seja S seu esqueleto arbitrário. É necessário provar que w (T) não excede w (S).

Seja M o conjunto de arestas de S, P o conjunto de arestasT. Se S não é igual a T, então há uma borda et do esqueleto T que não pertence a S. Nós juntamos et a S. Nós formamos um ciclo, nós o chamamos C. Nós removemos de C qualquer aresta pertencente a S. Um novo esqueleto é obtido, e existem tantos vértices nele. Seu peso não excede w (S), já que w (et) não é maior que w (es) pelo algoritmo de Kruskal. Esta operação (a substituição das arestas de S pelas arestas de T) será repetida até obtermos T. O peso de cada esqueleto resultante sucessivo não é maior que o peso do anterior, do qual se segue que w (T) é no máximo w (S).

Além disso, a exatidão do algoritmo Kruskal segue do teorema de Rado-Edmonds em matróides.

Exemplos da aplicação do algoritmo Kruskal

Dado um gráfico com vértices a, b, c, d, e e arestas (a,b), (A, E), (b, c), (b, e), (c, d), (C, E), (d, e). Os pesos das arestas são mostrados na tabela e na figura. Inicialmente, a construção da floresta F contém todos os vértices do gráfico e não contém uma única aresta. Algoritmo de Kruskal primeiro adicionar nervura (a, e), uma vez que o peso o mais baixo, e os vértices A e E são em componentes diferentes conectividade madeira F (nervura (a, e) é verde), em seguida, a nervura (c, d), porque que, pelo menos, esta borda de peso bordas do gráfico, não pertencentes a F, e é verde, então, pelas mesmas razões acumular borda (a, b). Mas a borda (b, e) é passado, mesmo que ele eo peso mínimo das bordas restantes, porque é vermelho: os vértices b e e pertencem ao mesmo componente de conectividade florestal F, isto é, se somarmos a F a borda (b, e), é formado ciclo. Em seguida, a borda verde (b, c) é adicionada, a borda vermelha (c, e) é ignorada e, em seguida, d, e. sequencialmente Assim, são adicionados bordas (a, e), (c, d), (a, b), (b, c). A partir dele, o esqueleto ideal do grafo original consiste. É assim que o algoritmo funciona neste caso Eu tingi. Um exemplo mostra isso.

A figura mostra um gráfico que consiste em dois componentes de conectividade. Linhas em negrito mostram as arestas da estrutura ótima (verde), construídas usando o algoritmo de Kruskal.

A figura superior mostra o gráfico original e, no inferior, o esqueleto do peso mínimo, construído para ele com a ajuda do algoritmo considerado.

A sequência de arestas adicionadas: (1.6); (0,3), (2,6) ou (2,6), (0,3) - não importa; (3,4); (0,1), (1,6) ou (1,6), (0,1), também é indiferente (5,6).

O algoritmo de Kruskal encontra aplicação prática, por exemplo, para otimizar blocos de comunicação, estradas em novos bairros nas localidades de cada país e também em outros casos.