Dominância em grafos

Aproveitando a tarefa da matéria de estruturas de dados, o próximo post será voltado para o conceito de dominância de grafos. A atividade envolvia encontrar número mínimo de aldeias de emergência que seriam necessárias para cobrir todas as aldeias em situação de emergência. Na simplificação assumida, todas as aldeais que se conectam tem arestas com peso unitário e a distância de auxílio é apenas uma aresta. Assim, a resposta ideal então é o menor número possível de se colocar aldeias tal que todas aldeias são ou aldeias-resposta (prestadoras de auxílio) ou vizinhas a uma dessas.

Depois de pesquisar esse problema NP-Completo (que, portanto, não tem uma solução eficiente conhecida), chegamos a um algorítmo "ganansioso", que não promete a melhor resposta possível, mas é de O(n^2*m), onde n é o número de vértices e m, o número de arestas.

Segue o código de tal algorítmo, comentado.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

package greedyDSPcustom; /* Esse código procura o vértice com maior número de cidades vizinhas sem auxílio e o torna em ponto de emergência * O algoritmo continua criando pontos de emergência até não existirem mais cidades sem auxílio */ public class algorithm { public static int[][] g = { {0, 1, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 1, 0, 0, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 1, 0, 0}, {0, 1, 1, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0},}; public static int[] state = {0,0,0,0,0,0,0,0,0}; public static void main(String[] args) { int vertexMaxOrder = -1; while(!done()) { vertexMaxOrder = maxOrder(); state[vertexMaxOrder] = 2; //É ponto de emergência! Recebe auxílio por ser ponto de emergência for(int i=0; i<g[vertexMaxOrder].length; i++) { if(g[vertexMaxOrder][i] == 1 && state[i]==0) state[i] = 1;//É vizinho a um ponto de emergência, portanto recebe auxílio } } for(int i=0; i<state.length;i++) if(state[i]==2) System.out.println(i+1); } //Retorna o número de vizinhos sem auxílio para o vértice pedido public static int getOrder(int vertex) { int counter=0; for(int i=0; i<g[vertex].length;i++) if(g[vertex][i]==1 && state[i] == 0) counter++; return counter; } //Retorna o maior getOrder(vertex) dentre todos os vértices public static int maxOrder() { int max=-1; int vertex=-1; for(int i=0; i<g[0].length;i++) { if(getOrder(i)>max) { max = getOrder(i); vertex = i; } } return vertex; } //Retorna se o algoritmo deve acabar. A condição é não existir mais vértices sem auxílio (isto é, não serem pontos de emergência NEM vizinhos a um ponto de emergência) public static boolean done() { boolean done = true; for(int i=0; i<state.length;i++) if(state[i] == 0) done = false; return done; } }

O trabalho completo pode ser visto em https://goo.gl/Bg3HQf, inclusive com um método de força bruta desenvolvido pelo genial aluno Matheus Mattos Moller.