Anúncios
1
Grafo Conexo
todos os vértices têm o mesmo grau (número de arestas).
possui múltiplas arestas entre dois mesmos vértices.
há caminho entre qualquer par de vértices
todos os vértices se conectam entre si. Arestas = n(n-1)/2.
2
Multigrafo
possui múltiplas arestas entre dois mesmos vértices.
mesmo número de vértices e arestas, e conexões semelhantes (estrutura equivalente, apesar de aparência diferente).
há caminho entre qualquer par de vértices.
não possui ciclos (caminhos fechados).
3
Grafo Acíclico:
não possui ciclos (caminhos fechados).
todos os vértices têm o mesmo grau (número de arestas).
todos os vértices se conectam entre si. Arestas = n(n-1)/2.
há caminho entre qualquer par de vértices.
4
Árvore
grafo conexo e acíclico – só há um caminho entre dois vértices.
todos os vértices têm o mesmo grau (número de arestas).
há caminho entre qualquer par de vértices.
mesmo número de vértices e arestas, e conexões semelhantes (estrutura equivalente, apesar de aparência diferente).
5
Grafo Regular
todos os vértices têm o mesmo grau (número de arestas).
todos os vértices se conectam entre si. Arestas = n(n-1)/2.
há caminho entre qualquer par de vértices.
vértices divididos em dois conjuntos, todos os vértices de um conjunto se conectam com todos do outro.
6
Grafo Completo
possui múltiplas arestas entre dois mesmos vértices.
todos os vértices se conectam entre si. Arestas = n(n-1)/2.
há caminho entre qualquer par de vértices.
não possui ciclos (caminhos fechados).
7
Grafo Bipartido Completo
todos os vértices se conectam entre si. Arestas = n(n-1)/2.
grafo conexo e acíclico – só há um caminho entre dois vértices.
mesmo número de vértices e arestas, e conexões semelhantes (estrutura equivalente, apesar de aparência diferente).
vértices divididos em dois conjuntos, todos os vértices de um conjunto se conectam com todos do outro.
8
Grafo Isomorfo
todos os vértices têm o mesmo grau (número de arestas).
mesmo número de vértices e arestas, e conexões semelhantes (estrutura equivalente, apesar de aparência diferente).
possui múltiplas arestas entre dois mesmos vértices.
não possui ciclos (caminhos fechados).
9
Ciclo (ou Circuito):
aminho fechado que passa por todos os vértices uma única vez.
Caminho fechado que passa por todas as arestas uma única vez.
passa por todas as arestas uma única vez.
Caminho fechado que começa e termina no mesmo vértice, sem repetir vértices (exceto o inicial).
10
Ciclo Euleriano
Caminho fechado que começa e termina no mesmo vértice, sem repetir vértices (exceto o inicial).
caminho fechado que passa por todos os vértices uma única vez.
visita todos os vértices uma única vez.
Caminho fechado que passa por todas as arestas uma única vez.
