Passeios e conectividade

Prévia do material em texto

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
Instituto de Matemática - DMPA
Profa. Virgínia Maria Rodrigues
Matemática Discreta I – 2015/2
Passeios e Conectividade
Definição:
Seja G=G (V , E) um grafo não-orientado.
(i) Um passeio em G, de um vértice v1 a um vértice vn , é uma sequência
v1 e1v2 e2…vn−1 en−1 vn , onde v1 , v2 ,… , vn∈V e ei={vi , v i+1 }, ou seja, é uma sequência de
vértices e arestas adjacentes.
(ii) Um passeio em que v1=vn é um circuito.
(iii) Um passeio em que v i≠v j , para todo i≠ j , é chamado de caminho.
(iv) No caso em que v1=vn e v i≠v j , para todos os demais i≠ j , o passeio é um ciclo. 
Obs.:
• Quando o grafo for simples, indicaremos um passeio v1 e1v2 e2…vn−1 en−1 vn listando apenas a 
sua sequência de vértices v1 v2…vn−1 vn , pois ela determina o passeio de forma única.
• Nomenclatura utilizada pelo K. Rosen: caminho -- no lugar de passeio, ciclo -- em vez de
circuito, caminho ou ciclo simples quando não há repetição de arestas.
Definição:
Um circuito Euleriano em um grafo G é um circuito que utiliza todas as arestas do grafo
exatamente uma vez. Dizemos que um grafo é Euleriano se ele possui um circuito Euleriano.
Teorema
Se um grafo é Euleriano então todos os seus vértices têm grau par.
Corolário
O problema das pontes de Könisgberg não tem solução.
Definição:
Seja G=G (V , E) um grafo não-orientado.
(i) Dizemos que G é um grafo conexo se existe um caminho entre qualquer par de vértices distintos
de G. Caso contrário, dizemos que o grafo G é desconexo.
(ii) Um subgrafo de G é um grafo H=H (W , F ) tal que W⊆V e F⊆E . Um subgrafo de G é
próprio se ele é diferente de G.
(iii) Uma componente conexa H de G é um subgrafo conexo maximal de G, ou seja, se H⊂K⊆G ,
onde K é um subgrafo conexo de G, então K=G.
Teorema
Se um grafo é conexo a menos de vértices isolados e todos os seus vértices têm grau par, então
ele é Euleriano.
Teorema
Um grafo conexo é Euleriano se e somente se todos os seus vértices têm grau par.
1
Definição:
Sejam u e v dois vértices de um grafo não orientado G=G (V , E). Um passeio Euleriano de u a
v é um passeio de u a v que utiliza todas as todas as arestas de G exatamente uma vez.
Corolário
Existe um passeio Euleriano entre dois vértices u e v de um grafo G se e somente se G é conexo e
u e v são os únicos vértices de grau ímpar de G.
Icosian Puzzle: jogo inventado em 1857 pelo matemático irlandês Sir William R. Hamilton. Consistia
de um dodecaedro regular (poliedro com 12 faces pentagonais regulares) de madeira, com um pino em
cada vértice e barbante. Os 20 vértices eram associados a cidades diferentes do mundo. O objetivo do
jogo era começar em uma cidade e viajar ao longo das arestas do dodecaedro, visitando cada uma das
outras 19 cidades exatamente uma vez e terminando de volta na primeira cidade.
Definição:
Um circuito (ciclo) Hamiltoniano em um grafo G é um circuito que utiliza todos os vértices do
grafo exatamente uma vez. Dizemos que um grafo é Hamiltoniano se ele possui um circuito
Hamiltoniano.
Proposição
Se um grafo G tem um ciclo Hamiltoniano, então G tem um subgrafo H tal que
i. H contém todos os vértices de G.
ii. H é conexo.
iii. H tem mesmo número de vértices e arestas.
iv. Todo vértice de H tem grau 2.
Teorema de Dirac
Se G for um grafo simples com n vértices, onde n⩾3, tal que o grau de todo vértice é, pelo
menos,
n
2
, então G é Hamiltoniano.
Teorema de Ore
Se G for um grafo simples com n vértices, onde n⩾3, tal que ∂(u)+∂(v)⩾n , para cada par de
vértices não adjacentes u e v em G, então G é Hamiltoniano.
vrodrig@mat.ufrgs.br 2
Obs.:
O problema das pontes de Königsberg é similar ao Problema do Carteiro Chinês, originalmente
estudado pelo matemático chinês Mei-ko Kwan. Neste problema, as arestas representam ruas que o
carteiro deve percorrer para entregar cartas e queremos encontrar um circuito que contenha todas as
arestas (o carteiro deve passar por todas as ruas) e cuja soma das distâncias percorridas (soma dos
pesos das arestas) seja mínima. Se o grafo for Euleriano, qualquer circuito Euleriano constitui uma
solução ótima, pois ada rua será percorrida exatamente uma vez.
O Problema do Caixeiro Viajante:
Neste problema de otimização, queremos determinar a menor rota que um caixeiro-viajante deveria
tomar para visitar um conjunto de cidades, ou seja, queremos encontrar um ciclo Hamiltoniano (o
caixeiro deve visitar todas as cidades) de custo mínimo, onde o custo de um ciclo é a soma dos custos
(distâncias percorridas) das arestas do ciclo. 
Este problema pode ser resolvido listando-se todos os circuitos Hamiltonianos começando e
terminando num certo vértice e calculando o custo de cada um. Neste caso, para um grafo completo de
n vértices, uma vez escolhido o ponto inicial teremos que examinar (n−1) !/ 2 ciclos. Num grafo com
25 vértices, considerando que levássemos apenas 10−9 segundos (1 nanossegundo) para examinar
cada ciclo, precisaríamos de aproximandamente 10 milhões de anos para examinar todos...
Nenhum algoritmo com tempo polinomial no pior caso é conhecido para resolver este problema.
vrodrig@mat.ufrgs.br 3