Ciências da computação dia 266
Graus (d)
- grau de um vértice → número de arestas incidentes a ele
- grau do grafo(grau máximo) → maior grau dos vertices
- grau de vertices isolados é 0 (também chamado só de isolado)
- d(v) = 1 → chamado de pendente, folha ou terminal
- menor grau do grafo é chamado de grau mínimo e é representado por δ(G)
- maior grau de um grafo é chamado de grau máximo e é representado por Δ(G)
nesse exemplo, Δ(G) = 3 e δ(G)=1
- para grafos direcionados, temos graus de entrada e saída
- graus de entrada(din)→ quantas arestas estão entrando no vértice
- graus de saía(dout) → quantas arestas saem do vértice
nesse caso, din(B) = 2 e dout(B) = 0
Problema de Königsberg
- problema que deu origem aos grafos
- problema das sete pontes
- passar por todas as pontes sem repetir nenhuma e voltar para o ponto inicial
Grafos
- por padrão um grafo não é direcionado
- para grafos não direcionados, um loop conta-se como duas arestas
- para grafos não direcionados com self-loop, conta-se como um multi-grafo (d(A) = 2)
- em multi-grafos, dizemos que cada aresta é paralela
- a ordem de um grafo é o número de vértices que ele possui
- em grafos direcionados, um self-loop representa um vértice de entrada e um de saída
