Trabalho sobre Grafo

Ver o tópico anterior Ver o tópico seguinte Ir em baixo

Trabalho sobre Grafo

Mensagem  Renancr em Dom 21 Nov 2010 - 18:40

GRAFO


Em matemática e ciência da computação, grafo é o objeto básico de estudo da teoria dos grafos. Tipicamente, um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por "setas".

Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Por exemplo, pode-se representar um mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais económico. Assim, os grafos podem possuir também pesos (ou custo), quer nas arestas quer nos vértices, e o custo total em estudo será calculado a partir destes pesos.

Grafos podem ser utilizados também em redes PERT no âmbito do planejamento de projetos. Neste caso, a cada aresta está associado o custo de execução, e as tarefas precedentes de uma outra serão suas afluentes.

Outro exemplo é o caso das redes de computadores, sendo cada terminal representado por um vértice, o cabo de rede pelas arestas e o custo associado a latência, por exemplo, ou o número de máquinas que a comunicação atravessa entre os nós. É nestes princípios que assenta todo o protocolo IP que torna possível a Internet ser uma realidade.

Grafos têm sido utilizados para representar o formalismo das redes complexas, onde o número de nós e de conexões entre esses nós é muito alto e complexamente estabelecido.

Introndução:

Uma possível definição para grafos: "O grafo propriamente dito é uma representação gráfica das relações existentes entre elementos de dados. Ele pode ser descrito num espaço euclidiano de n dimensões como sendo um conjunto V de vértices e um conjunto A de curvas contínuas (arestas)". Podemos avaliar um grafo através de seu tipo, propriedades e aplicações.

Busca em grafo:

Vários problemas representados por um grafo podem ser resolvidos efetuando uma busca nesse grafo. A busca em grafo consiste em explorar um grafo, de forma que obtenha um processo sistemático de como caminhar por seus vértices e arestas. Às vezes é preciso visitar todos os vértices de um grafos, as vezes o problema pode ser resolvido visitando somente um subconjunto dos vértices.
Se o grafo é uma árvore, esta questão se torna simples, podem utilizar as visitas em pré-ordem, ou ordem de nível.

Algoritmos de percurso:

Existem dois métodos de percurso em grafos: percurso em profundidade (depth-first search — DFS) e o percurso em largura (breadth first search — BFS).
A idéia básica do DFS é buscar "mais a fundo" no grafo quando possível. Assim, a partir de um vértice v, as arestas ainda não exploradas o são e, ao final, a busca retrocede.
A idéia do BFS é bastante simples: os vértices do grafo são visitados nível a nível, ou seja, todos os vértices a uma distância k do vértice inicial são visitados antes de qualquer vértice a uma distância k +1 do inicial.

Fonte: [Você precisa estar registrado e conectado para ver este link.]

Faça um programa para representar um grafo de 6 vertices, com arestas determinada pelo usuário, representar em uma matriz 6X6.

1- Faça o calculo do vértice com maior grau, e mostrar para o usuário o(s) vértice(s) com o maior grau.
2- Faça o calculo da soma dos graus de todos os 6 vértices.
3- Imprima um possivel caminho Hamiltoniano.


EM TESTE

Código:
#include <iostream>
using namespace std;

const int tam=6;
const int tam2=2*tam;

int makegrafo(int matriz[tam][tam], int aresta[tam2]);
void mgdv(int matriz[tam][tam]);
void stgv(int matriz[tam][tam]);
void hamilton(int aresta[tam]);

void main()
{
   int matriz[tam][tam], aresta[tam2], op, made=0;

   do{
      do{
         system("cls");
         cout<< "==================================================================\n";
         cout<< "\t1- Criar Grafo\n";
         cout<< "\t2- Encontrar a vertice com maior grau\n";
         cout<< "\t3- Somar todos os graus dos vertices\n";
         cout<< "\t4- Encontar um possivel caminho Hamiltoniano\n";
         cout<< "\t5- Sair\n";
         cout<< "==================================================================\n";
         cout<< "\n\tDigite a opcao desejada\n\t";
         cin>> op;
         if(op < 1 || op > 5)
         {
            system("cls");
            cout<< "\n\n\tOpcao invalida\n\n\n";
            system("pause");
         }
      }while(op < 1 || op > 5);
      if(op == 1)
      {
         made=makegrafo(matriz, aresta);
      }
      else
         if(op == 2)
         {
            if(made == 1)
               mgdv(matriz);
            else
            {
               system("cls");
               cout<< "\n\n\n\tNem um GRAFO foi criado ainda.\n\n\n";
               system("pause");
            }
         }
         else
            if(op == 3)
            {
               if(made == 1)
                  stgv(matriz);
               else
               {
                  system("cls");
                  cout<< "\n\n\n\tNem um GRAFO foi criado ainda.\n\n\n";
                  system("pause");
               }
            }
            else
               if(op == 4)
               {
                  if(made == 1)
                     hamilton(aresta);
                  else
                  {
                     system("cls");
                     cout<< "\n\n\n\tNem um GRAFO foi criado ainda.\n\n\n";
                     system("pause");
                  }
               }
   }while(op != 5);
}

