Grafos

2598 palavras 11 páginas
Exibir mais
Algoritmos em Grafos: Busca em Profundidade
Letícia Rodrigues Bueno
UFABC

Problema 1: Ordenação Topológica
• grafos direcionados acíclicos: usados para indicar

precedências entre eventos;

Problema 1: Ordenação Topológica
• grafos direcionados acíclicos: usados para indicar

precedências entre eventos;
• ordenação topológica: ordenação linear tal que arestas

orientadas sigam da esquerda para direita (pode haver várias);

Problema 1: Ordenação Topológica
• grafos direcionados acíclicos: usados para indicar

precedências entre eventos;
• ordenação topológica: ordenação linear tal que arestas

orientadas sigam da esquerda para direita (pode haver várias);
Socks Shoes Watch

Underwear

Pants

Suit

Belt Tie

Shirt

Problema 1: Ordenação Topológica
• grafos direcionados acíclicos: usados para indicar

precedências entre eventos;
• ordenação topológica: ordenação linear tal que arestas

orientadas sigam da esquerda para direita (pode haver várias);
Socks Shoes Watch

Underwear

Pants

Suit

Belt Tie

Shirt

Socks

Underwear

Pants

Shoes

Watch

Shirt

Belt

Tie

Suit

Busca em Profundidade (DFS - Depth-First Search)

Como encontrar uma ordenação topológica em um grafo direcionado acíclico?

Busca em Profundidade (DFS - Depth-First Search)

Como encontrar uma ordenação topológica em um grafo direcionado acíclico? Usaremos a busca em profundidade!

Busca em Profundidade (DFS - Depth-First Search)

a b g f c d e

Busca em Profundidade (DFS - Depth-First Search)

a b g f c d e

1

a

Busca em Profundidade (DFS - Depth-First Search)

a b g f c d e

1 2

b a

Busca em Profundidade (DFS - Depth-First Search)

a b g f c d e

1 2 3

c b a

Busca em Profundidade (DFS - Depth-First Search)

a b g f c d e

1 2 3 4

d c b a

Busca em Profundidade (DFS - Depth-First Search)

a b g f c d e

1 2 3 4 5

e d c b a

Busca em Profundidade (DFS - Depth-First Search)

a b g f c d e

1 2 3 4 5

e d c b a

Busca em Profundidade (DFS - Depth-First Search)

a b g
6

1 2 3 4 5

c

