GoConqr has a new look! Let us know what you think.

Flashcards

Teoria dos Grafos

guilhermeherisi Portuguese 43 cards

Matriz de adjacência (exemplo)

Cards in this deck (43)

  1. 1Emprego dos Grafos1 - Encontrar caminhos entre 2 pontos
    2 - Armazenamento de Impressões Digitais para comparações
  2. 2MultigrafoGrafo que possui mais de uma aresta entre
    um mesmo par de vértices
  3. 3LaçoAresta que parte de um Vértice para ele
    mesmo
  4. 4PseudografoGrafo com um ou mais laços
  5. 5Grafo SimplesGrafo que não é Multigrafo e nem
    Pseudografo
  6. 6Grau de um vérticeNúmero de arestas que saem ou entram em um vértice
  7. 7Caminho SimplesÉ uma sequência de vértices que são conectados por uma sequência de arestas. Cada vértice aparece apenas uma vez.
  8. 8Caminho com ciclosÉ uma sequência de vértices que são conectados por uma sequência de arestas.
    Há vértices que aparecem mais de uma vez
  9. 9CircuitoCaminho cujos primeiro e último vértices são o mesmo
  10. 10Grafo conexoExiste um caminho de qualquer vértice
    para qualquer vértice
  11. 11ÁrvoreÉ um grafo conexo sem ciclo
  12. 12Componente de um GrafoÉ um subgrafo conexo de G, tal que nenhum outro subgrafo conexo de G contém ele
  13. 13Grafo PonderadoGrafos com pesos nas arestas
  14. 14Grafo bipartido (simples)Grafo cujos vértices podem ser divididos em dois conjuntos tais que todas as arestas conectam vértices de um conjunto para outro
  15. 15Grafo bipartido completoIgual ao bipartido simples. Porém todos os vértices ligam os demais do outro conjunto. Km,n
  16. 16Grafo regularTodos os vértices possuem o
    mesmo grau.
  17. 17Vértice IsoladoÉ um vértice com nenhuma aresta incidente
  18. 18Vértice pendenteVértice com grau 1
  19. 19Grafo nuloGrafo sem nenhuma aresta
  20. 20Grafo completoPara cada par de vértices qualquer existe caminho entre eles
  21. 21Comprimento de um CaminhoÉ o número de arestas no caminho.
  22. 22Grafo aciclicoGrafo sem ciclos
  23. 23Grafo orientado fortemente conectadoSe cada um de dois vértices quaisquer é acessível a partir do outro.
  24. 24Grafo complementarSão as arestas que faltam para fazer o grafo simples ser completo.
  25. 25Grafo isomorfosCorrespondência um-para-um entre seus vértices e entre suas arestas, de maneira que as relações de incidência são preservadas
  26. 26Condições necessárias p/ ser Isomorfo1 - mesmo número de vértices
    2 - mesmo número de arestas
    3 - mesmo número de componentes
    4 - mesmo número de vértices com o mesmo grau
  27. 27Calcular quantidade de arestas de um grafo simples e completoA=n(n-1)/2
    Onde n é o número de vértices
  28. 28Complete: O número de vértices de grau ímpar......em um grafo é par
  29. 29Complete: A soma dos graus de todos os vértices de um grafo G é o......dobro do número de arestas de G
  30. 30Número minimo de arestas de um grafo simplesn vértices e k componentes é n-k
  31. 31Número máximo de arestas de um grafo simples(n-k) * (n – K + 1)/2
  32. 32Martiz de adjacencia- Mij = 1, se existe uma aresta entre os vértices i e j
    - Mij = 0, caso contrário
  33. 33Matriz de adjacência (exemplo)Matriz de adjacência (exemplo)Matriz de adjacência (exemplo)
  34. 34Lista de adjacência(exemplo)Lista de adjacência(exemplo)Lista de adjacência(exemplo)
  35. 35Grafo EulerianoÉ um grafo que visita cada aresta apenas uma vez e volta ao ponto de partida.
  36. 36Grafo Unicursal ou caminho ElerianoVisita todas as arestas apenas uma vez e não retorna ao ponto de partida.
  37. 37Propriedades Grafos EulerianosTodos os vértices precisam ter grau par
  38. 38Propriedades Grafos UnicursaisGrafo que é possível passar por todas as arestas sem repetir e sem retornar a origem. Devem ter 2 e somente 2 vértices de grau ímpar
  39. 39Grafo HamiltonianoÉ um caminho que permite passar por todos os vértices somente uma vez e retornando a origem.
  40. 40Caminho HamiltonianoÉ um caminho que permite passar por todos os vértices somente uma vez.
  41. 41Propriedades Grafo HamiltonianoNão é possível descrever um algorítimo preciso para descobrir se o grafo é Hamiltoniano.
  42. 42Algorítimos em Grafos- Busca em Largura
    - Busca em profundidade
    - Número de componentes em um grafo
    - Ordenação topológica
  43. 43Busca em amplitudeDado um vértice de origem em um grafo, a busca em amplitude explora sistematicamente as arestas até descobrir cada vértice acessível a partir da origem.

Information

Description
Flashcards on Teoria dos Grafos, created by guilhermeherisi on 20/04/2015.
Created by
guilhermeherisi
Views
26
Rating

More on Conceitos e tipos de grafos

Feedback

What is it about?

What do you think of the new look?

How do you like it?