int makegrafo(int matriz[tam][tam], int aresta[tam2])
{
   int vert, arest, l, c, cont=1, i, found;
   for(l=0; l<tam; l++)
      for(c=0; c<tam; c++)
         matriz[l][c]=0;
   for(l=0; l < tam2; l++)
   {
      do{
         system("cls");
         found=0;
         if(l > 0)
         {
            cout<< "Aresta = { ";
            for(c=0; c<l; c++)
            {
               if(c % 2 != 0)
               {
                  cout<< aresta[c] << "} ";
               }
               else
               {
                  cout<< "{" << aresta[c] << ",";
               }
            }
            cout<< " }";
         }
         cout<< "\n\nDigite um conjunto par de numeros de 1 ate 6 nao repetindo os pares\n\n";
         if(l % 2 == 0)
         {
            do{
               cout<< "\n\tDigite o primeiro numero do conjunto\n\t";
               cin>> aresta[l];
               if(aresta[l] < 1 || aresta[l] > 6)
               {
                  system("cls");
                  cout<< "\n\n\n\nO valor digitado nao poder ser menor do que 1 e maior do que 6\n\n\n";
                  system("pause");
                  system("cls");
                  if(l > 0)
                  {
                     cout<< "Aresta = { ";
                     for(c=0; c<l; c++)
                     {
                        if(c % 2 != 0)
                        {
                           cout<< aresta[c] << "} ";
                        }
                        else
                        {
                           cout<< "{" << aresta[c] << ",";
                        }
                     }
                     cout<< " }";
                  }
               }
            }while(aresta[l] < 1 || aresta[l] > 6);
         }
         else
         {
            do{
               cout<< "\n\tDigite o segundo numero do conjunto\n\t";
               cin>> aresta[l];
               if((aresta[l] < 1 || aresta[l] > 6) || (aresta[l] == aresta[l-1]))
               {
                  system("cls");
                  cout<< "\n\n\n\nO valor digitado nao poder ser menor do que 1 e maior do que 6, e nem repetido.\n\n\n";
                  system("pause");
                  system("cls");
                  if(l > 0)
                  {
                     cout<< "Aresta = { ";
                     for(c=0; c<l; c++)
                     {
                        if(c % 2 != 0)
                        {
                           cout<< aresta[c] << "} ";
                        }
                        else
                        {
                           cout<< "{" << aresta[c] << ",";
                        }
                     }
                     cout<< " }";
                  }
               }
            }while((aresta[l] < 1 || aresta[l] > 6) || (aresta[l] == aresta[l-1]));
            i=1;
            while(i < cont && found == 0)
            {
               if((aresta[i-1] == aresta[l-1] && aresta[i] == aresta[l]) || (aresta[i-1] == aresta[l] && aresta[i] == aresta[l-1]))
                  found=1;
               i+=2;
            }
         }
         if((found == 0) && (l % 2 != 0))
            cont+=2;
         else
            if((found == 1) && (l % 2 != 0))
            {
               system("cls");
               cout<< "O conjunto {" << aresta[l-1] << ", " << aresta[l] << "} ja existe, digite um diferente.\n\n";
               l--;
               system("pause");
            }
      }while(found == 1);
   }
   /*system("cls");
   cout<< "Aresta = { ";
   for(c=0; c<tam2; c++)
   {
      if(c % 2 != 0)
      {
         cout<< aresta[c] << "} ";
      }
      else
      {
         cout<< "{" << aresta[c] << ",";
      }
   }
   cout<< " }";
   cout<< "\n\n\n";
   for(l=0; l<tam; l++)
   {
      for(c=0; c<tam; c++)
         cout<< matriz[l][c] << " ";
      cout<< "\n";
   }*/
   for(vert=0; vert<tam; vert++)
   {
      for(arest=0; arest<tam; arest++)
      {
         for(l=1; l < tam2; l+=2)
            if(vert+1 == aresta[l-1] && arest+1 == aresta[l])
               matriz[vert][arest]= 1;
      }
   }
   /*cout<< "\n\n\n";
   for(l=0; l<tam; l++)
   {
      for(c=0; c<tam; c++)
         cout<< matriz[l][c] << " ";
      cout<< "\n";
   }
   system("pause");*/
   return 1;
}

