Teoria dos Grafos 🌐🔗

A Teoria dos Grafos é um ramo da Matemática Discreta que estuda estruturas formadas por objetos (vértices) conectados por ligações (arestas). Ela é amplamente utilizada para modelar redes de computadores, redes sociais, mapas de estradas, circuitos elétricos, entre muitos outros.

---

🧱 Elementos Básicos de um Grafo

• Vértices (ou nós): os pontos ou objetos da estrutura (ex: cidades, computadores, pessoas).

• Arestas (ou arcos): as conexões entre os vértices (ex: estradas, cabos, amizades).

Exemplo de grafo:

A --- B
|     |
C --- D

---

🧩 Tipos de Grafos

🔸 Grafo Simples

• Não possui laços (arestas que ligam um vértice a ele mesmo).

• Não possui arestas múltiplas (entre os mesmos dois vértices).

🔸 Grafo Direcionado (Digrafo)

• As arestas têm direção, como uma rua de mão única.

• Representadas por setas (A → B)

🔸 Grafo Ponderado

• Cada aresta tem um peso ou custo (distância, tempo, etc.).

🔸 Multigrafo

• Pode ter mais de uma aresta entre os mesmos dois vértices.

---

🧮 Representações de Grafos

• Lista de Adjacência: lista de quais vértices estão conectados.

• Matriz de Adjacência: matriz binária que mostra se há conexão entre pares de vértices.

• Matriz de Incidência: indica a relação entre vértices e arestas.

---

⚙️ Conceitos Importantes

Conceito	Descrição
Grau do vértice	Número de arestas conectadas a um vértice
Caminho	Sequência de vértices conectados
Ciclo	Caminho que começa e termina no mesmo vértice
Conectividade	Um grafo é conexo se existe um caminho entre qualquer par de vértices
Árvore	Grafo conexo sem ciclos
Grafo completo	Todos os vértices estão conectados entre si
Subgrafo	Parte de um grafo original com subconjunto de vértices e arestas

---

🧠 Problemas Clássicos da Teoria dos Grafos

✅ Caminho mais curto

• Encontrar a menor rota entre dois pontos.

• Algoritmos: Dijkstra, Bellman-Ford

✅ Caminho Euleriano

• Caminho que percorre todas as arestas sem repetir.

• Um grafo tem um caminho euleriano se tiver 0 ou 2 vértices de grau ímpar.

✅ Ciclo Hamiltoniano

• Passa por todos os vértices uma única vez e retorna ao início.

✅ Árvore Geradora Mínima

• Conecta todos os vértices com o menor custo possível.

• Algoritmos: Kruskal, Prim

---

🧮 Aplicações Reais

• Google Maps / Waze: cálculo de rotas

• Redes sociais: conexões entre usuários

• Internet: roteamento de pacotes de dados

• Planejamento urbano: semáforos, ruas, pontes

• Bioinformática: redes de proteínas, DNA

• Engenharia elétrica: circuitos e fluxos

---

🛠️ Ferramentas e Softwares

• Python (bibliotecas como networkx, igraph, graph-tool)

• MATLAB

• Gephi (visualização de grafos)

• Neo4j (banco de dados orientado a grafos)

---

📌 Exemplo com Grafo Ponderado

Grafo:

     (2)
  A ----- B
   \     /
 (3)\   /(1)
     \ /
      C

Matriz de Adjacência Ponderada:

	A	B	C
A	0	2	3
B	2	0	1
C	3	1	0

---