Trabalho sobre Grafo
Binary Road :: Lógica Computacional :: Introdução à Programação Lógica :: Linguagens Formais e Autômatos :: Matemática discreta :: Estudo
Página 1 de 1
Trabalho sobre Grafo
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: Wikipédia
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");
}
Renancr- Mensagens : 118
Data de inscrição : 08/03/2010
Tópicos semelhantes
» Trab 22/04/10
» Trabalho numeros Primos no intervalo
» Trabalho com matrizes
» Trabalho de Lista Dinâmica
» Trabalho inversa de uma matriz
» Trabalho numeros Primos no intervalo
» Trabalho com matrizes
» Trabalho de Lista Dinâmica
» Trabalho inversa de uma matriz
Binary Road :: Lógica Computacional :: Introdução à Programação Lógica :: Linguagens Formais e Autômatos :: Matemática discreta :: Estudo
Página 1 de 1
Permissões neste sub-fórum
Não podes responder a tópicos