void mgdv(int matriz[tam][tam])
{
   int l, c, vertice[tam], grau=0;
   system("cls");
   for(l=0; l<tam; l++)
      vertice[l]=0;

   for(l=0; l<tam; l++)
      for(c=0; c<tam; c++)
         if(matriz[l][c] == 1)
            vertice[l]++;

   for(l=0; l<tam; l++)
      if(vertice[l] > grau)
         grau=vertice[l];
   cout<< "\t1\t2\t3\t4\t5\t6\n\n";
   for(l=0; l<tam; l++)
   {
      cout<< l+1<< "\t";
      for(c=0; c<tam; c++)
         cout<< matriz[l][c] << "\t";
      cout<< "\tGrau: " << vertice[l] << "\n";
   }
   cout<< "\n\n\n";
   for(l=0; l<tam; l++)
      if(vertice[l] == grau)
         cout<< "O(s) vertice(s) " << l+1 << " possui o maior grau encontrado: Grau " << grau << "\n";
   cout<< "\n\n";
   system("pause");
}

void stgv(int matriz[tam][tam])
{
   int l, c, vertice[tam], somador=0;
   system("cls");
   for(l=0; l<tam; l++)
      vertice[l]=0;

   for(l=0; l<tam; l++)
      for(c=0; c<tam; c++)
         if(matriz[l][c] == 1)
            vertice[l]++;

   for(l=0; l<tam; l++)
   {
      somador+=vertice[l];
   }

   cout<< "\t1\t2\t3\t4\t5\t6\n\n";
   for(l=0; l<tam; l++)
   {
      cout<< l+1<< "\t";
      for(c=0; c<tam; c++)
         cout<< matriz[l][c] << "\t";
      cout<< "\tGrau: " << vertice[l] << "\n";
   }
   cout<< "\n\n\n";

   cout<< "A soma de todo os graus e :" << somador << "\n";

   cout<< "\n\n";
   system("pause");
}

void hamilton(int aresta[tam])
{
   int l, cont[tam2], control, start, end, get, found;
   do{
      system("cls");
      cout<< "\tEscolha o ponto de partida\n\t";
      cin>> start;
      if(start < 1 || start > 6)
      {
         system("cls");
         cout<< "\n\tO valor da vertice nao pode ser menor do que 1 e maior do que 6\n\n";
         system("pause");
      }
   }while(start < 1 || start > 6);
   do{
      cout<< "\n\tEscolha o ponto onde quer chegar\n\t";
      cin>> end;
      if((start < 1 || start > 6))
      {
         system("cls");
         cout<< "\n\tO valor da vertice nao pode sermanor do que 1 e maior do que 6\n\n";
         system("pause");
      }
      else
         if(start == end)
         {
            system("cls");
            cout<< "\n\tO valor do fim nao pode ser igual ao do inicio\n\n";
            system("pause");
         }
   }while((start < 1 || start > 6) || (start == end));

   for(l=0; l < tam2; l++)
      cont[l]=0;

   found=0;
   get=0;
   control=0;
   l=0;

   while(l < tam2 || get != end)
   {
      if(get != 0 && aresta[l] == get)
      {
            cont[control] = aresta[l];
            control++;
            get = aresta[l+1];
            if(get == end)
            {
               found=1;
               cont[control] = aresta[l+1];
               control++;
            }
      }
      else
         if(get == 0 && aresta[l] == start)
         {
            cont[control] = aresta[l];
            control++;
            get = aresta[l+1];
            if(get == end)
            {
               found=1;
               cont[control] = aresta[l+1];
               control++;
            }
         }
      if(l+1 == tam2 && found == 0)
         l=0;
      else
         l+=2;
   }

   cout<< "Aresta = { ";

   for(l=0; l<tam2; l++)
   {
      if(l % 2 != 0)
      {
         cout<< aresta[l] << "} ";
      }
      else
      {
         cout<< "{" << aresta[l] << ",";
      }
   }
   cout<< " }";

   cout<< "\n\n\n";

   cout<< "Hamilton = { ";
   l=0;
   while(l<tam2 && cont[l] != 0)
   {
      if(l+1 == tam2)
         cout<< cont[l];
      else
         cout<< cont[l] << ", ";
   }
   cout<< " }";

   system("pause");
}
avatar
Renancr

Mensagens : 118
Data de inscrição : 08/03/2010

Ver perfil do usuário

Voltar ao Topo Ir em baixo

Ver o tópico anterior Ver o tópico seguinte Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum