Resumo Prova2

Grafos

Simetricos: Quando vértice A chega em B e vértive B chega em A.
Orientados ou dirigidos: grafos com flexas/direção.
Odem: Número de vértices de um grafo.
Sucessor: w sucessor de v se existe flexa de v para w.
Antecessor: v antecessor de w se existe uma flexa de v para w.
Adjascente: vértices vizinhos.
Grau de emissão: número de flechas/arestas que saem de um vértice.
Grau de recepção: número de flechas/arestas que chegam em um vértice.
Fonte: Grau de recepção igual a zero.
Sumidouro: Grau de emissão igual a zero.
Laço: Aresta relacionando um vértice a ele mesmo.
Grafo regular: todos os vértices possuem o mesmo grau.
Grafo completo: é um grafo regular e existe uma aresta para todos pares de vértices.
Grafo Bipartido: Todas arestas ligam grafos do conjunto 1 ao conjunto 2.
Grafo Bipartido Completo: cada vértice do conjunto 1 é ligado a todos os outros vértices do conjunto 2.
Grafo Rotulado: é a identificação do vértice ou aresta.
Grafo Valorado: um valor, pode ser distância, tempo, etc; entre um vértice e outro.
Cadeia: sequencia qualquer ligando dois vértices.
Cadeia Elementar: De um nodo A até B, não passa pela mesma vértice.
Cadeia Simples: De um nodo A até B, não passa pelo mesmo aresta.
Comprimento da Cadeia: número de arestas entre o nodo A até o nodo B.
Caminho: Cadeia que possui a mesma diração/orientação.
Ciclo: Cadeia Simples e fechada (vértice inicial é o mesmo final).
Circuito: Caminho simples e fechado.
Fecho Transitivo Direto: são todos os vértices que ele pode atingir, inclusive ele mesmo.
Fecho Transitivo Invertido: são todos os vértices que por algum caminho chegam no vértice desejado, inclusive ele mesmo.
Grafo Conexo: Se há ligação entre todos os vértices..
Grafo Desconexo: Pelo menos um vértice sem ligação.
Base: vértice que por algum caminho chega em qualquer outro vértice.
Anti-base: Todos os vértices podem atingir a anti-base por algum caminho.
Grafo Planar: grafo que possui ao menos uma representação sem arestas se cruzando.