Embed Size (px)
Citation preview
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Caminhos mais longos em um grafo
Susanna Figueiredo de RezendeOrientadora: Yoshiko Wakabayashi
Instituto de Matematica e EstatısticaUniversidade de Sao Paulo
15 de novembro de 2011
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 1 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
1 Preliminares
2 O problema do caminho mais longo
3 Interseccao de caminhos mais longos
4 Um novo resultado
5 Conclusoes
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 2 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Grafos
G = (V ,E )
V: Vertices
E: Arestas (pares nao ordenados de vertices)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 3 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Grafos
G = (V ,E )
V: Vertices
E: Arestas (pares nao ordenados de vertices)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 3 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Grafos
G = (V ,E )
V: Vertices
E: Arestas (pares nao ordenados de vertices)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 3 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Grafos
G = (V ,E )
V: Vertices
E: Arestas (pares nao ordenados de vertices)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 3 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Grafos
G = (V ,E )
V: Vertices
E: Arestas (pares nao ordenados de vertices)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 3 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Grafos
G = (V ,E )
V: Vertices
E: Arestas (pares nao ordenados de vertices)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 3 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
PlanaridadePlanarNao-planar
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 4 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
PlanaridadePlanarNao-planar
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 4 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
PlanaridadePlanarNao-planar
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 4 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
PlanaridadePlanarNao-planar
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 4 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
CaminhosP: Caminho
Sequencia de vertices (e arestas) distintosExemplo: C-D-F-BComprimento: 3Nao e caminho: C-D-F-B-A-H-F-E
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 5 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
CaminhosP: Caminho
Sequencia de vertices (e arestas) distintosExemplo: C-D-F-BComprimento: 3Nao e caminho: C-D-F-B-A-H-F-E
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 5 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
CaminhosP: Caminho
Sequencia de vertices (e arestas) distintosExemplo: C-D-F-BComprimento: 3Nao e caminho: C-D-F-B-A-H-F-E
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 5 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
CaminhosP: Caminho
Sequencia de vertices (e arestas) distintosExemplo: C-D-F-BComprimento: 3Nao e caminho: C-D-F-B-A-H-F-E
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 5 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
CaminhosP: Caminho
Sequencia de vertices (e arestas) distintosExemplo: C-D-F-BComprimento: 3Nao e caminho: C-D-F-B-A-H-F-E
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 5 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
CaminhosP: Caminho
Sequencia de vertices (e arestas) distintosExemplo: C-D-F-BComprimento: 3Nao e caminho: C-D-F-B-A-H-F-E
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 5 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
CaminhoC: Circuito
Sequencia de vertices (e arestas) distintos exceto nasextremidadesExemplo: C-D-F-B-CComprimento: 4
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 6 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
CaminhoC: Circuito
Sequencia de vertices (e arestas) distintos exceto nasextremidadesExemplo: C-D-F-B-CComprimento: 4
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 6 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
CaminhoC: Circuito
Sequencia de vertices (e arestas) distintos exceto nasextremidadesExemplo: C-D-F-B-CComprimento: 4
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 6 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
CaminhoC: Circuito
Sequencia de vertices (e arestas) distintos exceto nasextremidadesExemplo: C-D-F-B-CComprimento: 4
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 6 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
CaminhoC: Circuito
Sequencia de vertices (e arestas) distintos exceto nasextremidadesExemplo: C-D-F-B-CComprimento: 4
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 6 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionados
Encontrar caminho mais curto
Encontrar caminho mais longo
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 7 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionados
Encontrar caminho mais curto
Encontrar caminho mais longo
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 7 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionados
Encontrar caminho mais curto
Encontrar caminho mais longo
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 7 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionados
Encontrar caminho mais curto
Encontrar caminho mais longo
Grafos conexos
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 7 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionados
Encontrar caminho mais curto
Encontrar caminho mais longo
Grafo nao-conexo:
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 7 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosDificuldade
Encontrar caminho mais curto:
DificuldadeProva
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 8 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosDificuldade
Encontrar caminho mais curto:
DificuldadeProva
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 8 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosDificuldade
Encontrar caminho mais longo:
DificuldadeProva
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 8 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosDificuldade
Encontrar caminho mais longo:
DificuldadeProva
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 8 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosDificuldade
Encontrar caminho mais longo:
DificuldadeProva
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 8 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosDificuldade
Encontrar caminho mais longo:
DificuldadeProva
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 8 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosDificuldade
Mais curto vs. mais longo
DificuldadeProva
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 8 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosDificuldade
Mais curto vs. mais longo
DificuldadeProva
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 8 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosDificuldade
Mais curto vs. mais longo
DificuldadeProva
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 8 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosMotivacao
Caminho HamiltonianoBiologia ComputacionalPERT: Program Evaluation and Review Technique
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 9 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosMotivacao
Caminho HamiltonianoBiologia ComputacionalPERT: Program Evaluation and Review Technique
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 9 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosMotivacao
Caminho HamiltonianoBiologia ComputacionalPERT: Program Evaluation and Review Technique
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 9 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosMotivacao
Caminho HamiltonianoBiologia ComputacionalPERT: Program Evaluation and Review Technique
www.fmnh.org and www.connect.in.comSusanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 9 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Dois problemas relacionadosMotivacao
Caminho HamiltonianoBiologia ComputacionalPERT: Program Evaluation and Review Technique
www.rff.comSusanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 9 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
O problema do caminho mais longo
Problema
Encontrar um caminho de comprimento maximo em G .
NP-difıcil para grafos arbitrarios.Para algumas classes especıficas de grafos existemalgoritmos polinomiais:
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 10 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
O problema do caminho mais longo
Problema
Encontrar um caminho de comprimento maximo em G .
NP-difıcil para grafos arbitrarios.Para algumas classes especıficas de grafos existemalgoritmos polinomiais:
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 10 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
O problema do caminho mais longo
Problema
Encontrar um caminho de comprimento maximo em G .
NP-difıcil para grafos arbitrarios.Para algumas classes especıficas de grafos existemalgoritmos polinomiais:
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 10 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
O problema do caminho mais longo
Problema
Encontrar um caminho de comprimento maximo em G .
NP-difıcil para grafos arbitrarios.Para algumas classes especıficas de grafos existemalgoritmos polinomiais:Arvores (Dijkstra ’60)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 10 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
O problema do caminho mais longo
Problema
Encontrar um caminho de comprimento maximo em G .
NP-difıcil para grafos arbitrarios.Para algumas classes especıficas de grafos existemalgoritmos polinomiais:Arvores (Dijkstra ’60)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 10 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
O problema do caminho mais longo
Problema
Encontrar um caminho de comprimento maximo em G .
NP-difıcil para grafos arbitrarios.Para algumas classes especıficas de grafos existemalgoritmos polinomiais:Arvores (Dijkstra ’60)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 10 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
O problema do caminho mais longo
Problema
Encontrar um caminho de comprimento maximo em G .
NP-difıcil para grafos arbitrarios.Para algumas classes especıficas de grafos existemalgoritmos polinomiais:Arvores (Dijkstra ’60)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 10 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
O problema do caminho mais longo
Problema
Encontrar um caminho de comprimento maximo em G .
NP-difıcil para grafos arbitrarios.Para algumas classes especıficas de grafos existemalgoritmos polinomiais:Arvores (Dijkstra ’60)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 10 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
O problema do caminho mais longo
Problema
Encontrar um caminho de comprimento maximo em G .
NP-difıcil para grafos arbitrarios.Para algumas classes especıficas de grafos existemalgoritmos polinomiais:Arvores (Dijkstra ’60)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 10 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
O problema do caminho mais longo
Problema
Encontrar um caminho de comprimento maximo em G .
NP-difıcil para grafos arbitrarios.Para algumas classes especıficas de grafos existemalgoritmos polinomiais:Cactus (Uehara e Uno ’05)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 10 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
O problema do caminho mais longo
Problema
Encontrar um caminho de comprimento maximo em G .
NP-difıcil para grafos arbitrarios.Para algumas classes especıficas de grafos existemalgoritmos polinomiais:Cactus (Uehara e Uno ’05)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 10 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
O problema do caminho mais longo
Problema
Encontrar um caminho de comprimento maximo em G .
NP-difıcil para grafos arbitrarios.Para algumas classes especıficas de grafos existemalgoritmos polinomiais:Grafos de intervalo (Ioannidou e outros ’10)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 10 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de 2 caminhos mais longos
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 11 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de 2 caminhos mais longos
Encontrar caminhos mais longos distintos:
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 11 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de 2 caminhos mais longos
Encontrar caminhos mais longos distintos:
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 11 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de 2 caminhos mais longos
Encontrar caminhos mais longos distintos:
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 11 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de 2 caminhos mais longos
Encontrar caminhos mais longos distintos:
Sempre acontece?Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 11 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de 2 caminhos mais longos
Assercao
Quaisquer 2 caminhos mais longos se intersectam.
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 12 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de 2 caminhos mais longos
Assercao
Quaisquer 2 caminhos mais longos se intersectam.
P1 e P2: caminhos mais longosM : caminho (mınimo) que liga P1 a P2
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 12 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de 2 caminhos mais longos
Assercao
Quaisquer 2 caminhos mais longos se intersectam.
P1 e P2: caminhos mais longosM : caminho (mınimo) que liga P1 a P2
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 12 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de 2 caminhos mais longos
Assercao
Quaisquer 2 caminhos mais longos se intersectam.
P ′1: maior segmento de P1
P ′2: maior segmento de P2
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 12 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de 2 caminhos mais longos
Assercao
Quaisquer 2 caminhos mais longos se intersectam.
P = P ′1 ·M · P ′
2
‖P‖ ≥ ‖P1‖+ ‖M‖
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 12 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de caminhos mais longos
Para 2 e verdade.
E para...
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 13 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de caminhos mais longos
Para 2 e verdade.
E para...
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 13 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de caminhos mais longos
Para 2 e verdade.
E para...
Fonte: www.lunchoverip.com
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 13 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Interseccao de caminhos mais longosGallai (’66):
Problema P∞
Para qualquer grafo G , existe sempre um vertice comum atodos os caminhos mais longos?
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 14 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Primeiro exemplo
Walther (’69)
25 vertices
13 caminhos
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 15 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Perguntas
Novas perguntas, Zamfirescu (’72):
Este exemplo e minimal?
E com restricoes (planaridade, maior conectividade)?
Para que classes de grafos a propriedade e verdade?
E a interseccao de apenas alguns caminhos mais longos?
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 16 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Perguntas
Novas perguntas, Zamfirescu (’72):
Este exemplo e minimal?
E com restricoes (planaridade, maior conectividade)?
Para que classes de grafos a propriedade e verdade?
E a interseccao de apenas alguns caminhos mais longos?
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 16 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Perguntas
Novas perguntas, Zamfirescu (’72):
Este exemplo e minimal?
E com restricoes (planaridade, maior conectividade)?
Para que classes de grafos a propriedade e verdade?
E a interseccao de apenas alguns caminhos mais longos?
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 16 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Perguntas
Novas perguntas, Zamfirescu (’72):
Este exemplo e minimal?
E com restricoes (planaridade, maior conectividade)?
Para que classes de grafos a propriedade e verdade?
E a interseccao de apenas alguns caminhos mais longos?
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 16 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Perguntas
Novas perguntas, Zamfirescu (’72):
Este exemplo e minimal?
E com restricoes (planaridade, maior conectividade)?
Para que classes de grafos a propriedade e verdade?
E a interseccao de apenas alguns caminhos mais longos?
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 16 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Exemplo minimal
Walther e Zamfirescu
Apenas 12 vertices
9 caminhos
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 17 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Exemplo minimal planar
Schmitz (’75)
17 vertices
Planar
7 caminhos
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 18 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Classes especiais de grafos
Arvores
Grafos arco-circulares - Balister e outros ’04
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 19 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Classes especiais de grafos
Arvores
Grafos arco-circulares - Balister e outros ’04
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 19 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Classes especiais de grafos
Arvores
Grafos arco-circulares - Balister e outros ’04
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 19 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
3 caminhos
Em aberto:
Problema
Existe um vertice comum a quaisquer tres caminhos maislongos em G ?
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 20 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
3 caminhos
Em aberto:
Problema
Existe um vertice comum a quaisquer tres caminhos maislongos em G ?
Axenovich (’09): Grafos Exoplanares
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 20 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
3 caminhos
Em aberto:
Problema
Existe um vertice comum a quaisquer tres caminhos maislongos em G ?
Axenovich (’09): Grafos Exoplanares
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 20 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
3 caminhos
Em aberto:
Problema
Existe um vertice comum a quaisquer tres caminhos maislongos em G ?
Axenovich (’09): Grafos Exoplanares
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 20 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Um novo resultadoTeorema
Se G e exoplanar, entao existe um vertice comum a todos oscaminhos mais longos.
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 21 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
ProvaProposicao - Klavzar e Petkovsek (’90)
Existe um vertice comum a todos os caminhos mais longos emG ⇔ para todo bloco B de G , todos os caminhos mais longosque tem pelo menos uma aresta em B tem um vertice emcomum.
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 22 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
R∗
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
R∗v
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
R∗v
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
R∗v
x
y
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
R∗v
x
y
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
R∗v
x
y
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
R∗v
x
y
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
R∗v
x
yz
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
R∗v
x
yz
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Prova
R∗v
x
yz
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 23 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Conclusoes
Artigo Axenovich ’09
Resultado mais geral apresentado
Outro resultado mais geral
Problemas em aberto
“Gap” muito grande (2 a 7)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 24 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Conclusoes
Artigo Axenovich ’09
Resultado mais geral apresentado
Outro resultado mais geral
Problemas em aberto
“Gap” muito grande (2 a 7)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 24 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Conclusoes
Artigo Axenovich ’09
Resultado mais geral apresentado
Outro resultado mais geral
Problemas em aberto
“Gap” muito grande (2 a 7)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 24 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Conclusoes
Artigo Axenovich ’09
Resultado mais geral apresentado
Outro resultado mais geral
Problemas em aberto
“Gap” muito grande (2 a 7)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 24 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Conclusoes
Artigo Axenovich ’09
Resultado mais geral apresentado
Outro resultado mais geral
Problemas em aberto
“Gap” muito grande (2 a 7)
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 24 / 25
PreliminaresO problema do caminho mais longo
Interseccao de caminhos mais longosUm novo resultado
Conclusoes
Obrigada!
Susanna Rezende, Yoshiko Wakabayashi Caminhos mais longos em um grafo 25 / 25
