Baixe o app para aproveitar ainda mais
Leia os materiais offline, sem usar a internet. Além de vários outros recursos!
Grafos 2009.2 UFCG
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 recebidosCompartilhar
Materiais relacionados
13 pág.
Perguntas relacionadas
Compartilhar