Baixe o app para aproveitar ainda mais
Prévia do material em texto
Grafos Escola de Ciência e Tecnologia Grafos 1 Miguel Carvalho Escola de Ciência e Tecnologia Curso: INFORMÁTICA Problemas do Cotidiano Redes Sociais GPS Para o correio. Para Viajantes. Disciplina:ESD2 2 Para Viajantes. Pesquisas Biológicas. Distribuição de Tarefas. Recomendações Engarrafamento. Escola de Ciência e Tecnologia Curso: INFORMÁTICA Um grafo é formado por conjunto de vértices (nó) e arestas. Teoria de GrafosTeoria de GrafosTeoria de GrafosTeoria de Grafos Disciplina:ESD2 3 vértices (nó) e arestas. Nos computadores um Grafo é normalmente representado por sua matriz de adjacências. Escola de Ciência e Tecnologia Curso: INFORMÁTICA Teoria de GrafosTeoria de GrafosTeoria de GrafosTeoria de Grafos Conecta elementos. Representado por nó(vértices) e arestas. Possui diversas aplicações reais. Disciplina:ESD2 Possui diversas aplicações reais. G(V,E). Pode ser direcionado ou não direcionado. Grafo Trivial Escola de Ciência e Tecnologia Curso: INFORMÁTICA Teoria de GrafosTeoria de Grafos-- GrafoGrafoTeoria de GrafosTeoria de Grafos-- GrafoGrafo V3 Disciplina:ESD2 V1 V2 Grafo Trivial Escola de Ciência e Tecnologia Curso: INFORMÁTICA Teoria de GrafosTeoria de Grafos-- MultiMulti--GrafoGrafoTeoria de GrafosTeoria de Grafos-- MultiMulti--GrafoGrafo V3 Disciplina:ESD2 V1 V2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Teoria dos GrafosTeoria dos Grafos-- LaçoLaçoTeoria dos GrafosTeoria dos Grafos-- LaçoLaço V3 Disciplina:ESD2 V1 V2 V1 V3 V2 Laço Escola de Ciência e Tecnologia Curso: INFORMÁTICA ConceitosConceitos-- Matriz de AdjacênciasMatriz de AdjacênciasConceitosConceitos-- Matriz de AdjacênciasMatriz de Adjacências V3 Disciplina:ESD2 V1 V2 V3 V1 0 1 1 V2 1 0 0 V3 1 0 0 V1 V2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA ConceitosConceitos--CaminhoCaminhoConceitosConceitos--CaminhoCaminho Disciplina:ESD2 Caminho - seqüência de vértices v1...vj Diâmetro - maior caminho do grafo Escola de Ciência e Tecnologia Curso: INFORMÁTICA ConceitosConceitos--CaminhoCaminhoConceitosConceitos--CaminhoCaminho Disciplina:ESD2 Caminho - seqüência de vértices v1...vj Diâmetro - maior caminho do grafo Escola de Ciência e Tecnologia Curso: INFORMÁTICA ConceitosConceitos--CaminhoCaminhoConceitosConceitos--CaminhoCaminho Disciplina:ESD2 Caminho - seqüência de vértices v1...vj Diâmetro - maior caminho do grafo Escola de Ciência e Tecnologia Curso: INFORMÁTICA ConceitosConceitos--CicloCicloConceitosConceitos--CicloCiclo Disciplina:ESD2 Ciclo - seqüência de vértices v1...vj, tal que v1= vj. Escola de Ciência e Tecnologia Curso: INFORMÁTICA ConceitosConceitos--CicloCicloConceitosConceitos--CicloCiclo Disciplina:ESD2 Obs.: *Acíclico –grafo que não possui ciclo* Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– Comprimento de um caminhoComprimento de um caminhoConceitos Conceitos –– Comprimento de um caminhoComprimento de um caminho Disciplina:ESD2 Comprimento = 3 Escola de Ciência e Tecnologia Curso: INFORMÁTICA ConceitosConceitos--Grau de um nóGrau de um nóConceitosConceitos--Grau de um nóGrau de um nó d=2 d=1 Disciplina:ESD2 Grau máximo = vértice com maior grau d=1 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos -- TriângulosTriângulosConceitos Conceitos -- TriângulosTriângulos Disciplina:ESD2 Ciclo de tamanho 3 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos -- CompletosCompletosConceitos Conceitos -- CompletosCompletos K3 K2 Disciplina:ESD2 Possuem os vértices possuem todas as arestas possíveis Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos -- RegularRegularConceitos Conceitos -- RegularRegular 2-Regular 1-Regular Disciplina:ESD2 Todos os vértices possuem o mesmo grau. Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos -- PonderadoPonderadoConceitos Conceitos -- PonderadoPonderado 10 20 55 Disciplina:ESD2 As arestas possuem peso 40 50 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– Grafos DirecionadosGrafos DirecionadosConceitos Conceitos –– Grafos DirecionadosGrafos Direcionados Sumidouro Disciplina:ESD2 Fonte Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– SubgrafoSubgrafoConceitos Conceitos –– SubgrafoSubgrafo Disciplina:ESD2 subgrafo Clique – Subgrafo completo Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– IsomorfismoIsomorfismoConceitos Conceitos –– IsomorfismoIsomorfismo a b f e Disciplina:ESD2 dc hg Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– BipartidoBipartidoConceitos Conceitos –– BipartidoBipartido Disciplina:ESD2 Um grafo é bipartido se somente se não possui ciclo impar. Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– ConexoConexoConceitos Conceitos –– ConexoConexo Disciplina:ESD2 Conexo – existe um caminho entre todos os pares de vértices. Desconexo – grafo não conexo. Biconexo - para qualquer dois vértices existe dois caminhos distintos entre eles. Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– ÁrvoresÁrvoresConceitos Conceitos –– ÁrvoresÁrvores �Grafo Conexo �Acíclico �V = E +1 Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– ConexoConexoConceitos Conceitos –– ConexoConexo Disciplina:ESD2 Articulação – vértices que quando removido desconecta o grafo. Ponte - aresta que quanto removida desconecta o Grafo. Em uma árvore todas as arestas são pontes. Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– EulerianoEulerianoConceitos Conceitos –– EulerianoEuleriano Disciplina:ESD2 Passa por cada arestas somente uma vez. Um grafo é euleriando se somente se possuir todos os vértices com grau par Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– HamiltonianoHamiltonianoConceitos Conceitos –– HamiltonianoHamiltoniano Disciplina:ESD2 Passa por cada vértice um única vez. Hamiltoniano – condição necessária não possuir articulação. Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– ColoraçãoColoraçãoConceitos Conceitos –– ColoraçãoColoração Disciplina:ESD2 Coloração Própria de vértices. Vértices adjacentes não podem possuir a mesma cor. Em um grafo bipartido é possível colorir com duas cores. Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– EmparelhamentoEmparelhamentoConceitos Conceitos –– EmparelhamentoEmparelhamento Disciplina:ESD2 Arestas de Emparelhamento Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– EmparelhamentoEmparelhamentoConceitos Conceitos –– EmparelhamentoEmparelhamento e1 e2 e3 e4 Trabalhadores Disciplina:ESD2 Trabalhadores e Tarefas t2t1 t4t3 Tarefas Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– PlanaridadePlanaridadeConceitos Conceitos –– PlanaridadePlanaridade Disciplina:ESD2 Podem ser desenhados em um plano e uma esfera sem cruzamento de arestas. Escola de Ciência e Tecnologia Curso: INFORMÁTICA Conceitos Conceitos –– BuscasBuscasConceitos Conceitos –– BuscasBuscas A B Disciplina:ESD2 Largura Profundidade Algoritmo de Dijkstra *Algoritmo Guloso* CD Escola de Ciência e Tecnologia Curso: INFORMÁTICA Onde estão?Onde estão?Onde estão?Onde estão? Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Onde estão?Onde estão?Onde estão?Onde estão? Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Onde estão?Onde estão?Onde estão?Onde estão? Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Onde estão?Onde estão?Onde estão?Onde estão? Disciplina:ESD2 Saber quem está com você!!! Escola de Ciência e Tecnologia Curso: INFORMÁTICA Onde estão?Onde estão?Onde estão?Onde estão? Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICAOnde estão?Onde estão?Onde estão?Onde estão? Disciplina:ESD2 Análise de Obesidade Escola de Ciência e Tecnologia Curso: INFORMÁTICA Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise Disciplina:ESD2 Escola de Ciência e Tecnologia Curso: INFORMÁTICA Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise Disciplina:ESD2 Web Escola de Ciência e Tecnologia Curso: INFORMÁTICA Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise IA Disciplina:ESD2 IA Escola de Ciência e Tecnologia Curso: INFORMÁTICA Outros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de AnáliseOutros Trabalhos de Análise Banco de NoSQL Disciplina:ESD2 Banco de Dados
Compartilhar