Percursos em Grafos - Conteúdo de Aula

Percuros em Grafos Prof Kennedy Lopes 4 de maio de 2022 Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 1 18 Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 2 18 Definicao Um percurso e uma sequˆencia de arestas sucessivamente adjacentes cada uma tendo uma extremidade adjacente a anteriore a outra a subsequente Percurso fechado A ultima aresta e adjacente a primeira Percurso aberto Caso contrario Comprimento de um percurso Numero de arestas por ele utilizado Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 3 18 Definicao Um percurso e uma sequˆencia de arestas sucessivamente adjacentes cada uma tendo uma extremidade adjacente a anteriore a outra a subsequente Percurso fechado A ultima aresta e adjacente a primeira Percurso aberto Caso contrario Comprimento de um percurso Numero de arestas por ele utilizado Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 3 18 Definicao Um percurso e uma sequˆencia de arestas sucessivamente adjacentes cada uma tendo uma extremidade adjacente a anteriore a outra a subsequente Percurso fechado A ultima aresta e adjacente a primeira Percurso aberto Caso contrario Comprimento de um percurso Numero de arestas por ele utilizado Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 3 18 Definicao Um percurso e uma sequˆencia de arestas sucessivamente adjacentes cada uma tendo uma extremidade adjacente a anteriore a outra a subsequente Percurso fechado A ultima aresta e adjacente a primeira Percurso aberto Caso contrario Comprimento de um percurso Numero de arestas por ele utilizado Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 3 18 Tipos de Percurso Simples Sem repeticao de arestas Elementar Nao repete vertices nem arestas Ciclo Repeticao do ultimo vertices Abrangente Inclui todos os vertices e arestas do grafo Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 4 18 Tipos de Percurso Simples Sem repeticao de arestas Elementar Nao repete vertices nem arestas Ciclo Repeticao do ultimo vertices Abrangente Inclui todos os vertices e arestas do grafo Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 4 18 Tipos de Percurso Simples Sem repeticao de arestas Elementar Nao repete vertices nem arestas Ciclo Repeticao do ultimo vertices Abrangente Inclui todos os vertices e arestas do grafo Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 4 18 Tipos de Percurso Simples Sem repeticao de arestas Elementar Nao repete vertices nem arestas Ciclo Repeticao do ultimo vertices Abrangente Inclui todos os vertices e arestas do grafo Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 4 18 Tipos de Percurso Simples Sem repeticao de arestas Elementar Nao repete vertices nem arestas Ciclo Repeticao do ultimo vertices Abrangente Inclui todos os vertices e arestas do grafo Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 4 18 Conexidade de Grafos Duas arestas u e v estao conexas conectadas se existir um caminho que entre u e v no grafo G O grafo G e dito conexo se existir entre quaisquer dois pares de vertices existir um caminho entre eles Relacoes de equivalˆencia Reflexiva Existe um caminho entre uu Simetrica Se existe um caminho de uv entao existe um caminho de vu Transitivo Se existe um caminho de ut e tv entao existe um caminho de uv Um Grafo pode ser desconexo mas possuir componentes conexas Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 5 18 Conexidade de Grafos Duas arestas u e v estao conexas conectadas se existir um caminho que entre u e v no grafo G O grafo G e dito conexo se existir entre quaisquer dois pares de vertices existir um caminho entre eles Relacoes de equivalˆencia Reflexiva Existe um caminho entre uu Simetrica Se existe um caminho de uv entao existe um caminho de vu Transitivo Se existe um caminho de ut e tv entao existe um caminho de uv Um Grafo pode ser desconexo mas possuir componentes conexas Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 5 18 Conexidade de Grafos Duas arestas u e v estao conexas conectadas se existir um caminho que entre u e v no grafo G O grafo G e dito conexo se existir entre quaisquer dois pares de vertices existir um caminho entre eles Relacoes de equivalˆencia Reflexiva Existe um caminho entre uu Simetrica Se existe um caminho de uv entao existe um caminho de vu Transitivo Se existe um caminho de ut e tv entao existe um caminho de uv Um Grafo pode ser desconexo mas possuir componentes conexas Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 5 18 Conexidade de Grafos Duas arestas u e v estao conexas conectadas se existir um caminho que entre u e v no grafo G O grafo G e dito conexo se existir entre quaisquer dois pares de vertices existir um caminho entre eles Relacoes de equivalˆencia Reflexiva Existe um caminho entre uu Simetrica Se existe um caminho de uv entao existe um caminho de vu Transitivo Se existe um caminho de ut e tv entao existe um caminho de uv Um Grafo pode ser desconexo mas possuir componentes conexas Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 5 18 Conexidade de Grafos Duas arestas u e v estao conexas conectadas se existir um caminho que entre u e v no grafo G O grafo G e dito conexo se existir entre quaisquer dois pares de vertices existir um caminho entre eles Relacoes de equivalˆencia Reflexiva Existe um caminho entre uu Simetrica Se existe um caminho de uv entao existe um caminho de vu Transitivo Se existe um caminho de ut e tv entao existe um caminho de uv Um Grafo pode ser desconexo mas possuir componentes conexas Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 5 18 Conexidade de Grafos Duas arestas u e v estao conexas conectadas se existir um caminho que entre u e v no grafo G O grafo G e dito conexo se existir entre quaisquer dois pares de vertices existir um caminho entre eles Relacoes de equivalˆencia Reflexiva Existe um caminho entre uu Simetrica Se existe um caminho de uv entao existe um caminho de vu Transitivo Se existe um caminho de ut e tv entao existe um caminho de uv Um Grafo pode ser desconexo mas possuir componentes conexas Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 5 18 Conexidade de Grafos Duas arestas u e v estao conexas conectadas se existir um caminho que entre u e v no grafo G O grafo G e dito conexo se existir entre quaisquer dois pares de vertices existir um caminho entre eles Relacoes de equivalˆencia Reflexiva Existe um caminho entre uu Simetrica Se existe um caminho de uv entao existe um caminho de vu Transitivo Se existe um caminho de ut e tv entao existe um caminho de uv Um Grafo pode ser desconexo mas possuir componentes conexas Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 5 18 Conexidade de Grafos Duas arestas u e v estao conexas conectadas se existir um caminho que entre u e v no grafo G O grafo G e dito conexo se existir entre quaisquer dois pares de vertices existir um caminho entre eles Relacoes de equivalˆencia Reflexiva Existe um caminho entre uu Simetrica Se existe um caminho de uv entao existe um caminho de vu Transitivo Se existe um caminho de ut e tv entao existe um caminho de uv Um Grafo pode ser desconexo mas possuir componentes conexas Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 5 18 Grafo Euleriano Um grafo conexo G e Euleriano se existir uma trilha fe chada que inclua todas as arestas de G Esta caminho e chamada de caminho Euleriana Exemplos Problema do Domino E possıvel com as pedras de um Jogo de Domino formar um anel Problema do Explorador Um explorador deseja conhecer todas as estradas entre algumas cidades E possıvel encontrar um passeio que use cada estrada exatamente uma vez e retorne ao ponto de partida Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 6 18 Grafo Euleriano Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 7 18 Grafo Euleriano Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 8 18 Grafo Hamiltoniano Um grafo G conexo e Hamiltoniano se existir um ciclo que inclui todo vertice de G Tal ciclo e dito Ciclo Hamiltoni ano Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 9 18 Grafo Hamiltoniano Um grafo G conexo e Hamiltoniano se existir um ciclo que inclui todo vertice de G Tal ciclo e dito Ciclo Hamiltoni ano Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 10 18 Grafo Hamiltoniano Exemplos Um viajante deseja visitar algumas cidades E possıvel encontrar um passeio que atravesse cada cidade exatamente uma vez e retorne a cidade inicial Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 11 18 Grafo Hamiltoniano Exemplos Um viajante deseja visitar algumas cidades E possıvel encontrar um passeio que atravesse cada cidade exatamente uma vez e retorne a cidade inicial Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 11 18 Grafo Hamiltoniano Os grafos abaixo sao Hamiltonianos Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 12 18 Grafo Hamiltoniano Os grafos abaixo sao Hamiltonianos Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 12 18 Grafo Hamiltoniano Os grafos abaixo sao Hamiltonianos Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 12 18 Grafo Hamiltoniano Os grafos abaixo sao Hamiltonianos Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 12 18 Grafo Hamiltoniano Consideracoes lFatoriais altos calculados pela estimativa de Stirling n 2mn 2 Grafo Hamiltoniano Consideracoes m E mais dificil verificar convencer alguém que o grafo é naoHamiltoniano do que é Hamiltoniano lFatoriais altos calculados pela estimativa de Stirling n 2mn 2 Grafo Hamiltoniano Consideracoes m E mais dificil verificar convencer alguém que o grafo é naoHamiltoniano do que é Hamiltoniano m Nao existe um algoritmo eficiente para verificar que um grafo é hamiltoniano Talvez nao exista lFatoriais altos calculados pela estimativa de Stirling n 2mn 2 Grafo Hamiltoniano Consideracoes m E mais dificil verificar convencer alguém que o grafo é naoHamiltoniano do que é Hamiltoniano m Nao existe um algoritmo eficiente para verificar que um grafo é hamiltoniano Talvez nao exista m E necessario comparar n1 percursos de um grafo para determinar se é hamiltoniano 1Fatoriais altos calculados pela estimativa de Stirling n 2mn 2 Grafo Hamiltoniano Consideracoes m E mais dificil verificar convencer alguém que o grafo é naoHamiltoniano do que é Hamiltoniano m Nao existe um algoritmo eficiente para verificar que um grafo é hamiltoniano Talvez nao exista m E necessario comparar n1 percursos de um grafo para determinar se é hamiltoniano m Uma vez incluido um vértice todas as arestas a ele incidentes e que nao foram inseridas no circuito podem ser desconsideradas 1Fatoriais altos calculados pela estimativa de Stirling n 2mn 2 Percurso em Grafos Os percursos em arvores sao casos particulares de percursos em Grafos Busca em profundidade Visita os nos filhos antes de visitar os irmaos Visita os nos irmaos antes de visitar os nos filhos Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 14 18 Percurso em Grafos Os percursos em arvores sao casos particulares de percursos em Grafos Busca em profundidade Visita os nos filhos antes de visitar os irmaos Visita os nos irmaos antes de visitar os nos filhos Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 14 18 Percurso em Grafos Os percursos em arvores sao casos particulares de percursos em Grafos Busca em profundidade Visita os nos filhos antes de visitar os irmaos Visita os nos irmaos antes de visitar os nos filhos Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 14 18 Percurso em Profundidade Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 15 18 Percurso em Profundidade Caracterısticas Implementa um pilha explicitamente ou por recursao Visita os vertices adjacentes em uma ordem particular Complexidade Utilizando lista de adjacˆencia OV A Grafos densos OV 2 Matriz de adjacˆencia OV 2 Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 16 18 Percurso em Profundidade Caracterısticas Implementa um pilha explicitamente ou por recursao Visita os vertices adjacentes em uma ordem particular Complexidade Utilizando lista de adjacˆencia OV A Grafos densos OV 2 Matriz de adjacˆencia OV 2 Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 16 18 Percurso em Profundidade Caracterısticas Implementa um pilha explicitamente ou por recursao Visita os vertices adjacentes em uma ordem particular Complexidade Utilizando lista de adjacˆencia OV A Grafos densos OV 2 Matriz de adjacˆencia OV 2 Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 16 18 Percurso em Profundidade Caracterısticas Implementa um pilha explicitamente ou por recursao Visita os vertices adjacentes em uma ordem particular Complexidade Utilizando lista de adjacˆencia OV A Grafos densos OV 2 Matriz de adjacˆencia OV 2 Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 16 18 Percurso em Profundidade Caracterısticas Implementa um pilha explicitamente ou por recursao Visita os vertices adjacentes em uma ordem particular Complexidade Utilizando lista de adjacˆencia OV A Grafos densos OV 2 Matriz de adjacˆencia OV 2 Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 16 18 Percurso em Profundidade Caracterısticas Implementa um pilha explicitamente ou por recursao Visita os vertices adjacentes em uma ordem particular Complexidade Utilizando lista de adjacˆencia OV A Grafos densos OV 2 Matriz de adjacˆencia OV 2 Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 16 18 Percurso em Largura Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 17 18 Percurso em Largura Caracterısticas Implementa uma fila Os vertices sao visitados em nıvel semelhante a uma arvore Complexidade Utilizando lista de adjacˆencia OV A Grafos densos OV 2 Matriz de adjacˆencia OV 2 Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 18 18 Percurso em Largura Caracterısticas Implementa uma fila Os vertices sao visitados em nıvel semelhante a uma arvore Complexidade Utilizando lista de adjacˆencia OV A Grafos densos OV 2 Matriz de adjacˆencia OV 2 Prof Kennedy Lopes Percuros em Grafos 4 de maio de 2022 18 18