Problemas em Grafos

Problema 1

1. Em um certo reino, existem 300 cidades, e cinco estradas partem de cada cidade. Quantas estradas existem no reino?


Problema 2

Na cidade de Micrópolis, há 7 telefones. Um candidato a prefeito prometeu que ampliaria a rede de telefonia de modo que cada um dos 7 telefones esteja conectado diretamente a exatamente 5 outros telefones. É possível que ele cumpra sua promessa?

Use o  seguinte Teorema

Em todo grafo G=(V,E), a soma dos graus dos vértices é igual ao dobro do número de arestas, ou
seja,

$\sum_{v \in V}$ d(v) =2*|E| 

Problema 3

 Existem 105 cidades em Arbórea. Algumas delas são conectadas por estradas, e cada par de cidades é

conectado por um e somente um caminho simples. Quantas estradas existem?

Teorema: Seja G = (V,E) um árvore , |V| = n e |E| = m, então  m = n -1.

Problema 4

Mostre que em toda festa, existem pelo menos duas que possuem deram a mesma quantidade de  apertos

de mão nos participantes da festa.

Separe em dois casos:

Caso 1) Existe uma pessoa que não apertou a mão de ninguém.

Caso 2) Cada pessoa apertou a mão de pelo menos uma pessoa.

Problema 4

É possível caminhar pela casa da figura abaixo de forma que cada porta da casa seja usada exatamente

uma vez? Justifique.

Problema 5

Verifique se os grafos são bipartidos:

Problema 6

Seja G = (V;E) um grafo simples conexo não-euleriano. Queremos construir um grafo H que seja euleriano e que contenha G como subgrafo. Considere os seguintes possíveis processos de construção:

(I) Acrescenta-se um novo vértice, ligando-o a cada vértice de G por uma aresta.

(II) Acrescenta-se um novo vértice, ligando-o a cada vértice de grau ímpar de G por uma aresta.

(III) Cria-se uma nova cópia G' do grafo G e acrescenta-se uma aresta ligando cada par de vértices correspondentes.

(IV) Escolhe-se um vértice arbitrário de G e acrescentam-se arestas ligando este vértice a todo vértice de grau ímpar de G.

(V) Duplicam-se todas as arestas de G.

(VI) Acrescentam-se arestas a G até se formar o grafo completo com |V| vértices.

Quais dos processos acima sempre constroem corretamente o grafo H?

(a) Somente (II) e (IV)                 (b) Somente (II), (IV) e (V)         (c) Somente (III), (V) e (VI)

(d) Somente (II), (IV), (V) e (VI)               (e) Somente (I), (III), (IV) e (V)

Problema 7

Todo um grafo possui n vértices, cada um dos quais com grau no mínimo (n−1)/2, então ele é

conexo. Falso ou Verdadeiro?

Problema 8

É possível que a seguintes listas de números sejam os graus de todos os vértices de um grafo simples?

i) 2,2,2,3 

ii) 1,2,2,3,4

iii) 3,4,3,3,2

iv) 4,4,4,4,2

Nos casos em que a resposta é afirmativa, represente um grafo nessas condições.

Problemas 9

É possível que os cavalos do tabuleiro (I) fiquem na posição do tabuleiro (II) ?

Problema 10

Podemos desenhar uma estrela de cinco pontas sem tirar o lápis do papel . Justifique

Problema 11

Podemos desenhar um envelope sem tirar o lápis do papel mas não terminamos no

mesmo ponto que começamos. Justifique

Problema 12

Uma criança diz ter posto a ponta do lápis numa das bolinhas e com movimentos contínuos

(sem levantar e sem retroceder o lápis) traçou as linhas que formam o desenho da casa,

traçando cada linha uma única vez. Rudini, professor de Matemática Discreta, acha que ela

está trapaceou pois não foi capaz de achar nenhuma seqüência que pudesse produzir tal

resultado. Você concorda com Rudini?

Problema 13

Três casas e têm de ser ligadas ao gás, à água e à electricidade. Será possível encontrar um

grafo tal que as (linhas que representam as) arestas não se cruzam?

Prove por absurdo, usando o Teorema de Euler F = A – V +2.

Problema 14

Residência do bilionário Count Van Diamond, que acaba de ser assassinado.  Sherlock Gomes (um conhecido detetive que nas horas vagas é um estudioso da Teoria dos Grafos) foi chamado para investigar o caso. 

O mordomo alega ter visto o jardineiro entrar na sala da piscina (lugar onde ocorreu o assassinato) e logo em seguida deixar sair daquela sala pela mesma porta que havia entrado.

O jardineiro, contudo, afirma que  ele não poderia ser a pessoa vista pelo mordomo, pois ele havia entrado na casa, passado por todas as portas uma única vez e, em seguida, deixado a casa.

