Tipos Grafos - Resumo

Grafos

G(V,A)

Vértices = nós

Simétrico = vértices ligados com linhas normais

Não simétrico = com setas indicando

Ordem = nº de vértices

Em grafos simples quando 2 vértices são ligados por uma aresta eles são adjacentes

Pode ser dirigida: sucessor e antecessor

Grau = nº de arestas ligadas a um vértice

Grafo dirigido: grau de emissão (nº de arcos q partem de um vértice), grau de recepção (nº de arcos q chegam a um vértice)

Fonte = grau de recepção = 0

Sumidouro = grau de emissão = 0

Laço = quando um vértice se relaciona com ele mesmo

Grafo regular = quando todos os vértices tem o mesmo grau(regular -3)

Grafo completo = quando há uma aresta para cada par de vértice (regular n-1)

Grafo bipartido = quando pode separar os grafos em 2 grupos

Grafo bipartido completo = quando todos os vértices de um grupo se liga a todos de outro

Grafo rotulado = quando o vértice ou aresta estiver associado a um rotulo

Grafo valorado = quando as arestas possuem valores

Multigrafo = quando possui múltiplas arestas entre os pares de vértices

Subgrafo = quando um grafo esta contido em outro

Hipergrafo = quando possui 3 vértices para se ligarem

Cadeia = sequência de arestas adjacentes que ligam 2 vértices, elementar quando não passa pelo mesmo vértice, simples quando não passa pela mesma aresta, comprimento = nº de arestas

Caminho = (somente grafos orientados) cadeia onde todos os arcos possuem a msma orientação

Ciclo = cadeia fechada ( vértice inicial = final)

Circuito = caminho simples e fechado

Fecho transitivo direto = é o conjunto de todos os vértices que podem ser atingidos por algum caminho iniciado em v

Fecho transitivo inverso = é o conjunto de todos os vértices a partir dos quais se pode atingir v por algum caminho.

Grafo conexo = quando há pelo menos uma cadeia ligando cada par de vértices

Grafo desconexo = quando há pelo menos um par de vértices que não está ligado por nenhuma cadeia

Grafo fortemente conexo = (orientado) se cada par de vértices participa de um circuito

Componente fortemente conexa = quando um grafo é formado por pelo menos 2 subgrafos fortemente conexos

Vértice de corte = quando a remoção de um vértice provoca uma redução na conexidade do grafo

Ponte = quando a remoção de uma