Resumo | Teoria dos Grafos

Prévia do material em texto

Teoria dos grafos 
Grafo = estruturas matemáticas que permitem codificar relacionamentos entre pares de 
objetos 
Objetos = vértices (ou nós) do grafo 
Relacionamentos = suas arestas 
 
Grafo simples = não possuem múltiplas arestas e laços 
 
Multigrafo = é como um gráfico, mas pode conter múltiplas arestas entre dois vértices, 
bem como um único aro de aresta (que é uma aresta de um vértice para si mesmo) 
 
 
 
grafos dirigidos = as arestas são pares ordenados de vértice. 
Saindo de um em direção ao outro, mesmo que ambos sejam o mesmo vértice. 
 
 
 
grafos não dirigidos = não direcionados. As relações representadas pelas arestas não têm 
sentido definido. As arestas podem ser seguidas em qualquer direção. 
 
comprimento = número de arestas 
 
ciclo = quando, a partir de um determinado vértice, pode-se percorrer algum caminho que 
nos leve a esse mesmo vértice. 
 
Grafo não direcionado conexo (ou conectado) = se cada par de vértice nele estiver 
conectado por um caminho 
 
Grafo dirigido fortemente conexo = se existir um caminho entre qualquer par de vértices 
no grafo 
 
Árvore = Grafo acíclico, conexo, não-dirigido 
 
No caso de grafos dirigidos, há dois tipos de graus de vértice: • Grau de saída: número de 
arestas que saem do vértice • Grau de entrada: número de arestas que chegam no vértice. • 
Então o grau do vértice é a soma do grau de entrada, menos o de saída.