Ciências da computação dia 270
grafos
Grafo completo (Kn)
- todas as vertices são interligadas entre si
Subgrafo
- grafo gerado a partir de um subset do grafo original
- é dito que o grafo H é um subconjunto de G ( H ⊆ G)
- só é um subgrafo se: V(H)⊆V(G) e E(H) ⊆ E(G)
Passeio
- sequência de arestas no formato → (V0, V1), (V1, V2), (V2, V3), ...,
(Vs-1, Vs)
- sendo s o tamanho do passeio(no caso, grafo)→ total de arestas que
foram usadas ((L,M), (M, L), (L,R) → s=3)
- é permitido repetir arestas → (C, M), (M, L), (L, C), (C, M)
Trilha
- passeio com todas as arestas distintas
Trilha fechada
Caminho
- trilha que não repete vertices (apenas V0 e Vs podem ser iguais)
Ciclo
