Ciências da computação dia 262

Grafos

• Conjunto de elementos de um grafo são as vertices (V = A, B, C, D) e o conjunto de suas relações (E = A,C, B, D, C,B)

//dot program
graph{
  beautify=true
  layout="sfdp"

  A [color=green]
  B [color=red]
  C [color=blue]
  D [color=purple]

  A -- C
  B -- D 
  C -- B
}

Tipos de grafos

• dígrafo → grafo direcionado (com seta) (A,B é diferente de B,A, sendo assim colocarei apenas aquele que será usado no conjunto), não possui self loop (um vértice vai para ele mesmo)

• Grafo → grafo sem direção (aqui é necessário especificar tanto A,B como B,A, não que não se sabe a direção, então ambas podem ser percorridas)
• multi-grafo → há mais de um caminho entre vértices. Pode conter self-loop

• Grafo desconexo → há sub-grafos independentes