Changes

Essa seção explica como usar o Maple para construir árvores de extensão (spanning trees) para grafos e como usar árvores de extensão usá-las para resolver muitos tipos diferentes de problema. Árvores de extensão já foram usadas no capítulo 7; elas tem uma grande quantidade de aplicações. Em particular, nós iremos mostrar como usar o Maple para formar as essas árvores de extensão usando dois algoritmos: depth-first search (busca em profundidade) e breadth-first search(busca em largura). Então nós iremos mostrar , mostraremos como usar o Maple para fazer backtracking, uma ténica baseada em depth-first search , usada para resolver vários problemas.

Para começar, nós iremos discutir discutiremos como implementar o algoritmo de depth-first search no Maple. Como o nome do algoritmo (busca em profundidade, em português) sugere, os vértices são visitados em ordem de crescimento crescente de profundidade da na árvore de extensão. O pseudocódigo é:

2. Escolha x para ser um vizinho de w que não está na árvore. Adicione aresta(x,w) e faça conjunto w igual a = x.

3. Repita o passo (2) até não haver ter mais vértices que não estão na árvore.

 Nós demonstramos Demonstramos o uso do procedure de depth-first search com o seguinte exemplo:

Tendo implementado o algoritmo de árvore de extensão de depth-first search, agora nós podemos modificar levemente o código Maple e conseguir uma árvore de extensão com breadth-first search. Especificamente, o O algoritmo de breadth-first search opera examinando todos os vértices da atual profundidade do grafo antes de se mover para baixo, no próximo nível do grafo. Antes de implementar esse algoritmo, nós damos uma descrição em pseudocódigo do algoritmodele.

2. Adicione arestas de V até para cada vértice em N_1 que ainda não está na árvore de extensão.

Backtracking é um método que pode ser usado para achar soluções para resolver problemas que poderiam ser impráticos de se resolver solucionar usando técnicas de busca excessiva, . O backtracking é baseado na busca sistemática pela solução de um problema usando uma árvore de decisão. Aqui nós mostramos comos como usar backtracking para reslver vários problemas diferentes, incluindo pintar um grafo, resolver o problema das n-rainhas de , que consiste em posicionar n rainhas em um tabuleiro de xadrez nXn de maneira que uma rainha não possa atacar a outra, e também o problema do subconjunto da soma, que consiste em visa encontrar um subconjunto de um conjunto de inteiros cuja soma é um inteiro dado inteiro.

O primeiro problemas problema que nós iremos atacar através de um procedure de backtracking é o de colorir um grafo usando n cores, onde sendo n é um inteiro positivo. Dado um grafo, nós tentaremos colorir ele usando n cores de uma maneira gananciosa. No entanto, quando nós atingimos uma coloração que não nos permite colorir um vértice adicional propriamente, nós usamos backtrack, mudando a cor de um vértice anteriormente colorido e tentando novamente. Aqui está o pseudocódigo para nosso procedure BackColor que executa essa coloração baseado em backtracking. Aqui nós ordenamos as cores como color1, color2, ..., colorn:

Outro problema que pode ser solucionado com uma solução elegante de backtracking é o problema de posicionar n-rainhas em um tabuleiro de xadrez de dimensão nXn de maneira que nenhuma rainha tem tenha como atacar a outra. Isso significa que nenhum par de rainhas pode ser posicionadona posicionado na mesma linha horizontal, vertical ou diagonal. Nós iremos resolver esse problema usando um procedure baseado em backtracking. Iremos posicionar as rainhas no tabuleiro de uma maneira gananciosa, até que todas as rainhas elas estejam posicionadas ou não haja mais posição disponível para um rainha ficar sem estar na mesma linha diagonal, vertical ou horizontal que outra já posicionada.