Ciências da computação dia 270

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

• trilha do qual Vs = V0

Caminho

• trilha que não repete vertices (apenas V0 e Vs podem ser iguais)

Ciclo

• caminho do qual V0 = Vs