Flashcards
Teoria dos Grafos

Cards in this deck (43)
- 1Emprego dos Grafos1 - Encontrar caminhos entre 2 pontos
2 - Armazenamento de Impressões Digitais para comparações - 2MultigrafoGrafo que possui mais de uma aresta entre
um mesmo par de vértices - 3LaçoAresta que parte de um Vértice para ele
mesmo - 4PseudografoGrafo com um ou mais laços
- 5Grafo SimplesGrafo que não é Multigrafo e nem
Pseudografo - 6Grau de um vérticeNúmero de arestas que saem ou entram em um vértice
- 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.
- 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 - 9CircuitoCaminho cujos primeiro e último vértices são o mesmo
- 10Grafo conexoExiste um caminho de qualquer vértice
para qualquer vértice - 11ÁrvoreÉ um grafo conexo sem ciclo
- 12Componente de um GrafoÉ um subgrafo conexo de G, tal que nenhum outro subgrafo conexo de G contém ele
- 13Grafo PonderadoGrafos com pesos nas arestas
- 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
- 15Grafo bipartido completoIgual ao bipartido simples. Porém todos os vértices ligam os demais do outro conjunto. Km,n
- 16Grafo regularTodos os vértices possuem o
mesmo grau. - 17Vértice IsoladoÉ um vértice com nenhuma aresta incidente
- 18Vértice pendenteVértice com grau 1
- 19Grafo nuloGrafo sem nenhuma aresta
- 20Grafo completoPara cada par de vértices qualquer existe caminho entre eles
- 21Comprimento de um CaminhoÉ o número de arestas no caminho.
- 22Grafo aciclicoGrafo sem ciclos
- 23Grafo orientado fortemente conectadoSe cada um de dois vértices quaisquer é acessível a partir do outro.
- 24Grafo complementarSão as arestas que faltam para fazer o grafo simples ser completo.
- 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
- 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 - 27Calcular quantidade de arestas de um grafo simples e completoA=n(n-1)/2
Onde n é o número de vértices - 28Complete: O número de vértices de grau ímpar......em um grafo é par
- 29Complete: A soma dos graus de todos os vértices de um grafo G é o......dobro do número de arestas de G
- 30Número minimo de arestas de um grafo simplesn vértices e k componentes é n-k
- 31Número máximo de arestas de um grafo simples(n-k) * (n – K + 1)/2
- 32Martiz de adjacencia- Mij = 1, se existe uma aresta entre os vértices i e j
- Mij = 0, caso contrário - 33Matriz de adjacência (exemplo)


- 34Lista de adjacência(exemplo)


- 35Grafo EulerianoÉ um grafo que visita cada aresta apenas uma vez e volta ao ponto de partida.
- 36Grafo Unicursal ou caminho ElerianoVisita todas as arestas apenas uma vez e não retorna ao ponto de partida.
- 37Propriedades Grafos EulerianosTodos os vértices precisam ter grau par
- 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
- 39Grafo HamiltonianoÉ um caminho que permite passar por todos os vértices somente uma vez e retornando a origem.
- 40Caminho HamiltonianoÉ um caminho que permite passar por todos os vértices somente uma vez.
- 41Propriedades Grafo HamiltonianoNão é possível descrever um algorítimo preciso para descobrir se o grafo é Hamiltoniano.
- 42Algorítimos em Grafos- Busca em Largura
- Busca em profundidade
- Número de componentes em um grafo
- Ordenação topológica - 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