Please enable JavaScript.
Coggle requires JavaScript to display documents.
Fundamentos de Grafos - Coggle Diagram
Fundamentos de Grafos
Definição
Definição mais formal de grafo: Um grafo G é um par ( V,E ) onde V é um conjunto finito (conjunto de vértices ou nodos) e E é uma relação binária (pares ordenados ou não) sobre V (conjunto de arestas ou arcos)
Escrevemos uv (ou vu) para uma aresta e = (u, v ). Se uv ∈ E (G ), então u e v são adjacentes ou vizinhos.
-
Se xy ∈ E (G ), então x e y são incidentes a e = xy .
Um laço (ou loop) é uma aresta cujas pontas finais são iguais. Arestas paralelas ou múltiplas arestas são arestas que tem omesmo par de pontas finais.
-
A ordem de um grafo G é dada pela cardinalidade do conjunto de vértices, ou seja, pelo número de vértices de G.
Cadeia, caminhos, ciclos e circuitos
Um caminho é uma cadeia na qual todos os arcos possuem a mesma orientação. Aplica-se, portanto, somente a grafos orientados. A seqüência de vértices (x1, x2, x5, x6, x3) é um exemplo de caminho em G11.
Um ciclo é uma cadeia simples e fechada (o vértice inicial é o mesmo que o vértice final). A seqüência de vértices (x1, x2, x3, x6, x5, x4, x1) é um exemplo de ciclo elementar em G11.
Um circuito é um caminho simples e fechado. A seqüência de vértices (x1, x2, x5, x4, x1) é um exemplo de circuito elementar em G11.
-
Uma cadeia é uma sequência qualquer de arestas adjacentes que ligam dois vértices. O conceito de cadeia vale também para grafos orientados, bastando que se ignore o sentido da orientação dos arcos. A seqüência de vértices (x6, x5, x4, x1) é um exemplo de cadeia em G11.
- Uma cadeia é dita ser elementar se não passa duas vezes pelo mesmo vértice.
- É dita ser simples se não passa duas vezes pela mesma aresta (arco).
- O comprimento de uma cadeia é o número de arestas (arcos) que a compõe.
Fecho Transitivo
O fecho transitivo direto (ftd) de um vértice v é o conjunto de todos os vértices que podem ser atingidos por algum caminho iniciando em v. O ftd do vértice x5 do grafo G17, por exemplo, é o conjunto: {x1, x2, x3, x4, x5, x6}. Note que o próprio vértice faz parte do ftd já que ele é alcançável partindo-se dele mesmo.
O fecho transitivo inverso (fti) de um vértice v é o conjunto de todos os vértices a partir dos quais se pode atingir v por algum caminho. O fti do vértice x5 do grafo G17, por exemplo, é o conjunto: {x1, x2, x4, x5, x7}. Note que o próprio vértice faz parte do fti já que dele se pode alncançar ele mesmo.
Conexidade
Um grafo G(V,A) é dito ser conexo se há pelo menos uma cadeia ligando cada par de vértices deste grafo G.
Um grafo G(V,A) é dito ser desconexo se há pelo menos um par de vértices que não está ligado por nenhuma cadeia.
Componente Conexa Um grafo G(V,A) desconexo é formado por pelo menos dois subgrafos conexos, disjuntos em relação aos vértices e maximais em relação à inclusão. Cada um destes subgrafos conexos é disto ser uma componente conexa de G.
Grafo fortemente conexo No caso de grafos orientados, um grafo é dito ser fortemente conexo (f-conexo) se todo par de vértices está ligado por pelo menos um caminho em cada sentido, ou seja, se cada par de vértices participa de um circuito. Isto significa que cada vértice pode ser alcançável partindo-se de qualquer outro vértice do grafo.
Componente fortemente conexa Um grafo G(V,A) que náo é fortemente conexo é formado por pelo menos dois subgrafos fortemente conexos, disjuntos em relação aos vértices e maximais em relação à inclusão. Cada um destes subgrafos é disto ser uma componente fortemente conexa de G, a exemplo dos subgrafos identificados por S1, S2 e S3 em G17.
Vizinhança
A vizinhança aberta de um vértice v é o conjunto de seus
vizinhos. Notação: N(v) = vizinhança aberta de v
-
Orientação
(u, v ) = (v , u) - Não Orientado
(u, v ) <> (v , u) - Orientado
Subgrafos
Um grafo H é um subgrafo de G se V (H) ⊆ V (G ) e E (H) ⊆ E (G ). Escrevemos que H ⊆ G e dizemos que G contém H.
Adjacência e Incidência
Em um grafo simples (a exemplo de G1) dois vértices v e w são adjacentes (ou vizinhos) se há uma aresta a=(v,w) em G. Está aresta é dita ser incidente a ambos, v e w
O grau de um vértice de um grafo é o número de arestas incidentes a ele, exceto que um laço em um vértice contribui duas vezes ao grau daquele vértice. O grau do vértice v é denotado por d(v). Um vértice de grau zero é dito isolado. Um vértice é dito pendente se ele tem grau 1.