Relacionados

  • Grafos
    272 palavras | 2 páginas

    Introdução aos Grafos Introdução aos Grafos Introdução aos Grafos Introdução aos Grafos Introdução aos Grafos Introdução aos Grafos Introdução aos Grafos Introdução aos Grafos Introdução aos Grafos Introdução aos Grafos Introdução aos Grafos Introdução aos Grafos Introdução aos Grafos Introdução aos Grafos Teorema sobre Isomorfismo de Grafos Simples 1 -Dois grafos simples (N1, A1, g1) e (N2, A2, g2) são isomorfos se existem bijeções f:N1 → N2….

    exibir mais
  • Grafos
    4071 palavras | 17 páginas

    DCC111 – Matemática Discreta UFMG/ICEx/DCC Lista de Exercícios 9: Soluções Grafos 2o Semestre de 2015 Ciências Exatas & Engenharias 1. O grafo de interseção de uma coleção de conjuntos A1 , A2 , . . . , An é o grafo que tem um vértice para cada um dos conjuntos da coleção e tem uma aresta conectando os vértices se esses conjuntos têm uma interseção não vazia. Construa o grafo de interseção para as seguintes coleções de conjuntos. (a) A1 A2 A3 A4 A5 = = = = = {0, 2, 4, 6, 8} {0, 1, 2, 3, 4}….

    exibir mais
  • grafos
    819 palavras | 4 páginas

    GRAFOS Não é o objecto para espetar a comida… O que são grafos? Em matemática e em ciências informáticas, grafo é o objecto básico de estudo da teoria dos grafos. Um grafo consiste num conjunto finito de pontos (vértices) e um conjunto finito de arestas, e cada uma destas arestas liga dois vértices (não necessariamente distintos). Um grafo G(V,A) é definido pelo par de conjuntos V e A, onde: V - conjunto não vazio: os vértices ou nodos do grafo; A - conjunto de pares ordenados: a=(v….

    exibir mais
  • Grafos
    626 palavras | 3 páginas

    Grafos - uma aplicação da álgebra das matrizes A teoria dos grafos é uma área da matemática aplicada que envolve matrizes, principalmente na representação de circuitos e redes de comunicação. É o objeto básico de estudo da teoria dos grafos. Tipicamente, um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por "setas". Um vértice é representado por um círculo e uma curva é….

    exibir mais
  • Grafos
    2074 palavras | 9 páginas

    Engenharia Mecânica TEORIA DOS GRAFOS Fagner Passarelli Lourenço Camila Fernanda A. Vieira Novembro 2011 TEORIA DOS GRAFOS Definição: Um grafo é uma estrutura de abstração que representa um conjunto de elementos denominados nós e suas relações de interdependência arestas. Representação Matemática: Denominando por V o conjunto de vértices da estrutura, e por A o conjunto das arestas ou ligações entre os vértices, um grafo pode ser representado por: G = (V,A). Um grafo nada mais é do que uma representação….

    exibir mais
  • Grafos
    2681 palavras | 11 páginas

    A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G(V,A), onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, chamado arestas. Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as….

    exibir mais
  • Grafos
    534 palavras | 3 páginas

    Um caminho hamiltoniano num grafo e um Caminho onde ocorrem todos os vértices do Grafo exatamente uma vez. Analogamente, um ciclo hamiltoniano ´e um ciclo que contém todos os vértices do grafo exatamente uma vez, com exceção dos vértices inicial e final que tem de coincidir. Um grafo diz-se hamiltoniano se possuir algum ciclo hamiltoniano. Se retirarmos a ultima aresta a um ciclo hamiltoniano Obtemos um caminho hamiltoniano, logo todo o grafo hamiltoniano possui caminhos hamiltonianos. No….

    exibir mais
  • Grafos
    2345 palavras | 10 páginas

    Teoria dos Grafos Exercícios Módulos 1 e 2 - Conceitos Básicos & Representação de Grafos 1) Construir uma representação geométrica do grafo G = (V,E), onde: V = {1,2,3,4,5,6} E = {(1,3), (1,4), (1,5), (2,3),(2,4),(2,5),(3,5),(4,5)} [pic] Represente-o através de suas matrizes de adjacência e de incidência. Matriz de adjacência Matriz de incidência [pic] [pic] 2) Os amigos João….

    exibir mais
  • Grafos
    989 palavras | 4 páginas

    GRAFOS Matemática Discreta - Informática Profª Me. Geiseane Rubi ? Refere-se a um método de representação de uma ideia ou conceito, por meio da ilustração ou por escrito. Tanto em MATEMÁTICA como na linguagem corrente, costuma referir-se a um diagrama usado para exibir o relacionamento entre duas grandezas. - PROBLEMAS: *RESOLUÇÃO DOS TRÊS SERVIÇOS As pontes de Königsberg Em Königsber, Alemanha, um rio que passava pela Cidade tinha uma ilha e, logo depois de passar por essa ilha se bifurcava….

    exibir mais
  • Grafos
    4295 palavras | 18 páginas

    S. Sichman Líria M. Sato Romero Tori © 2005 Módulo:Grafos 1o. Semestre 2006 GRAFOS Professores: Anna Helena Reali Costa Jaime Simão Sichman Liria Matsumoto Sato Romero Tori Autor: Liria M. Sato Versão: 1.0 Data: 22/02/06 1 Conteúdo 1. 2. 3. 4. 5. 6. 7. Grafos: histórico e conceitos Caminhos (rotas) e Ciclos Ciclo de Euler Ciclo de Hamilton Algoritmo do Caixeiro Viajante Algoritmo do Caminho Mínimo Grafos Isomorfos e Planares. PCS 2214 Fund. Eng. Comp. I 1o.Sem. / 2005 Profs: Anna….

    exibir mais

Outros Trabalhos Populares