Teoria dos Grafos

[bernardino]

O que é um grafo?

“São estruturas formadas por um conjunto de vértices (pontos ou elementos) não vazios e por um conjunto de arestas (retas ou linhas) que fazem alusão a uma relação binária. Ou seja, com os grafos conseguimos representar elementos e suas possíveis relações.” Sagah

“Um grafo é uma estrutura abstrata que representa um conjunto de elementos denominados vértices e suas relações de interdependência ou arestas.”
Goldbarg, E; Goldbarg, M – Grafos – Ed. Gen LTC

O que é um grafo?

É uma estrutura de dados matemática, sendo formada por um conjunto de elemento que se relacionam. Estas relações chamamos de arestas ou arcos e os elementos de vértices ou nós.

o_que_e_um_grafo.png (29.84 KiB) Exibido 10 vezes

Elementos de um grafo

• Vértices ou nós

vertices_ou_nos.png (1.27 KiB) Exibido 10 vezes

• Arestas e arcos

arestas-e-arcos.png (584 Bytes) Exibido 10 vezes

• Ligações entre os vértices

ligacoes_entre_vertices.png (5.56 KiB) Exibido 10 vezes

• Em verde temos um laço. Aresta ou arco que se relaciona um vértice a ele próprio.

vertice_a_ele_proprio.png (2.3 KiB) Exibido 10 vezes

Grafo

Representação matemática

• V é Conjunto de vértices
• E é o Conjunto de ligações entre vértices

• Logo um grafo é representado por uma ordenado:
• G = (V, E)

• Exemplos simples de como representar um grafo:
V = {A, B, C, D}
E = {(A, B), (A, C), (B, C), (C, D)}

exemplo_simples_grafo.png (14.78 KiB) Exibido 9 vezes

Quanto as ligações entre os vértices temos dois tipos:

• Grafos direcionados (orientados ou dígrafos)
• Grafos não direcionados (não orientados

Uma aresta (u, v) é dita dirigida de u para v se o par (u, v) por ordenado, com u precedendo v. Logo, (u, v) ≠ (v, u)

u_v.png (5.61 KiB) Exibido 9 vezes

• Agora uma aresta (u, v) é não dirigida se o par (u, v) não for ordenado. Logo, {u, v} = {v, u}

u_vb.png (5.61 KiB) Exibido 9 vezes

Grafo direcionado

grafo_direcionado.png (39.54 KiB) Exibido 8 vezes

Representação:

• V = {A, B, C, D, E}
• E = {(A, B), (A, C), (A, E), (B, C), (D, C), (E, A)}

Outra forma:

• xi i = XA, XB, XC, XD , XE representado os vértices
• aij i e j representado as ligações entre os vértices E = {aAB , aAC , aAE , aBC , aDC , aEA}

Grafo não direcionado

grafo_nao_direcionado.png (17.48 KiB) Exibido 8 vezes

Representação:
• V = {A, B, C, D, E}
• E = {(A, B), (A, C), (A, E), (B, C), (C, D), (E, D)}

Outra forma:
• V = {A, B, C, D}
• E = {(A- B), (A - C), (B - C), (C- D)}

• xi i = XA, XB, XC, XD , XE representado os vértices
• aij i e j representado as ligações entre os vértices E = {aAB , aAC , aAE , aBC , aDC , aDE}

Atividade

• Monte o grafo conforme representação matemática:
• V = {A, B, C, D}
• E = {(A,B), (D, B), (C, A), (A,D), (B, D), (D, A)}

Atividade

• Monte o grafo conforme representação matemática:
• V = {A, B, C, D, E}
• E = {(A,B), (B, C), (A, D), (D,C), (D, E), (C, E)}
• E = {(A,B), (D, B), (C, A), (A,D), (B, D), (D, A)}

O que podemos modelar com grafos?

grafo_redes_sociais.png (189.25 KiB) Exibido 8 vezes

• Redes sociais
• Os vértices representam uma pessoa ou perfil
• As arestas representam as conexões ou interações entre elas (curtidas, seguir, ..)
• Obter informações como identificar comunidades.

O que podemos modelar com grafos?

o_que_podemos_modelar.png (130.63 KiB) Exibido 8 vezes

Circuitos elétricos

• Os vértices representam os componentes elétricos.
• As arestas representam o caminho da corrente no circuito.
• Otimizar o circuito quanto aos uso de dispositivos e componentes.