Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
Algorítmos/bfs_dinamico_concluído.cpp #include<iostream> #include<vector> #include<queue> #include<map> #include<stdio.h> #include<stdlib.h> #define WHITE 0 #define CRAY 1 #define BLACK 2 #define INFINITE 214748367 using namespace std; vector<int>distancia(101); typedef struct lista *Lista; struct lista{ int vertice; struct lista *proximo; struct lista *anterior; }; typedef struct nodo Nodo; struct nodo{ int vertice; Lista adjacents; }; typedef struct digrafo Digrafo; struct digrafo{ int numeroDeVertices; int numeroDeArcos; vector<Nodo>listaAdj; }; Lista inicio = NULL; int buscaLinear(Digrafo G, int vertice){ int i = 0; while(i < G.numeroDeVertices && G.listaAdj[i].vertice != vertice) i++; if(i == G.numeroDeVertices ) return -1; return i; } //cria um grafo Digrafo initDigrafo(){ Digrafo G; vector<Nodo>lista; G.numeroDeVertices = 0; G.numeroDeArcos = 0; G.listaAdj = lista; return G; } void printDigrafo(Digrafo G){ printf("Numero de Vertices : %d\n",G.numeroDeVertices); printf("Numero de Arcos : %d\n",G.numeroDeArcos); for(int i= 0; i < G.numeroDeVertices ; i++){ Lista aux; aux = G.listaAdj[i].adjacents; printf("\nVertice %d\n",G.listaAdj[i].vertice); if(aux != NULL) { while(aux->anterior != NULL) aux = aux->anterior; while(aux != NULL){ printf(" [%d]",aux->vertice); aux= aux->proximo; } } else printf("A lista esta vazia"); } } Digrafo insertVertice(Digrafo G, int vertice){ Nodo nodoNovo; nodoNovo.adjacents = NULL; nodoNovo.vertice = vertice; if(buscaLinear(G,vertice)!= -1) return G; G.listaAdj.push_back(nodoNovo); G.numeroDeVertices += 1; return G; } //retorna 1 para verdadeiro Digrafo insertArc(Digrafo G, int verticeA, int verticeVizinho){ Lista vizinho=(Lista)malloc(sizeof(Lista)); vizinho->vertice = verticeVizinho; vizinho->proximo = NULL; vizinho->anterior = NULL; for(int i= 0 ; i < G.numeroDeVertices ; i++){ if(G.listaAdj[i].vertice == verticeA){ while(G.listaAdj[i].adjacents != NULL && G.listaAdj[i].adjacents->anterior != NULL){ G.listaAdj[i].adjacents = G.listaAdj[i].adjacents->anterior; } while(G.listaAdj[i].adjacents != NULL && G.listaAdj[i].adjacents->proximo != NULL && G.listaAdj[i].adjacents->vertice != verticeVizinho){ G.listaAdj[i].adjacents = G.listaAdj[i].adjacents->proximo; } if(G.listaAdj[i].adjacents == NULL){ G.listaAdj[i].adjacents = vizinho; return G; } else if(G.listaAdj[i].adjacents->proximo == NULL){ vizinho->anterior = G.listaAdj[i].adjacents; G.listaAdj[i].adjacents->proximo = vizinho; G.listaAdj[i].adjacents = G.listaAdj[i].adjacents->proximo; G.numeroDeArcos += 1; return G; }else return G; } } return G; } Digrafo insertArco(Digrafo G, int verticeA, int verticeB){ G=insertArc(G,verticeA,verticeB); G=insertArc(G,verticeB,verticeA); return G; } void BFS(Digrafo G, int inicio){ vector<int>cores(G.numeroDeVertices); queue<int>fila; map<int,int>lvertices; int s; int u; int buscaU; int busca; //pinta vertices de branco for(int i = 0 ; i < G.numeroDeVertices ; i++){ cores[i] = WHITE; distancia[i] = INFINITE; lvertices[G.listaAdj[i].vertice] = i; if(inicio == G.listaAdj[i].vertice) s=i; } distancia[lvertices[inicio]] = 0; cores[s] = CRAY; fila.push(inicio); while(fila.empty() != true){ //int tamanho; Lista aux; u = fila.front(); fila.pop(); buscaU = lvertices[u];//busca o indice na lista aux = G.listaAdj[buscaU].adjacents; while(aux->anterior != NULL) aux = aux->anterior; for(Lista aux2 = aux; aux2 != NULL ; aux2 = aux2->proximo){ int v = aux2->vertice; busca = lvertices[v]; if (busca != -1 && cores[busca] == WHITE){ distancia[busca] = distancia[buscaU]+1; cores[busca] = CRAY; fila.push(v); } } cores[buscaU] = BLACK; } } int main(){ Digrafo G = initDigrafo();; G=insertVertice(G,1); G=insertVertice(G,2); G=insertArco(G,1,2); printDigrafo(G); return 0; } __MACOSX/Algorítmos/._bfs_dinamico_concluído.cpp ��������Mac OS X ����� ���2���r�������¤��������������������������������������ATTR�������¤���������������������������������� Mac_Metadata�õ�����������ÿ�ÿÿ���� Algorítmos/BFS_ESTATICO.cpp /** * BFS * ESTÁTICO * MESMAS CARACTERISTICAS DE IMPLEMENTAÇÃO DE DIJKSTRA * FUNCIONA PARA GRAFOS DIRIGIDOS * */ #include<iostream> #include<stack> #include<queue> #include<string.h> #define MAX 100 #define WHITE 0 #define CRAY 1 #define BLACK 2 #define CONECTADO 1 using namespace std; int G[MAX][MAX]; int cor[MAX]; int V, E; int distancias[MAX]; int predecessor[MAX]; void bfs(int s) { int i, node; queue<int> myStack; memset(cor, WHITE, sizeof(cor)); memset(distancias, 0, sizeof(distancias)); memset(predecessor, 0, sizeof(predecessor)); //inicia a distancia distancias[s] = 0; myStack.push(s); while(!myStack.empty()) { node = myStack.back(); myStack.pop(); for(i=0; i<= V; i++){ if(G[node][i]==CONECTADO){ //pinta vertice adjacente ao vertice nodo //caso nao tenha lido if(cor[i]==WHITE){ cor[i] = CRAY; predecessor[i] =node; distancias[i] += distancias[node] + 1; myStack.push(i); } } } cor[node] = BLACK; } } int main() { memset(cor, WHITE, sizeof(cor)); V = 10; E = 6; G[1][2] = CONECTADO; G[2][5] = CONECTADO; G[7][4] = CONECTADO; G[7][2] = CONECTADO; G[4][6] = CONECTADO; G[3][4] = CONECTADO; G[8][9] = CONECTADO; bfs(3); cout<<"distancia de 1 a :"<<endl; for(int i = 0 ; i <= V ; i++) cout<<i<<" : "<<distancias[i]<<"predecessor : "<<predecessor[i]<<endl; system("pause"); return 0; } __MACOSX/Algorítmos/._BFS_ESTATICO.cpp ��������Mac OS X ����� ���2���r�������¤��������������������������������������ATTR�������¤���������������������������������� Mac_Metadata�õ�����������ÿ�ÿÿ���� Algorítmos/DFS_ESTATICO.cpp #include<iostream> #include<queue> #define MAX 100 #define WHITE 0 #define CRAY 1 #define BLACK 2 #define CONECTADO 1 using namespace std; int G[MAX][MAX]; int tempoDecorrido[MAX][2]; int V, E; int cores[MAX]; int timeT = 1; int predecessor[MAX]; bool visitaDFS(int v, int u){ cores[v] = CRAY; timeT += 1; tempoDecorrido[v][0] = timeT; cout<<"visitaDFS("<<v<<") : "<<tempoDecorrido[v][0]<<"/?"<<endl; for(int i = 1 ; i < V ; i++){ //cout<<v<<" : "<<i<<" "<<G[v][i]<<"cores "<<cores[i]<<endl; if(i == v) return true; if(G[v][i] == CONECTADO && cores[i] == WHITE){ predecessor[i] = v; visitaDFS(i,u); } } cores[v]= BLACK; timeT += 1; tempoDecorrido[v][1] = timeT; cout<<"return visitaDFS("<<v<<") : "<<tempoDecorrido[v][0]<<"/"<<tempoDecorrido[v][1]<<endl; return false; } bool dfs(int s, int u) { int i, j, node; memset(cores, WHITE, sizeof(cores)); cores[s] = CRAY; tempoDecorrido[s][0] = 1; for(i=1; i<V; i++){ cout<<i<<endl; if(G[s][i] == CONECTADO && cores[i] == WHITE){ predecessor[i] = s; if(visitaDFS(i,u)) return true; } cout<<"desconectou"<<endl; } tempoDecorrido[s][1] = timeT+1; return false; } int main() { V=7; G[0][1] = CONECTADO; G[1][0] = CONECTADO; G[1][2] = CONECTADO; G[2][1] = CONECTADO; G[3][4] = CONECTADO; G[4][3] = CONECTADO; G[5][6] = CONECTADO; G[6][5] = CONECTADO; cout<<dfs(0,6); for(int i = 1 ; i <= V ; i++) { cout<<i<<" : "<<tempoDecorrido[i][0]<<"/"<<tempoDecorrido[i][1]; cout<<" "<<predecessor[i]<<endl; } system("pause"); return 0; } __MACOSX/Algorítmos/._DFS_ESTATICO.cpp ��������Mac OS X ����� ���2���r�������¤��������������������������������������ATTR�������¤���������������������������������� Mac_Metadata�õ�����������ÿ�ÿÿ���� Algorítmos/DINIC_TESTADO.cpp /** * ////////////////// * // MAXIMUM FLOW // * ////////////////// * * This file is part of my library of algorithms found here: * http://shygypsy.com/tools/ * LICENSE: * http://shygypsy.com/tools/LICENSE.html * Copyright (c) 2006 * Contact author: * abednego at gmail.c0m **/ /**************** * Maximum flow * (Dinic's on an adjacency list + matrix) **************** * Takes a weighted directed graph of edge capacities as an adjacency * matrix 'cap' and returns the maximum flow from s to t. * * PARAMETERS: * - cap (global): adjacency matrix where cap[u][v] is the capacity * of the edge u->v. cap[u][v] is 0 for non-existent edges. * - n: the number of vertices ([0, n-1] are considered as vertices). * - s: source vertex. * - t: sink. * RETURNS: * - the flow * - prev contains the minimum cut. If prev[v] == -1, then v is not * reachable from s; otherwise, it is reachable. * RUNNING TIME: * - O(n^3) * FIELD TESTING: * - Valladolid 10330: Power Transmission (Gives WA, but it's probably my graph building that's wrong) * - Valladolid 563: Crimewave * - Valladolid 753: A Plug for UNIX * - Valladolid 10511: Councilling * - Valladolid 820: Internet Bandwidth * - Valladolid 10779: Collector's Problem * #include <string.h> **/ #include <string.h> #include <stdio.h> #include <stdlib.h> // the maximum number of vertices #define NN 1024 // adjacency matrix (fill this up) // If you fill adj[][] yourself, make sure to include both u->v and v->u. int cap[NN][NN], deg[NN], adj[NN][NN]; // BFS stuff int q[NN], prev[NN]; void printPrev(int n); int dinic( int n, int s, int t ) { int flow = 0; while( true ) { // find an augmenting path memset( prev, -1, sizeof( prev ) ); int qf = 0, qb = 0; prev[q[qb++] = s] = -2; while( qb > qf && prev[t] == -1 ){ for( int u = q[qf++], i = 0, v; i < deg[u]; i++ ){ if( prev[v = adj[u][i]] == -1 && cap[u][v] ) prev[q[qb++] = v] = u; //q[qb] = v; //prev[q[qb]] = u; //qb += 1; } } // see if we're done if( prev[t] == -1 ) break; // try finding more paths for( int z = 0; z < n; z++ ) if( cap[z][t] && prev[z] != -1 ) { int bot = cap[z][t]; for( int v = z, u = prev[v]; u >= 0; v = u, u = prev[v] ) bot <?= cap[u][v];//se cap[u][v] e menor que bot entao armazene if( !bot ) continue; cap[z][t] -= bot; cap[t][z] += bot; for( int v = z, u = prev[v]; u >= 0; v = u, u = prev[v] ) { cap[u][v] -= bot; cap[v][u] += bot; } flow += bot; } } return flow; } //----------------- EXAMPLE USAGE ----------------- int main() { // read a graph into cap[][] memset( cap, 0, sizeof( cap ) ); int nodes, sink, t, m; scanf( " %d %d %d %d", &nodes, &sink, &t, &m ); while( m-- ) { int u, v, c; scanf( " %d %d %d", &u, &v, &c ); cap[u][v] = c; } memset( deg, 0, sizeof( deg ) ); //inicia a lista de adjacencia //deg = tamanho da lista do vertice x for( int u = 0; u < nodes; u++ ) for( int v = 0; v < nodes; v++ ) // se pelo menos um dos dois valores for diferente de zero if( cap[u][v] || cap[v][u] ) adj[u][deg[u]++] = v; printf( "%d\n", dinic( nodes, sink, t ) ); system("pause"); return 0; } __MACOSX/Algorítmos/._DINIC_TESTADO.cpp ��������Mac OS X ����� ���2���r�������¤��������������������������������������ATTR�������¤���������������������������������� Mac_Metadata�õ�����������ÿ�ÿÿ���� Algorítmos/FORD_FULKERSON_TESTADO.cpp /** * ////////////////// * // MAXIMUM FLOW // * ////////////////// * * This file is part of my library of algorithms found here: * http://www.palmcommander.com:8081/tools/ * LICENSE: * http://www.palmcommander.com:8081/tools/LICENSE.html * Copyright (c) 2004 * Contact author: * igor at cs.ubc.ca **/ /**************** * Maximum flow * (Ford-Fulkerson on an adjacency matrix) **************** * Takes a weighted directed graph of edge capacities as an adjacency * matrix 'cap' and returns the maximum flow from s to t. * * PARAMETERS: * - cap (global): adjacency matrix where cap[u][v] is the capacity * of the edge u->v. cap[u][v] is 0 for non-existent edges. * - n: the number of vertices ([0, n-1] are considered as vertices). * - s: source vertex. * - t: sink. * RETURNS: * - the flow * - fnet contains the flow network. Careful: both fnet[u][v] and * fnet[v][u] could be positive. Take the difference. * - prev contains the minimum cut. If prev[v] == -1, then v is not * reachable from s; otherwise, it is reachable. * DETAILS: * FIELD TESTING: * - Valladolid 10330: Power Transmission * - Valladolid 653: Crimewave * - Valladolid 753: A Plug for UNIX * - Valladolid 10511: Councilling * - Valladolid 820: Internet Bandwidth * - Valladolid 10779: Collector's Problem * #include <string.h> * #include <queue> **/ #include <string.h> #include <stdio.h> #include <stdlib.h> // the maximum number of vertices #define NN 1024 // adjacency matrix (fill this up) int cap[NN][NN]; // flow network int fnet[NN][NN]; // BFS int q[NN], qf, qb, prev[NN]; int fordFulkerson( int n, int s, int t ) { // init the flow network memset( fnet, 0, sizeof( fnet ) ); int flow = 0; while( true ) { // find an augmenting path memset( prev, -1, sizeof( prev ) ); qf = qb = 0; prev[q[qb++] = s] = -2; while( qb > qf && prev[t] == -1 ) for( int u = q[qf++], v = 0; v < n; v++ ) if( prev[v] == -1 && fnet[u][v] - fnet[v][u] < cap[u][v] ) prev[q[qb++] = v] = u; // see if we're done if( prev[t] == -1 ) break; // get the bottleneck capacity int bot = 0x7FFFFFFF; for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] ) bot <?= cap[u][v] - fnet[u][v] + fnet[v][u]; // update the flow network for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] ) fnet[u][v] += bot; flow += bot; } return flow; } //----------------- EXAMPLE USAGE ----------------- int main() { memset( cap, 0, sizeof( cap ) ); int nodes, sink, t, m; scanf(" %d %d %d %d", &nodes, &sink, &t, &m ); while( m-- ) { int u, v, c; scanf( " %d %d %d", &u, &v, &c ); cap[u][v] = c; } // ... fill up cap with existing edges. // if the edge u->v has capacity 6, set cap[u][v] = 6. printf("%d",fordFulkerson( nodes, sink, t )); system("pause"); return 0; } __MACOSX/Algorítmos/._FORD_FULKERSON_TESTADO.cpp ��������Mac OS X ����� ���2���r�������¤��������������������������������������ATTR�������¤���������������������������������� Mac_Metadata�õ�����������ÿ�ÿÿ���� Algorítmos/Implementação - bellman-ford-floyd-warshall.pdf Algoritmo de Bellman-Ford É um pouco mais lento que dijkstra, mas é mais simples e fácil de compreender e permite pesos negativos nas arestas, enquanto que dijkstra não permite. #include <iostream> #define INFINITY 99999999 using namespace std; typedef struct { int source; int dest; int weight; } Edge; // Arestas void BellmanFord(Edge edges[], int edgecount, int nodecount, int source) { int i,j; int *distance = new int [nodecount]; for (i = 0; i < nodecount; i++) { distance[i] = INFINITY; } distance[source] = 0; for (i = 0; i < nodecount; i++) { // como otimizar este laço? for (j = 0; j < edgecount; j++) { if (distance[edges[j].dest] > distance[edges[j].source] + edges[j].weight) { distance[edges[j].dest] = distance[edges[j].source] + edges[j].weight; } } } for (i = 0; i < edgecount; i++) { if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) { cout << "Ciclo negativo de pesos de arestas detectado" << endl; break; } } for (i = 0; i < nodecount; i++) { cout << "Distancia menor entre nodos " << source << " e " << i <<" eh " << distance[i] << endl; } delete distance; } int main (void){ Edge Arestas[100]; int casos,nc,vertices,arestas; cin >> casos; for (nc = 0; nc < casos; nc ++){ cin >> vertices; //m cin >> arestas; for (int i=0; i< arestas; i++){ cin >> Arestas[i].source; cin >> Arestas[i].dest; cin >> Arestas[i].weight; } BellmanFord(Arestas,arestas,vertices,0); //Arestas,n de arestas,n de vertices,origem); cout << endl; } return(0); } Entrada: 2 3 3 0 1 1000 1 2 15 2 1 -42 4 4 0 1 10 1 2 20 2 3 30 3 0 -60 Saída: Ciclo negativo de pesos de arestas detectado A distancia mais curta entre os nodos 0 e 0 eh 0 A distancia mais curta entre os nodos 0 e 1 eh 919 A distancia mais curta entre os nodos 0 e 2 eh 961 A distancia mais curta entre os nodos 0 e 0 eh 0 A distancia mais curta entre os nodos 0 e 1 eh 10 A distancia mais curta entre os nodos 0 e 2 eh 30 A distancia mais curta entre os nodos 0 e 3 eh 60 Análise do algoritmo Edge Arestas[100]; typedef struct { int source; int dest; int weight; } Edge; // Arestas Arestas[ ] source dest weight 0 0 1 31 1 0 4 78 2 1 2 12 3 1 3 8 4 2 0 -5 5 2 3 124 6 3 4 61 7 3 6 13 8 4 0 78 9 4 5 14 10 5 1 -3 11 6 4 4 i distance[i] 0 1 2 3 4 5 6 distance [ ] 0 α α α α α α Pega campo dest do vetor de Arestas (arestas[] .dest) (distance[1] > distance[0] + 31) ? α > 0 + 31 ? (sim) distance[1] = 31 0 1 2 3 4 5 6 distance [ ] 0 31 α α α α α (distance[4] > distance[0] + 78) ? α > 0 + 31 ? (sim) distance[4] = 78 0 1 2 3 4 5 6 distance [ ] 0 31 α α 78 α α (distance[2] > distance[1] + 12) ? α > 31 12 distance[2]= 43 ... 0 1 2 3 4 5 6 distance [ ] 0 31 43 39 56 70 52 A distancia mais curta entre os nodos 0 e 0 eh 0 A distancia mais curta entre os nodos 0 e 1 eh 31 A distancia mais curta entre os nodos 0 e 2 eh 43 A distancia mais curta entre os nodos 0 e 3 eh 39 A distancia mais curta entre os nodos 0 e 4 eh 56 A distancia mais curta entre os nodos 0 e 5 eh 70 A distancia mais curta entre os nodos 0 e 6 eh 52 1 5 2 4 6 31 14 -3 4 13 61 124 -5 8 12 78 0 3 Problemas envolvendo Bellman-Ford UVA 11492 - Babel – Facilitado (ignore restrições) sub-regional Brasil de 20 de setembro de 2008 - Problema B Joaozinho e Mariazinha são dois irmãos que estão muito empolgados com suas aulas de idiomas, cada um está fazendo vários diferentes cursinhos. Ao chegar em casa comentam sobre gramática, vocabulário, cultura dos países etc. Numa dessas conversas perceberam que algumas palavras são comuns a mais de um idioma, mesmo que não necessariamente tenham o mesmo significado. Por exemplo, “amigo” existe em português e espanhol e tem o mesmo significado, enquanto que “date” é uma palavra comum entre francês e inglês mas que pode ter significados diferentes, uma vez que “date” também se refere a um encontro em inglês, além de “data” de calendário. Já “red” em espanhol se refere a uma rede, enquanto que em inglês se refere à corvermelha. Outro exemplo seria “actual” que, em inglês significa algo real e, em espanhol, tem o significado de presente, atual (como em português). Empolgados com essas descobertas, resolveram escrever num caderno todas as palavras em comum que conseguiram pensar, associando cada uma a um par de idiomas. Observador como é, Joãozinho propôs um desafio a Mariazinha: dados um idioma de origem e um de destino, escrever uma série de palavras sendo que a primeira necessariamente deveria pertencer ao idioma de origem e a ´ultima ao de destino. Duas palavras adjacentes nessa seq¨uência deveriam necessariamente pertencer a um mesmo idioma. Por exemplo, se o idioma de origem fosse português e o de destino francês, Mariazinha poderia escrever a seq¨uência amigo actual date (português/espanhol, espanhol/inglês, inglês/francês). Restrições: Mariazinha deve encontrar a solução que tenha o menor comprimento da seqüência total não contando os espaços entre as palavras e duas palavras consecutivas não podem ter a mesma letra inicial. Sendo assim, a solução anterior passa a ser inválida, pois “amigo” e “actual” têm a mesma letra inicial. é possível, porém, encontrar outra solução, que no caso seria amigo red date, cujo comprimento total é 12. Joãozinho fez uma extensa pesquisa na internet e compilou uma enorme lista de palavras e desafiou Mariazinha a resolver o problema. Como é possível que haja mais de uma solução, ele pediu para que ela apenas respondesse o comprimento da seqüência encontrada dadas as restrições ou se não há solução possível. Você seria capaz de ajudar Mariazinha? Entrada A entrada contém vários casos de teste. A primeira linha de um caso de teste contém um inteiro M (1 <= M < 2000), representando o total de palavras compiladas por Joãozinho. A segunda linha contém duas cadeias de caracteres distintas O e D, separadas por um espaço em branco, indicando os idiomas de origem e destino respectivamente. Cada uma das M linhas seguintes contém três cadeias de caracteres I1, I2 e P, separadas por um espaço em branco, representando dois idiomas e uma palavra comum entre ambos (I1 e I2 são sempre diferentes). Todas as cadeias de caracteres terão tamanho mínimo 1 e máximo 50 e conterão apenas letras minúsculas. Um mesmo par de idiomas pode ter várias palavras diferentes associadas a ele, porém uma mesma palavra P nunca será repetida. O final da entrada é indicado por uma linha que contém apenas um zero. Saída Para cada caso de teste da entrada seu programa deve imprimir um único inteiro, o comprimento da menor seqüência que satisfaça as restrições de Joãozinho, ou impossivel (em minúsculas, sem acento) caso não seja possível. Exemplo de Entrada 4 portugues frances ingles espanhol red espanhol portugues amigo frances ingles date espanhol ingles actual 4 portugues alemao ingles espanhol red espanhol portugues amigo frances ingles date espanhol ingles actual 6 portugues frances ingles espanhol red espanhol portugues amigo frances ingles date frances espanhol la portugues ingles a espanhol ingles actual 0 Saída correspondente 12 impossivel 5 Resolução Inicialmente, deve-se entender a entrada como um grafo. Pense que as duas palavras iniciais são origem e destino e a palavra em comum entre as 2 línguas é a forma de transporte entre a origem e destino. O custo total de transporte ( distância ) entre a origem e o destino seria o tamanho da palavra em questão. Vamos supor que uma pessoa deseja ir de Gaurama até Cotegipe utilizando os meios de transporte disponíveis, escolhendo a rota cujo tamanho do meio em questão seja o menor possível. Exemplo: 5 gaurama cotegipe gaurama erechim onibus gaurama erechim van gaurama erechim carro erechim cotegipe onibusleito erechim cotegipe vanzinha 0 O principal aqui é fazer uma entrada de dados correta para grafos. Inicia-se com a leitura do vetor de arestas. Arestas[6002] source dest weight 0 0 2 onibus 1 2 0 onibus 2 0 2 van 3 2 0 van 4 0 2 carro 5 2 0 carro 6 2 1 onibusleito 7 1 2 onibusleito 8 2 1 vanzinha 9 1 2 vanzinha A chave agora é como converter os nomes para números na leitura para armazenar no vetor de arestas (Edge) int main (void){ Edge Arestas[6002]; int casos,nc,achou,cont,tamanhostring; string origem,destino; map <string,int> mapa; cin >> casos; while (casos!=0){ mapa.clear(); cin >>origem >> destino; mapa[origem]=0; mapa[destino]=1; tamanhostring=2; cont = 0; for (nc = 0; nc < casos; nc ++){ cin >> origem >> destino >> Arestas[cont].weight; Arestas[cont+1].weight = Arestas[cont].weight; if (mapa.find(origem)!=mapa.end()){ // encontrou achou = mapa[origem]; } else { mapa[destino]=tamanhostring; achou=tamanhostring++; } Arestas[cont].source= ... ... Arestas[6002] source dest weight 0 0 onibus 1 0 onibus Obs.: o uso de maps dá um ganho de 500 % em performance comparando com uma matriz de strings na qual teríamos que pesquisar a toda a matriz a cada entrada para ver se a cidade já existe ou não na matriz. On ib us gaurama erechim cotegipe va n ca rr o On ib us le it o va nz in ha 0 1 2 mapa["gaurama"] = 0; mapa["cotegipe"] = 1; gaurama erechim onibus achou = mapa[gaurama] = 0 UVA 558 - Wormholes In the year 2163, wormholes were discovered. A wormhole is a subspace tunnel through space and time connecting two star systems. Wormholes have a few peculiar properties: • Wormholes are one-way only. • The time it takes to travel through a wormhole is negligible. • A wormhole has two end points, each situated in a star system. • A star system may have more than one wormhole end point within its boundaries. • For some unknown reason, starting from our solar system, it is always possible to end up in any star system by following a sequence of wormholes (maybe Earth is the centre of the universe). • Between any pair of star systems, there is at most one wormhole in either direction. • There are no wormholes with both end points in the same star system. All wormholes have a constant time difference between their end points. For example, a specific wormhole may cause the person travelling through it to end up 15 years in the future. Another wormhole may cause the person to end up 42 years in the past. A brilliant physicist, living on earth, wants to use wormholes to study the Big Bang. Since warp drive has not been invented yet, it is not possible for her to travel from one star system to another one directly. This can be done using wormholes, of course. The scientist wants to reach a cycle of wormholes somewhere in the universe that causes her to end up in the past. By travelling along this cycle a lot of times, the scientist is able to go back as far in time as necessary to reach the beginning of the universe and see the Big Bang with her own eyes. Write a program to find out whether such a cycle exists. Input The input file starts with a line containing the number of cases c to be analysed. Each case starts with a line with two numbers n and m . These indicate the number of star systems (1 <=n<=1000) and the number of wormholes ( 1 <=m<=2000) . The star systems are numbered from 0 (our solar system) through n-1 . For each wormhole a line containing three integer numbers x, y and t is given. These numbers indicate that this wormhole allows someone to travel from the star system numbered x to the star system numbered y, thereby ending up t (-1000 <= t <= 1000) years in the future. Output The output consists of c lines, one line for each case, containing the word possible if it is indeed possible to go back in time indefinitely, or not possible if this is not possible with the given set of star systems and wormholes. Sample Input 2 3 3 0 1 1000 1 2 15 2 1 -42 4 4 0 1 10 1 2 20 2 3 30 3 0 -60 Sample Output possible not possible UVA 11090 - Going in Cycle!! You are given a weighted directed graph with n vertices and m edges. Each cycle in the graph has a weight, which equals to sum of its edges. There are so many cycles in the graph with different weights. In this problem we want to find a cycle with the minimum mean. Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with two numbers n and m. m lines follow, each has three positive number a, b, c which means there is an edge from vertex a to b with weight of c. Output For each test case output one line containing “Case #x: ” followed by a number that is the lowest mean cycle in graph with 2 digits after decimal place, if there is a cycle. Otherwise print “No cycle found.”. Constraints - n ≤ 50 - a, b ≤ n - c ≤ 10000000 Sample Input 5 2 1 1 2 1 2 2 1 2 2 2 1 3 3 4 1 2 12 2 1 -2 2 3 5 3 2 -6 4 5 1 2 5 2 3 2 3 1 6 3 4 3 4 3 -8 4 6 1 2 1 2 3 8 2 4 6 4 3 -1 3 2 2 3 1 6 Sample Output Case #1: No cycle found. Case #2: 2.50 Case #3: -0.50 Case #4: -2.50 Case #5: 2.33 UVA 515 - King Once, in one kingdom, there was a queen and that queen was expecting a baby. The queen prayed: ``If my child was a son and if only he was a sound king.'' After nine months her child was born, and indeed, she gave birth to a nice son. Unfortunately, as it used to happen in royal families, the son was a little retarded. After many years of study he was able just to add integer numbers and to compare whether the result is greater or less than a given integer number. In addition, the numbers had to be written in a sequence and he was able to sum just continuous subsequences of the sequence. The old king was very unhappy of his son. But he was ready to make everything to enable his son to govern the kingdom after his death. With regards to his son's skills he decided that every problem the king had to decide about had to be presented in a form of a finite sequence of integer numbers and the decision about it would be done by stating an integer constraint (i.e. an upper or lower limit) for the sum of that sequence. In this way there was at least some hope that his son would be able to make some decisions. After the old king died, the young king began to reign. But very soon, a lot of people became very unsatisfied with his decisions and decided to dethrone him. They tried to do it by proving that his decisions were wrong. Therefore some conspirators presented to the young king a set of problems that he had to decide about. The set of problems was in the form of subsequences of a sequence . The king thought a minute and then decided, i.e. he set for the sum of each subsequence Si an integer constraint ki (i.e or resp.) and declared these constraints as his decisions. After a while he realized that some of his decisions were wrong. He could not revoke the declared constraints but trying to save himself he decided to fake the sequence that he was given. He ordered to his advisors to find such a sequence S that would satisfy the constraints he set. Help the advisors of the king and write a program that decides whether such a sequence exists or not. Input The input file consists of blocks of lines. Each block except the last corresponds to one set of problems and king's decisions about them. In the first line of the block there are integers n, and m where 0 < n <=100 is length of the sequence S and 0 < m <=100 is the number of subsequences Si. Next m lines contain particular decisions coded in the form of quadruples si, ni, oi, ki, where oi represents operator > (coded as gt) or operator < (coded as lt) respectively. The symbols si, ni and ki have the meaning described above. The last block consists of just one line containing 0. Output The output file contains the lines corresponding to the blocks in the input file. A line contains text successful conspiracy when such a sequence does not exist. Otherwise it contains text lamentable kingdom. There is no line in the output file corresponding to the last ``null'' block of the input file. Sample Input 4 2 1 2 gt 0 2 2 lt 2 1 2 1 0 gt 0 1 0 lt 0 0 Sample Output lamentable kingdom successful conspiracy UVA 10702 – Traveling Salesman!! Jean is a travelling salesman. He keeps travelling among some cities. When he arrives in a city, he sells everything he has and buy new things. Then he travels to another city, sells his items and buy new ones. In this problem you will have to find the total amount of money Jean will gain on the optimal tour. On a tour he can go to some city more than once, and he must finish his tour in some cities. Also there is a starting city for his tour and the number of inter- city travels he wants to do in his tour. Input The input file contains several input sets. The description of each set is given below: Each set starts with four integers C (2 ≤ C ≤ 100), the number of cities, S (1 ≤ S ≤ 100), the identifier of the starting city, E (1 ≤ E ≤ 100), the number of cities his tour can end at, and T (1 ≤ T ≤ 1000), the number of inter-city travels he wants to do. Follow C lines with C non-negative integers. The j'th integer of the i'th line will describe the profit he earns when he goes from city i to city j. As he does not want to make a trip to a city he is already, the i'th integer of the i'th line will always be 0. Note that going from city i to city j can have a different profit than going from city j to city i. After there will be a line with E integers, the identifier of the cities he can end his tour. Input is terminated by a set where C=S=E=T=0. This set should not be processed. There is a blank line beteween two input sets. Output For each input set produce one line of output, the total profit he can earn in the corresponding tour. Sample Input 3 1 2 2 0 3 5 5 0 1 9 2 0 2 3 0 0 0 0 Sample Output 7 Algoritmo de Floyd - Warshall #include <iostream> #include <iomanip> #define INFINITO 999999999 using namespace std; /* A estrutura digraph representa um digrafo. O campo adj é um ponteiro para a matriz de adjacência do digrafo. O campo Vertices contém o número de Vértices e o campo A contém o número de arcos do digrafo. */ struct digraph { int V; int A; int adj[301][301]; }; /* Um objeto do tipo Digraph contém o endereço de um digraph. */ typedef struct digraph *Digraph; void Floyd (Digraph G) { for (int k=1; k <= G->V; k++) { for (int i=1; i <= G->V; i++) { for (int j=1; j <= G->V; j++){ if ( (G->adj[j][k]+G->adj[k][i] < G->adj[j][i]) ) { G->adj[j][i]=G->adj[j][k]+G->adj[k][i]; } } } } } int main(void){ Digraph D= new (struct digraph); int i, j, vertices, arestas, origem, destino, custo; cin >> vertices >> arestas; for (i=0; i<vertices+1; i++){ for (j=0; j<vertices+1; j++){ D->adj[i][j]=INFINITO; } } D->V=vertices; D->A=arestas; for (i=0; i<arestas; i++){ cin >> origem >> destino >> custo; D->adj[origem][destino]=custo; } Floyd (D); for (i=1;i<D->V+1;i++){ // Mostra a Matriz de Adjascencia for (j=1;j<D->V+1;j++) cout << setw(12) << D->adj[i][j] << " " ; cout << endl; } return(0); } floyd.in 4 7 1 3 5 3 1 4 1 2 8 2 1 10 2 4 12 4 2 6 3 4 3 UVA – 186 – Trip Routing Your employer, the California Car Club (CCC), has decided to provide a trip routing service to its members. Your job is to write a program which reads a list of departure point-destination point pairs and calculates the shortest routes between them. For each trip, your program will print a report which itemises the names of each city passed through, with route names and leg distances. Input Input to your program will be in two parts. The first part is a map in the form of a list of highway segments. Each segment is designated by a line containing four fields which are separated by commas. The first two fields are 1-20 characters each, and are the names of the cities which are at each end of the highway segment. The third field is the 1-10 character name of the route. The fourth field is the number of miles between the two endpoints, expressed as a positive integer. The highway segment list will be terminated by an empty line. The second part of the input is a list of departure point-destination point pairs, one per line. The departure point is given first, followed by a comma and the destination point. Each of the cities is guaranteed to have appeared in the first part of the input data, and there will be a path that connects them. The list is terminated by the end of file. Output The output should be a series of reports, one for each departure point-destination point pair in the input. Each report should be in exactly the same form as those in the example below. There should be two blank lines before each report (including the first one). Sample input San Luis Obispo,Bakersfield,CA-58,117 Bakersfield,Mojave,CA-58,65 Mojave,Barstow,CA-58,70 Barstow,Baker,I-15,62 Baker,Las Vegas,I-15,92 San Luis Obispo,Santa Barbara,US-101,106 San Luis Obispo,Santa Barbara,CA-1,113 Santa Barbara,Los Angeles,US-101,95 Bakersfield,Wheeler Ridge,CA-99,24 Wheeler Ridge,Los Angeles,I-5,88 Mojave,Los Angeles,CA-14,94 Los Angeles,San Bernardino,I-10,65 San Bernardino,Barstow,I-15,73 Los Angeles,San Diego,I-5,121 San Bernardino,San Diego,I-15,103 Santa Barbara,Las Vegas San Diego,Los Angeles San Luis Obispo,Los Angeles Sample output From To Route Miles -------------------- -------------------- ---------- ----- Santa Barbara Los Angeles US-101 95 Los Angeles San Bernardino I-10 65 San Bernardino Barstow I-15 73 Barstow Baker I-15 62 Baker Las Vegas I-15 92 ----- Total 387 From To Route Miles -------------------- -------------------- ---------- ----- San Diego Los Angeles I-5 121 ----- Total 121 From To Route Miles -------------------- -------------------- ---------- ----- San Luis Obispo Santa Barbara US-101 106 Santa Barbara Los Angeles US-101 95 ----- Total 201 Note: There will be no extraneous blanks in the input. There will be no more than 100 cities in the map and no more than 200 highway segments. The total distance in each best route is guaranteed to fit within a 16-bit integer. Input Output Sample Input Sample Output Input Output Constraints Sample Input Sample Output Input Output Sample Input Input Output Sample Input Sample Output Your employer, the California Car Club (CCC), has decided to provide a trip routing service to its members. Your job is to write a program which reads a list of departure point-destination point pairs and calculates the shortest routes between them. For each trip, your program will print a report which itemises the names of each city passed through, with route names and leg distances. Input Output Sample input __MACOSX/Algorítmos/._Implementação - bellman-ford-floyd-warshall.pdf Algorítmos/Optimization_EN_Ford-Belman_algorithm.pdf 10.3. Bellman-Ford Algorithm By: Snezhana Gocheva-Ilieva, snow@uni-plovdiv.bg Basic problem 2 An oriented graph is given containing no contours with negative length (equal to the sum of weights of their arcs). Find the minimal paths from a given node to all other nodes of the graph. This problem is a natural summary of the network planning problem. In this case minimal paths need to be found not only within a network, but also for a random path starting from a given node of the graph. One of the best-known algorithms for solving this dynamic optimization problem is Bellman-Ford’s. It uses output information from distances matrix R, introduced earlier in paragraph 10.1. First we will consider a simple example which demonstrates the idea of Bellman-Ford’s algorithm. Example 3. In fig. 5 is shown an oriented weighted graph with 4 nodes, containing 3 contours. Find the shortest distances from node 1 to all the other nodes. Fig. 5. Graph with 3 contours and its corresponding distances matrix. ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ ∞ ∞∞ ∞ = 033 5022 30 470 4 3 2 1 R 2 1 2 4 3 7 3 3 3 2 4 5 Solution. The variable Di stands for the sought minimal distance from node 1 to the i-th node. The solution goes through stages with and every stage includes a new node and the new value for Di is recalculated. This goes on until the resulting values can no longer get smaller. Variable k stands for the number of the stage. In the initial stage k = 1 all Di are equal to the direct distance from node 1 to the corresponding node. We have: k =1, Di = R1i, i.e. D1 = 0, D2 = 7, D3 = 4, D4 = ∞ . k =2, D1 = 0, D2 = min from D2 and the sums of the remaining Di with the distances from the i-th node to the second node (second column of the matrix). We have: D2 = min {7, 0+7, 4+2, ∞+3}= 6, (the minimum is underlined). Likewise for a minimum of D3 and the sums of the remaining Di with the third column of R: D3 = min { 4, 0+4, 7+3, ∞+3}= 4. Likewise for D4 we calculate: Аналогично D4 = min {∞ , 0+ , 7+ , ∞ ∞ 4+5}= 9. k = 3, D1 = 0, D2 = min {6, 0+7, 4+2, 9+3}= 6. D3 = min {4, 0+4, 6+3, 9+3}= 4. D4 = min {9, 0+ , 6+ , ∞ ∞ 4+5}= 9. We have reached a stage at which the results are the same as in the previous one and they can’t get better. Therefore we’ve reached the minimal distances that we sought. The calculations are written in the following table: k D1 D2 D3 D4 1 0 7 4 ∞ 2 0 6 4 9 3 0 6 4 9 The last row shows the minimal paths from 1 to every node. General case - formulas for Bellman-Ford’s algorithm for graph with n nodes For the sake of convenience we consider the node for which minimal distances are sought as number 1. k =1, Di = R1i, i = 1, 2, … , n. k =2, D1= 0, (1) D2 = min {D2, D1+R12, D3+R32, … , Dn+Rn2}, D3 = min {D3, D1+R13, D2+R23, … , Dn+Rn3}, ... Dn = min {Dn, D1+R1n, D2+R2n, … , Dn-1+Rn-1,n}. k =3, 4, ..., n-2. This procedure is repeated until we get two identical rows of distance in the table or until n-2 is reached in the worst case. Description of Bellman-Ford’s algorithm using metalanguage Let a given oriented weighted graph (V, E) with n nodes V and arcs E, which does not contain a contour with negative length. The aim is to find the minimal distances from node number p to all other nodes of the graph. The distances matrix R is given and the sought distances are recorded in an array D. The number of stages obviously does not exceed n-2. Incoming and outgoing operations have been skipped. begin for v∈V do D[v]:=R[p,v]; D[p]:=0; for k:=1 to n-2 do begin for v∈V \ {p} do for u∈V do D[v]:= min ( D[v], D[u] + R[p,v] ) end end The number of necessary arithmetical operations is O(n3). Example 4. Use Bellman-Ford’s method for finding the minimal distances from node 1 to all other nodes of the graph shown in fig. 6. 3 4 1 1 4 5 2 6 1 1 1 2 2 5 7 3 Fig. 6. Oriented graph with six contours. ⎥⎥ ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ ∞∞∞∞ ∞∞∞∞ ∞∞ ∞∞∞∞ ∞∞ ∞∞∞∞ = 01 03 4012 10 7250 10 6 5 4 3 2 1 R Solution: Using formulas (1) we write the results down in a table. In the formulas the case of a medial minimum has been underlined. k =1, D1= 0, D2 = R12 = 1, D3 = D4 = D5 = D6 =∞ . k =2, D1 = 0, D2 = min {D2, D1+R12, D3+R32, D4+R42, D5+R52, D6+R62} = min {1, 0+1, + , ∞ ∞ ∞+∞ , ∞+∞ , ∞+∞ } = 1, D3 = min {D3, D1+R13, D2+R23, D4+R43, D5+R53, D6+R63} = min {∞ , 0+ , ∞ 1+5, ∞+1 , ∞+∞ , ∞+∞ } = 6, D4 = min {D4, D1+R14, D2+R24, D3+R34, D5+R54, D6+R64} = min {∞ , 0+ , ∞ 1+2, 6+∞ , ∞+3, ∞+∞ } = 3, D5 = min {D5, D1+R15, D2+R25, D3+R35, D4+R45, D6+R65} = min {∞ , 0+ , 1+ , 6+∞ ∞ ∞ , 3+4 , ∞+1 } = 7, D6 = min {D6, D1+R16, D2+R26, D3+R36, D4+R46, D5+R56} = min {∞ , 0+ , 1+7, ∞ 6+1 , 3+∞ , 7+∞ } = 7. k =3, D1 = 0, D2 = min {1, 0+1 , 6+ , 3+∞ ∞ , 7+∞ , 7+∞ } = 1, D3 = min {6, 0+ , 1+5, ∞ 3+1, 7+∞ , 7+∞ } = 4, D4 = min {3, 0+ , ∞ 1+2, 4+∞ , 7+3, 7+∞ } = 3, D5 = min {7, 0+ , 1+∞ , 4+∞ ∞ , 3+4, 7+1} = 7, D6 = min {7, 0+ , 1+7, ∞ 4+1, 3+∞ , 7+∞ } = 5. k =4, D1 = 0, D2 = min {1, 0+1, 6+ , 3+∞ ∞ , 7+∞ , 7+∞ } = 1, D3 = min {6, 0+ , 1+5, ∞ 3+1, 7+∞ , 7+∞ } = 4, D4 = min {3, 0+ , ∞ 1+2, 4+∞ , 7+3, 7+∞ } = 3, D5 = min {7, 0+ , 1+∞ , 4+∞ ∞ , 3+4, 7+1} = 7, D6 = min {7, 0+ , 1+7, ∞ 4+1, 3+∞ , 7+∞ } = 5. k =5, D1 = 0, D2 = min {1, 0+1 , 6+ , 3+∞ ∞ , 7+∞ , 5+∞ } = 1, D3 = min {6, 0+ , 1+5, ∞ 3+1, 7+∞ , 5+∞ } = 4, D4 = min {3, 0+ , ∞ 1+2, 4+∞ , 7+3, 5+∞ } = 3, D5 = min {7, 0+ , 1+∞ , 4+∞ ∞ , 3+4, 5+1} = 6, D6 = min {7, 0+ , 1+7, ∞ 4+1, 3+∞ , 5+∞ } = 5. k D1 D2 D3 D4 D5 D6 1 0 1 ∞ ∞ ∞ ∞ 2 0 1 6 3 7 7 3 0 1 4 3 7 5 4 0 1 4 3 6 5 5 0 1 4 3 6 5 10.3. Bellman-Ford Algorithm __MACOSX/Algorítmos/._Optimization_EN_Ford-Belman_algorithm.pdf __MACOSX/._Algorítmos Aulas de Jorge/Aula10 - Coloração e planaridade.pdf 1 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Exercício 1 1. Uma companhia manufatura os produtos químicos C1, C2, … Cn. Alguns destes produtos podem explodir se colocados em contato com outros. Como precaução contra acidentes, a companhia quer construir k armazéns para armazenar os produtos químicos de tal forma que produtos incompatíveis fiquem em armazéns diferentes. Qual é o menor número k de armazéns que devem ser construídos? Como resolver este problema com a ajuda da teoria dos Grafos? 1. Uma companhia manufatura os produtos químicos C1, C2, … Cn. Alguns destes produtos podem explodir se colocados em contato com outros. Como precaução contra acidentes, a companhia quer construir k armazéns para armazenar os produtos químicos de tal forma que produtos incompatíveis fiquem em armazéns diferentes. Qual é o menor número k de armazéns que devem ser construídos? Como resolver este problema com a ajuda da teoria dos Grafos? Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Teoria dos Grafos Planaridade e Coloração em Grafos Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Aspectos da Topologia de Grafos • Planaridade (grafos planares) •Coloração de grafos • Exemplos: –Problema das 3 casas/3 serviços –Problema de coloração de mapas • Planaridade (grafos planares) •Coloração de grafos • Exemplos: –Problema das 3 casas/3 serviços –Problema de coloração de mapas Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Conceitos Básicos de Planaridade • Grafo planar • Grafo plano • K4 é planar? • Grafo planar • Grafo plano • K4 é planar? Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Grafos Não-Planares • K3,3 é não-planar. • K5 é não-planar. • Prova por construção. • K3,3 é não-planar. • K5 é não-planar. • Prova por construção. Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Teorema de Kuratowski • Importância do K3,3 e K5 para descobrir se um grafo é ou não planar. – Nenhum grafo que contém um destes grafos como subgrafo não pode ser planar. – Nenhum grafo obtido através do K3,3 e K5 pela simples adição de vértices às arestas não pode ser planar. • Importância do K3,3 e K5 para descobrir se um grafo é ou não planar. – Nenhum grafo que contém um destes grafos como subgrafo não pode ser planar. – Nenhum grafo obtido através do K3,3 e K5 pela simples adição de vértices às arestas não pode ser planar. 2 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG DEFINIÇÃO: Dois grafos são homeomórficos se e somente se se eles podem ser obtidos a partir do mesmo grafo pela adição de vértices (necessariamente de grau 2) às arestas. Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG TEOREMA (Kuratowski): Um grafo é planar se e somente se ele não tem subgrafo homeomórfico a K 5 e K 3,3 . Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Coloração em Grafos • Qual o número mínimo de cores que devemos usar para colorir os estados do mapa do Brasil, com a restrição de que estados vizinhos não podem ter a mesma cor? – Relação com o problema de colorir vértices de um grafo. – O Teorema das 4 Cores, provado em 1976, se constitui em um dos resultados mais importantes da matemática no Século XX. (permaneceu sem solução desde 1852) • Aplicação em muitos problemas práticos. • Qual o número mínimo de cores que devemos usar para colorir os estados do mapa do Brasil, com a restrição de que estados vizinhos não podem ter a mesma cor? – Relação com o problema de colorir vértices de um grafo. – O Teorema das 4 Cores, provado em 1976, se constitui em um dos resultados mais importantes da matemática no Século XX. (permaneceu sem solução desde 1852) • Aplicação em muitos problemas práticos. Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Coloração em Grafos • Uma coloração de um grafo é uma atribuição de cores aos vértices, de modo que vértices adjacentes tenham cores distintas. • Um grafo G tem k-coloração se ele pode ser colorido com k cores. • Se G tem k-coloração mas não pode ter (k-1)- coloração: – O número cromático de G é k. – G é k-cromático. – χ(G) = k . • Uma coloração de um grafo é uma atribuição de cores aos vértices, de modo que vértices adjacentes tenham cores distintas. • Um grafo G tem k-coloração se ele pode ser colorido com k cores. • Se G tem k-coloração mas não pode ter (k-1)- coloração: – O número cromático de G é k. – G é k-cromático. – χ(G) = k . Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Coloração em Grafos Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Coloração em Grafos 3 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Alguns Cenários Interessantes • χ(G) = 1. O que isso significa? • χ(Kn) = ? • χ(G) = 2. Quando isso ocorre? • χ(G) = 1. O que isso significa? • χ(Kn) = ? • χ(G) = 2. Quando isso ocorre? Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Alguns Cenários Interessantes • χ(G) = 1. Podemos afirmar que o grafo G não tem arestas. • χ(Kn) = n. Isso implica dizer que podemos ter números cromáticos grandes. • χ(G) = 2. Se e somente se é bipartido. E no caso de uma árvore? • χ(G) = 1. Podemos afirmar que o grafo G não tem arestas. • χ(Kn) = n. Isso implica dizer que podemos ter números cromáticos grandes. • χ(G) = 2. Se e somente se é bipartido. E no caso de uma árvore? Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Mais considerações • Não é possível garantir que tipos de grafos são 3- cromáticos. • Se um grafo tem n vértices, seu número cromático não pode ser maior do que n. • Se Kr é subgrafo de um grafo G, o número cromático não pode ser menor do que r. • Não é possível garantir que tipos de grafos são 3- cromáticos. • Se um grafo tem n vértices, seu número cromático não pode ser maior do que n. • Se Kr é subgrafo de um grafo G, o número cromático não pode ser menor do que r. Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Alguns Teoremas Úteis • Se G é um grafo e ∆ é o maior grau de seus vértices, então G tem (∆ + 1)-coloração. • Se G é um grafo conectado que não é completo, e se o maior grau de seus vértices é ∆ (≥ 3), então G tem (∆)-coloração. • Todo grafo planar pode ter 5-coloração. • Appel e Hasken provaram em 1976 que todo grafo planar admite 4-coloração. • Como determinar o número cromático de um grafo? • Se G é um grafo e ∆ é o maior grau de seus vértices, então G tem (∆ + 1)-coloração. • Se G é um grafo conectado que não é completo, e se o maior grau de seus vértices é ∆ (≥ 3), então G tem (∆)-coloração. • Todo grafo planar pode ter 5-coloração. • Appel e Hasken provaram em 1976 que todo grafo planar admite 4-coloração. • Como determinar o número cromático de um grafo? Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG 4 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Exercício 2 1. Emissoras de televisão vão ser instaladas em estações baseadas em nove cidades de nosso estado (cidades A, B, ..., I). As regulamentações do setor de telecomunicações indicam que uma mesma emissora não pode ser instalada em duas cidades com distância inferior a 150Km. Considere a tabela abaixo que indica as distâncias entre as cidades. Qual o menor número de emissoras para contemplar as nove cidades? Utilize a teoria dos grafos para resolver este problema e justificar a sua resposta. 1. Emissoras de televisão vão ser instaladas em estações baseadas em nove cidades de nosso estado (cidades A, B, ..., I). As regulamentações do setor de telecomunicações indicam que uma mesma emissora não pode ser instalada em duas cidades com distância inferior a 150Km. Considere a tabela abaixo que indica as distâncias entre as cidades. Qual o menor número de emissoras para contemplar as nove cidades? Utilize a teoria dos grafos para resolver este problema e justificar a sua resposta. __MACOSX/Aulas de Jorge/._Aula10 - Coloração e planaridade.pdf Aulas de Jorge/Aula11 - Fluxo em rede e emparalhamento.pdf 1 Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Teoria dos Grafos Fluxo em Redes Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Introdução • Considere a seguinte situação modelada por um grafo: – Cada arco representa uma rua de mão única. – O peso de cada arco indica o maior fluxo possível ao longo da rua (veículos/hora). • Qual o maior número possível de veículos que pode viajar de v a w em uma hora? • Considere a seguinte situação modelada por um grafo: – Cada arco representa uma rua de mão única. – O peso de cada arco indica o maior fluxo possível ao longo da rua (veículos/hora). • Qual o maior número possível de veículos que pode viajar de v a w em uma hora? v x z wy3 4 2 2 1 4 4 1 2 Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Rede (de fluxo) • Uma rede (de fluxo) G = (V, E) é um grafo dirigido em que cada aresta (u, v) ∈ E tem um valor (não-negativo) capacidade c(u,v). Se (u, v) ∉ E, assume-se que c(u,v) = 0. • Uma rede possui dois vértices especiais: fonte e sorvedouro. • ∀v ∈ V, assume-se que existe um caminho entre a fonte e sorvedouro que passa por v. • O grafo é, portanto, conectado e |E| ≥ |V| - 1 . • Uma rede (de fluxo) G = (V, E) é um grafo dirigido em que cada aresta (u, v) ∈ E tem um valor (não-negativo) capacidade c(u,v). Se (u, v) ∉ E, assume-se que c(u,v) = 0. • Uma rede possui dois vértices especiais: fonte e sorvedouro. • ∀v ∈ V, assume-se que existe um caminho entre a fonte e sorvedouro que passa por v. • O grafo é, portanto, conectado e |E| ≥ |V| - 1 . Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG v x t 13 12 14 2016 4 7s zy 10 9 4 Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Fluxo em Rede • Sejam um grafo G = (V, E), a função capacidade c, uma fonte s e um sorvedouro t. O fluxo em G é uma função f: V×V → REAIS que satisfaz às seguintes propriedades: 1. Restrição de capacidade: ∀u,v ∈ V, f(u,v) ≤ c(u,v). 2. Simetria: ∀u,v ∈ V, f(u,v) = -f(v,u). 3. Conservação do fluxo: ∀u ∈ V – {s, t}, ∑v∈V f(u, v) = 0. • A quantidade f(u,v) (positiva ou negativa) indica o fluxo da rede a partir do vértice u até o vértice v. • O fluxo total da rede é |f| = ∑v∈V f(s,v). • Sejam um grafo G = (V, E), a função capacidade c, uma fonte s e um sorvedouro t. O fluxo em G é uma função f: V×V → REAIS que satisfaz às seguintes propriedades: 1. Restrição de capacidade: ∀u,v ∈ V, f(u,v) ≤ c(u,v). 2. Simetria: ∀u,v ∈ V, f(u,v) = -f(v,u). 3. Conservação do fluxo: ∀u ∈ V – {s, t}, ∑v∈V f(u, v) = 0. • A quantidade f(u,v) (positiva ou negativa) indica o fluxo da rede a partir do vértice u até o vértice v. • O fluxo total da rede é |f| = ∑v∈V f(s,v). Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG v x t 8/13 12/12 11/14 15/2011/16 4/4 7/7s zy 10 4/9 1/4 2 Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG • |f| = 19. • Apenas os fluxos positivos são mostrados. • Se f(u,v) > 0, mostramos f(u,v)/c(u,v). Caso contrário mostramos apenas a capacidade. • Pode ser generalizado para redes com múltiplas fontes e sorvedouros. • Um dos problemas é encontrar o fluxo máximo. • |f| = 19. • Apenas os fluxos positivos são mostrados. • Se f(u,v) > 0, mostramos f(u,v)/c(u,v). Caso contrário mostramos apenas a capacidade. • Pode ser generalizado para redes com múltiplas fontes e sorvedouros. • Um dos problemas é encontrar o fluxo máximo. Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Redes Residuais • Sejam uma rede e um fluxo. Uma rede residual é uma rede com os arcos da rede original que comportam mais fluxo. • Sejam um grafo G = (V, E), a função capacidade c, um fluxo f, uma fonte s e um sorvedouro t: – Capacidade residual de (u,v): • cf(u,v) = c(u,v) – f(u,v). • A rede residual induzida por f é Gf = (V, Ef), em que – Ef = {(u,v) ∈ V×V : cf(u,v) >0}. • Sejam uma rede e um fluxo. Uma rede residual é uma rede com os arcos da rede original que comportam mais fluxo. • Sejam um grafo G = (V, E), a função capacidade c, um fluxo f, uma fonte s e um sorvedouro t: – Capacidade residual de (u,v): • cf(u,v) = c(u,v) – f(u,v). • A rede residual induzida por f é Gf = (V, Ef), em que – Ef = {(u,v) ∈ V×V : cf(u,v) >0}. Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Rede Residual (exemplo) v x t 8 12 11 15 5 4 7s zy 11 4 3 11 5 5 3 5 Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Caminho Expandível • Seja uma rede G = (V, E) e um fluxo f , um caminho expandível p é um caminho de s para t na rede residual Gf. • A capacidade residual de um caminho expandível é definida como: – cf(p) = min{cf(u,v) : (u,v) ∈ p}. • Seja uma rede G = (V, E) e um fluxo f , um caminho expandível p é um caminho de s para t na rede residual Gf. • A capacidade residual de um caminho expandível é definida como: – cf(p) = min{cf(u,v) : (u,v) ∈ p}. Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Caminho Expandível (exemplo) v x t 8 12 11 15 5 4 7s zy 11 4 3 11 5 5 3 5 Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG O Método de Ford-Fulkerson • Como determinar o fluxo máximo? – Utilizar os conceitos de grafo residual e caminho expandível. • Como determinar o fluxo máximo? – Utilizar os conceitos de grafo residual e caminho expandível. BFS(G, s, t) for ∀e ∈ E[G] do fluxo[e] ← 0 while exisitr um caminho expandível p do aumentar f ao longo de p return f 3 Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Cortes • Um corte é uma partição de V em S e T = V – S, em que s ∈ S e t ∈ T • O fluxo da rede (f(S,T)) através do corte é a soma dos fluxos f(u,v), em que u ∈ S e v ∈ T • A capacidade (c(S,T)) do corte é a soma das capacidades c(u,v), em que u ∈ S e v ∈ T • Corte mínimo – um corte com a menor capacidade • |f|= f(S,T) • Um corte é uma partição de V em S e T = V – S, em que s ∈ S e t ∈ T • O fluxo da rede (f(S,T)) através do corte é a soma dos fluxos f(u,v), em que u ∈ S e v ∈ T • A capacidade (c(S,T)) do corte é a soma das capacidades c(u,v), em que u ∈ S e v ∈ T • Corte mínimo – um corte com a menor capacidade • |f|= f(S,T) Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG v x t 12/12 11/14 15/2011/16 4/4 7/7s zy 10 4/9 1/4 8/13 S T Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Teorema do Fluxo Máximo-Corte Mínimo • Se f é o fluxo de G, as seguintes condições são equivalentes: 1. f é um fluxo máximo de G 2. A rede residual Gf não contém caminhos expandíveis 3. |f| = c(S,T) para algum corte (S,T) de G • Se f é o fluxo de G, as seguintes condições são equivalentes: 1. f é um fluxo máximo de G 2. A rede residual Gf não contém caminhos expandíveis 3. |f| = c(S,T) para algum corte (S,T) de G Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Teoria dos Grafos Emparelhamento Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Introdução • Conjunto de arestas M ⊆ E, em que nenhum vértice é incidente a mais de uma aresta. • Emparelhamento Maximal – Nenhuma aresta e, com M ∪ {e} também formando um emparelhamento. • Emparelhamento Máximo – Emparelhamento com o maior |M| possível. • Emparelhamento Perfeito – |M| = n/2: cada vértice é incidente a alguma aresta de M. • Emparelhamento com custo mínimo: cada aresta tem um custo associado. • Conjunto de arestas M ⊆ E, em que nenhum vértice é incidente a mais de uma aresta. • Emparelhamento Maximal – Nenhuma aresta e, com M ∪ {e} também formando um emparelhamento. • Emparelhamento Máximo – Emparelhamento com o maior |M| possível. • Emparelhamento Perfeito – |M| = n/2: cada vértice é incidente a alguma aresta de M. • Emparelhamento com custo mínimo: cada aresta tem um custo associado. Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Introdução • Principais problemas: – Seja um grafo G, encontrar: • Emparelhamento Maximal: fácil (algoritmo guloso) • Emparelhamento Máximo: – Não é fácil encontrar em tempo polinomial. – Caso mais simples é no caso de grafos bipartidos. • Emparelhamento perfeito: – Caso especial de emparelhamento máximo • Aplicações: – Atribuições pessoais: tarefas e competências. – Escalonamento. – Seleção de adversários em competições esportivas. • Principais problemas: – Seja um grafo G, encontrar: • Emparelhamento Maximal: fácil (algoritmo guloso) • Emparelhamento Máximo: – Não é fácil encontrar em tempo polinomial. – Caso mais simples é no caso de grafos bipartidos. • Emparelhamento perfeito: – Caso especial de emparelhamento máximo • Aplicações: – Atribuições pessoais: tarefas e competências. – Escalonamento. – Seleção de adversários em competições esportivas. 4 Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Emparelhamento em Grafos Bipartidos 1 2 3 a b c X Y Vértices emparelhados: 2, 3, a, b. Vértices não-emparelhados: 1, c. É um emparelhamento maximal? Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Emparelhamento em Grafos Bipartidos 1 2 3 a b c X Y Emparelhamento máximo. Emparelhamento perfeito. Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Como encontrar um emparelhamento máximo? • Utilizar o método de Ford-Fulkerson para fluxo em rede. • A idéia é determinar um fluxo em rede, em que os fluxos correspondem aos emparelhamentos. • Definir a rede correspondente G’= (V’, E’), a partir do grafo bipartido G= (L ∪ R, E): – V’= V ∪ {s, t}. – E’= {(s,u): u ∈ L} ∪ {(u,v): u ∈ L, v ∈ R, (u,v) ∈ E} ∪ {(v,t): v ∈ R} • Assinalar peso 1 para cada aresta em E’. • Utilizar o método de Ford-Fulkerson para fluxo em rede. • A idéia é determinar um fluxo em rede, em que os fluxos correspondem aos emparelhamentos. • Definir a rede correspondente G’= (V’, E’), a partir do grafo bipartido G= (L ∪ R, E): – V’= V ∪ {s, t}. – E’= {(s,u): u ∈ L} ∪ {(u,v): u ∈ L, v ∈ R, (u,v) ∈ E} ∪ {(v,t): v ∈ R} • Assinalar peso 1 para cada aresta em E’. Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Exemplo 1 2 3 4 5 6 sorvedouro a b c d e f fonte Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Exemplo 1 2 3 4 5 6 sorvedouro a b c d e f fonte Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Exemplo 1 2 3 4 5 6 sorvedouro a b c d e f fonte 5 Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Exemplo 1 2 3 4 5 6 sorvedouro a b c d e f fonte Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Exemplo 1 2 3 4 5 6 sorvedouro a b c d e f fonte Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Exemplo 1 2 3 4 5 6 sorvedouro a b c d e f fonte Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Exemplo 1 2 3 4 5 6 sorvedouro a b c d e f fonte Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Exemplo 1 2 3 4 5 6 sorvedouro a b c d e f fonte Teoria dos Grafos – 2007.1 © Jorge Figueiredo, DSC/UFCG Excercício 1 2 3 a b c d e 4 __MACOSX/Aulas de Jorge/._Aula11 - Fluxo em rede e emparalhamento.pdf Aulas de Jorge/Aula2 - Definicao de Grafos.pdf 1 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Teoria dos Grafos Aula 3: 18/08/2009 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Agenda • Conceitos básicos: – Grafos simples, Multigrafos, Grafos com auto-laços. – Grafos dirigidos. – Grau de vértices. – Isomorfismo de grafos. – Grafo completo, subgrafo, grafo bipartido, complemento de grafo. • Representação de grafos: – Lista de adjacência. – Matriz de adjacência. – Matriz de incidência. • Conceitos básicos: – Grafos simples, Multigrafos, Grafos com auto-laços. – Grafos dirigidos. – Grau de vértices. – Isomorfismo de grafos. – Grafo completo, subgrafo, grafo bipartido, complemento de grafo. • Representação de grafos: – Lista de adjacência. – Matriz de adjacência. – Matriz de incidência. Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Teoria dos Grafos Definições e Conceitos Básicos Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Definições • Dois tipos de elementos: – Vértices ou nós. – Arestas. • Dois tipos de elementos: – Vértices ou nós. –– ArestasArestas.. v3 v2 v4v1 v5 v6 2 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Grafo Simples G = (V, E) V é um conjunto finito não-vazio de vértices. E é um conjunto finito de arestas. Se e ∈ E, é um conjunto da forma: e = { v, w} = vw = wv, onde v,w ∈ V. e é incidente a v e w. v e w são adjacentes ou vizinhos. G = (V, E) V é um conjunto finito não-vazio de vértices. E é um conjunto finito de arestas. Se e ∈ E, é um conjunto da forma: e = { v, w} = vw = wv, onde v,w ∈ V. e é incidente a v e w. v e w são adjacentes ou vizinhos. Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Grafo Simples v3 v2 v4v1 v5 v6 e1 V = {v1, v2, v3, v4, v5, v6} E = {v1v2, v1v3, v2v3, v2v4, v2v5, v3v4} e1 é incidente a v2 e v5 v1, v3, v4 e v5 são adjacentes a v2 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Graus de Vértices • Grau de um vértice v (deg(v)) é o número de arestas que incidem em v. – Vértice ímpar. – Vértice par. – Vértice isolado. • Um grafo é regular (k-regular) se todos os seus vértices tem o mesmo grau (k). • Seqüência de graus de um grafo consiste em escrever em ordem crescente os graus de seus vértices. • Grau de um vértice v (deg(v)) é o número de arestas que incidem em v. – Vértice ímpar. – Vértice par. – Vértice isolado. • Um grafo é regular (k-regular) se todos os seus vértices tem o mesmo grau (k). • Seqüência de graus de um grafo consiste em escrever em ordem crescente os graus de seus vértices. Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Graus de Vértices v3 v2 v4v1 v5 v6 e1 v6 é um vértice isolado. deg(v6) = 0 v2 é um vértice par. deg(v2) = 4 v5 é um vértice ímpar. deg(v5) = 1 Seqüência de graus = 0, 1, 2, 2, 3, 4 3 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Outros Tipos de Grafos • Pseudo-grafos: – Multigrafos. – Grafos com auto-laços. • Grafos dirigidos. • Não existe terminologia padronizada. • Pseudo-grafos: – Multigrafos. – Grafos com auto-laços. • Grafos dirigidos. • Não existe terminologia padronizada. Vamos usar o termo grafo para representar grafos finitos, não dirigidos, com auto-laços e múltiplas arestas. Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG v3 v2 v4v1 v5 v6 e1 deg(v4) = 4 deg(v3) = 5 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Proposição de Euler •A partir do conceito de adjacência e graus de vértices. •Prova é intuitiva. •Como conseqüência: número de vértices ímpares é par. •A partir do conceito de adjacência e graus de vértices. •Prova é intuitiva. •Como conseqüência: número de vértices ímpares é par. Proposição de Euler: i 1 n deg vi 2 E Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG v3 v2 v4v1 v5 v6 Σ deg(vi) = 2 + 4 + 3 + 2 + 1 + 0 = 12 = 2 x 6 № de vértices ímpares = 2 = v3 e v5 4 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Isomorfismo de Grafos • Dois grafos são isomórficos: – São essencialmente iguais. – Correspondência entre os vértices e arestas. • Sejam G1= (V1, E1) e G2 = (V2, E2): – G1 ≈ G2, se existir uma bijeção f: V1 → V2: • Se vw é uma aresta de E1, então f(v)f(w) é aresta de E2. • Toda aresta em E2 tem a forma de f(v)f(w) para alguma aresta vw ∈ E1. • Dois grafos são isomórficos: – São essencialmente iguais. – Correspondência entre os vértices e arestas. • Sejam G1= (V1, E1) e G2 = (V2, E2): – G1 ≈ G2, se existir uma bijeção f: V1 → V2: • Se vw é uma aresta de E1, então f(v)f(w) é aresta de E2. • Toda aresta em E2 tem a forma de f(v)f(w) para alguma aresta vw ∈ E1. Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Isomorfismo de Grafos u v w x y z Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Isomorfismo de Grafos u v w x y z f(u) = azul, f(v) = roxo, f(w) = vermelho f(x) = verde, f(y) = amarelo, f(z) = rosa Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Isomorfismo de Grafos • Isomorfismo preserva: – Simetria: G1 ≈ G2 ↔ G2 ≈ G1. – Reflexividade: G ≈ G. – Transitividade: G1 ≈ G2 e G2 ≈ G3 → G1 ≈ G3. • Proposições válidas se G1 ≈ G2: – G1 e G2 têm o mesmo número de vértices. – G1 e G2 têm a mesma seqüência de graus. – G1 e G2 têm o mesmo número de arestas. • Isomorfismo preserva: – Simetria: G1 ≈ G2 ↔ G2 ≈ G1. – Reflexividade: G ≈ G. – Transitividade: G1 ≈ G2 e G2 ≈ G3 → G1 ≈ G3. • Proposições válidas se G1 ≈ G2: – G1 e G2 têm o mesmo número de vértices. – G1 e G2 têm a mesma seqüência de graus. – G1 e G2 têm o mesmo número de arestas. 5 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Subgrafos • G1 = (V1, E1) é subgrafo de G2 = (V2, E2) sss: – V1 é subconjunto de V2; e, – E1 é subconjunto de E2. • Subgrafos podem ser obtidos através da remoção de arestas e vértices. • G1 = (V1, E1) é subgrafo de G2 = (V2, E2) sss: – V1 é subconjunto de V2; e, – E1 é subconjunto de E2. • Subgrafos podem ser obtidos através da remoção de arestas e vértices. Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Subgrafos u w x y z u v w x y z u v w x y z G1 G2 G3 G2 = G1 \ {uz} G3 = G1 \ {v} Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Grafos Completos e nulos • Grafo nulo é aquele em que E = Ø. • Um grafo simples é completo se qualquer par de vértices distintos é adjacente. – Grafo simples completo de n vértices é dito Kn. • Grafo nulo é aquele em que E = Ø. • Um grafo simples é completo se qualquer par de vértices distintos é adjacente. – Grafo simples completo de n vértices é dito Kn. K3 K4 K5 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Grafos Bipartidos • Grafo bipartido é aquele em que V pode ser dividido em dois subconjuntos disjuntos não vazios V1 e V2. – Cada aresta conecta um vértice de V1 e um vértice de V2. • Grafo bipartido completo: cada um dos elementos de V1 é adjacente a cada um dos elementos de V2. • Grafo bipartido é aquele em que V pode ser dividido em dois subconjuntos disjuntos não vazios V1 e V2. – Cada aresta conecta um vértice de V1 e um vértice de V2. • Grafo bipartido completo: cada um dos elementos de V1 é adjacente a cada um dos elementos de V2. 6 Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Grafos Bipartidos u v w x y z K3,3 V1 = {u, v, w} V2 = {x, y, z} Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Complemento de um Grafo • Seja G um grafo simples: – G é complemento de G se: • V = V; e, • Dois vértices são adjacentes em G se e somente se eles não são adjacentes em G. • Seja G um grafo simples: – G é complemento de G se: • V = V; e, • Dois vértices são adjacentes em G se e somente se eles não são adjacentes em G. Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Exercício 1. Considere as 8 primeiras letras do seu nome. Construa um grafo simples em que: • Toda vogal é adjacente a toda consoante. • Nenhuma vogal é adjacente a outra vogal. • Nenhum consoante é adjacente a outra consoante. a) Defina formalmente esse grafo. b) Determine o complemento desse grafo. c) É um grafo bipartido? Justifique. 1. Considere as 8 primeiras letras do seu nome. Construa um grafo simples em que: • Toda vogal é adjacente a toda consoante. • Nenhuma vogal é adjacente a outra vogal. • Nenhum consoante é adjacente a outra consoante. a) Defina formalmente esse grafo. b) Determine o complemento desse grafo. c) É um grafo bipartido? Justifique. Teoria dos Grafos © Jorge Figueiredo, DSC/UFCG Exercício 1. Você e seu amigo retornam das férias e são recebidos no aeroporto pelas mães e por duas irmãs do seu amigo. Após troca de abraços, cada uma das (outras) cinco pessoas lhe fala o número de abraços que deu. Curiosamente, todos os números são diferentes. Assumindo que: – Você e seu amigo não se abraçaram. – A mãe de vocês não se abraçaram. – As irmãs não se abraçaram. – Duas mesmas pessoas se abraçaram, no máximo, uma vez. Responda: 1. Quantas pessoas você abraçou? 2. Quantas pessoas seu amigo abraçou? 1. Você e seu amigo retornam das férias e são recebidos
Compartilhar