Ativ 1 - Introdução a teoria dos grafos

Prévia do material em texto

INTRODUÇÃO A TEORIA DOS GRAFOS 
ATIVIDADE 1 
Os grafos são ferramentas matemáticas que possibilitam o entendimento de diversas situações-problemas, permitindo que se desenvolvam soluções para várias áreas do conhecimento. A sua forma de representação, apesar de muito simples, possibilita que se tenha mais compreensão dos cenários e permite abstrair informações muito úteis. Porém, toda essa capacidade encontrada na teoria dos grafos só terá utilidade se possuir uma aplicação prática, que resolva problemas. 
Analise como um grafo de cinco nós (vértices) e arcos (arestas) pode ser representado por meio de uma tripla ordenada (N, A, g). 
Vamos definir os seguintes elementos para representar um grafo de cinco nós (vértices) e arcos (arestas) por meio de uma tripla ordenada (N, A, g):
N: Conjunto de nós (vértices) do grafo.
A: Conjunto de arcos (arestas) do grafo.
g: Função que associa a cada arco um par ordenado de nós (vértices) que ele conecta.
- Conjunto de Nós (𝑁):
Para um grafo de cinco nós, podemos ter um conjunto de nós 𝑁= {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑣5}, onde cada 𝑣𝑖​ representa um nó do grafo.
- Conjunto de Arcos (A):
Para um grafo com cinco nós, o conjunto de arcos pode ser representado por 𝐴= {𝑎1, 𝑎2, 𝑎3, 𝑎4, 𝑎5}, onde cada ai representa uma aresta do grafo. Este conjunto pode conter várias arestas, cada uma conectando dois nós diferentes.
- Função de Conexão (𝑔):
A função 𝑔 associa a cada arco do conjunto 𝐴 um par ordenado de nós que ele conecta. Por exemplo, se 𝑎1​ conecta o nó 𝑣1​ ao nó 𝑣2​, então 𝑔(𝑎1) = (𝑣1, 𝑣2). Esta função mapeia cada arco para o par de nós que ele conecta.
Portanto, a tripla ordenada (𝑁, 𝐴, 𝑔) representa completamente o grafo de cinco nós e suas conexões através de arcos. Cada nó e cada arco são identificados dentro dos conjuntos 𝑁 e 𝐴, respectivamente, e a função 𝑔 descreve como os arcos estão conectados aos nós.