Sherlock Gomes avaliou a planta da residência e em poucos minutos declarou solucionado o caso.

a) Quem poderia ser o suspeito indicado por Sherlock Gomes?

b)      Qual o raciocínio utilizado pelo detetive para apontar o suspeito? 

Problema 15

Mostre que os números de 1 a 16 podem ser escritos numa reta, de tal modo que a soma de quaisquer dois

números adjacentes seja um quadrado perfeito.

Problema 16

Mostre que os números de 1 a 16 não pode ser escritos ao redor de uma circunferência, de tal modo que a

soma de quaisquer dois números adjacentes seja um quadrado perfeito.

Problema 1,3 e 4 retirados de 

http://www.obm.org.br/export/sites/default/semana_olimpica/docs/2006/grafos_onofre.pdf

Problema 2 e 9 retirados de 

http://www.obm.org.br/export/sites/default/revista_eureka/docs/artigos/grafos_dupla.pdf

Busca em Profundidade

A busca em profundidade é um algoritmo para realizar busca  e travessia numa árvore ou em um grafo. A ideia do algoritmo é começar num nó raiz e explora cada um dos seus ramos  tanto quanto possível antes de retroceder.

Aplicações:

• Descobrir se um grafo é conexo.
• Descobrir se um grafo é bipartido.
• Encontrar componentes fortemente conexas.
• Encontrar articulações.
• Encontrar pontes.
• Encontrar uma ordenação topológica.
• Resolver quebra-cabeças.

Vamos implementar a busca em profundidade utilizando as ferramentas da STL.

#include <iostream>
#include <vector>
#define all(c) (c).begin, (c).end()
#define tr(c,it) for(typeof((c).begin()) it = (c).begin()  ; it != (c).end() ; it++ )
using namespace std;

typedef vector <int> vi;
typedef vector <vi> vvi;
typedef vector <bool> vb;

void dfs(int i, vvi g ,vb & marc, int & cont){
 if( !marc[i] ){
  cont++;
  marc[i] =true;
  tr(g[i],it){
   dfs(*it, g, marc, cont);
  }  
 }
}

int main(){
 int N,M;
 int a,b;
 int cont;
 
 while(1){
  
  cin >> N >> M;
  
  vvi g(N+1);
  
  for(int i =0;i<M;i++){
   cin >> a >> b;
   g[a].push_back(b);
   g[b].push_back(a);
  }
  
  vb marc(N+1,false);  
  
  cont = 0 ;
  dfs(1, g, marc, cont);
  
  if(cont==N)
   cout << "Normal\n" ; 
  else 
   cout << "Falha\n" ;
   
 }
}

Conexidade de um grafo

Aplicação: Descobrir se um grafo é conexo ou não. 

http://br.spoj.pl/problems/ENERGIA/

Ficha Técnica:
Problema: Descobrir se um grafo é conexo
Algoritmo: Busca em Profundidade usando recursão
Estrutura de Dados: Lista de Adjacência usando vector
Observações:
Compared to the other base standard sequence containers (deques and lists), vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists.
Complexidade: O(V+E)
Tempo:  0.14
Linguagem: C++
Memória:  2.8M

Busca em Profundidade usando recursão usando lista de adjacência C++

#include <iostream>
#include <vector>
#include <stack>
#define MAX 101
using namespace std;
//representacao de grafo usando lista de adjacência
vector <int> lista[MAX]; 
//marc[i] = true significa que o vetor foi visitado
bool marc[MAX];
//contador de numero de visitas
int cont;

void bp(int u){
 vector <int>::iterator it; 
 cont++;
 for(it = lista[u].begin(); it!=lista[u].end(); it++){
    if(!marc[*it]){
      marc[*it]=true;
      bp(*it);
    }
 } 
 

}
int main(){
 int n,m,u,v,i,a,b,teste=1;
 while(true){
   cin >> n >> m; 
   if(n==0 && m==0) break;
   for(i=1;i<=n;i++){ 
     marc[i]=false;
     lista[i].clear();
          }
   for(i=1;i<=m;i++){
     cin >> a >> b;
     lista[a].push_back(b);
     lista[b].push_back(a);
   }
  
   marc[1] = true;
   cont = 0;
   bp(1);
  
  
   cout << "Teste " << teste++ << endl;
   if(cont==n)
    cout << "normal" << endl;
   else
           cout << "falha" << endl;
   cout << endl;
 }
} 

Ficha Técnica:
Problema: Descobrir se um grafo é conexo
Algoritmo: Busca em Profundidade usando pilha
Estrutura de Dados: Lista de Adjacência usando matriz
Complexidade: O(V+E)
Tempo:  0.02
Linguagem: C
Memória:  1.7M

Busca em Profundidade usando pilha e  lista de adjacência em C

#include <stdio.h>
#define MAX 101

int pilha[MAX];
int topo;
int g[MAX][MAX];
int d[MAX];
int marc[MAX];

int inicializa(){
 topo = 0;
}

void push(int x){
 pilha[topo++] = x;
}

int pop(){
 return pilha[--topo];
}

int vazia(){
 return topo==0;
}

int main(){
 int n,m,u,i,v,a,b,cont,teste=1;
 
 while(1){
  scanf("%d %d",&n,&m);
  
  if(n==0 && m==0) break;
  
  for(i=1;i<=n;i++){
   d[i] = 0;
   marc[i]=0; 
  }
  
  for(i=1;i<=m;i++){
   scanf("%d %d",&a,&b);
   g[a][d[a]++]=b;
   g[b][d[b]++]=a;
  }

  inicializa();
  marc[1]=1;
  push(1);
  cont = 0;
  
  while(!vazia()){
   u = pop();
   cont++;
   
   for(i=0;i<d[u];i++){
    v = g[u][i];
    if(marc[v]==0){
     marc[v]=1;
     push(v);
    }
   }
  }
  
  printf("Teste %d\n",teste++);
  
  if(cont==n) printf("normal\n\n");
  else printf("falha\n\n");
  
 }
 
 return 0;
  

}

Ficha Técnica:
Problema: Descobrir se um grafo é conexo
Algoritmo: Busca em Profundidade usando pilha
Estrutura de Dados: Lista de Adjacência usando vector
Complexidade: O(V+E)
Tempo:  0.13
Linguagem: C++
Memória:  2.6M

Busca em Profundidade usando pilha e lista de adjacência em C++

#include <iostream>
#include <vector>
#include <stack>
#define MAX 101
using namespace std;
vector <int> lista[MAX];
vector <int>::iterator it;
stack <int> pilha;
bool marc[MAX];
int main(){
 int n,m,u,v,i,a,b,cont,teste=1;
 while(true){
  cin >> n >> m; 
  if(n==0 && m==0) break;
  for(i=1;i<=n;i++){ 
    marc[i]=false;
     lista[i].clear();
  }
  for(i=1;i<=m;i++){
   cin >> a >> b;
   lista[a].push_back(b);
   lista[b].push_back(a);
  }
  marc[1] = true;
  pilha.push(1);
  cont = 0;
  while(!pilha.empty()){
   u = pilha.top();
   pilha.pop();
   cont++;
   for(it = lista[u].begin(); it!=lista[u].end(); it++){
    if(!marc[*it]){
     marc[*it]=true;
     pilha.push(*it);
    }
   } 
  }
  
  
  cout << "Teste " << teste++ << endl;
  if(cont==n)
   cout << "normal" << endl;
  else
   cout << "falha" << endl;
  cout << endl;
 }
}

2009-10-12 15:26:37  Transmissão de Energia aceito 0.13  2.6M  C++4.0.0-8 

Ficha Técnica:
Problema: Descobrir se um grafo é conexo
Algoritmo:
Estrutura de Dados: Conjuntos Disjuntos
Complexidade:??
Tempo:  0.03
Linguagem: C
Memória:  1.6M

Descobrindo se grafo é conexo usando conjuntos disjuntos

#include <stdio.h>

int p[101];
int ordem[101];

void make_set(int x){
     p[x] = x;
     ordem[x] = 0;
}

int find_set(int x){
    if( x!= p[x] ) 
      p[x] = find_set(p[x]);
    return p[x];
}

void link(int x,int y){
     if(ordem[x] > ordem[y]){
        p[y] = x;
     }else{
        p[x] = y;
        if(ordem[x]==ordem[y])
          ordem[y]++;
     }
}


void une(int x,int y){
     link(find_set(x),find_set(y));
}


int same_componente(int x,int y){
    if(find_set(x)==find_set(y)) return 1;
    else return 0;
}

int main(){
    int n,m,i,a,b,conexo,teste=1,cont;
    
    while( scanf("%d %d",&n,&m) > 0 ){
           if(n+m==0) break;
           
           for(i=1;i<=n;i++){
             make_set(i);
           }
           
           cont = 0;
           for(i=1;i<=m;i++){
              scanf("%d %d",&a,&b);
              if( !same_componente(a,b) )
               cont++;
        une(a,b);
           }
           
           
           printf("Teste %d\n",teste++);
           if(cont==n-1) printf("normal\n\n");
           else printf("falha\n\n");
    }
    return 0;
    
}

2009-10-12 15:01:21     Transmissão de Energia    aceito 0.03     1.6M     C