ATIVIDADE 1 -GRA0808 INTRODUÇÃO À TEORIA DOS GRAFOS UAM 2022

Prévia do material em texto

ATIVIDADE 1 
GRA0808 – INTRODUÇÃO À TEORIA DOS GRAFOS 
UAM – BLOCO 1 1º SEMESTRE - 2022 
ENUNCIADO: 
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. 
Caro(a) aluno(a), 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). 
RESPOSTA: 
Dado um Grafo planar, grafo este com cinco nós (vértices) e arcos (arestas) conforme 
pode ser visto na figura abaixo: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Representação por meio de uma tripla ordenada (N, A, g): 
Grafos de nós de 1 à 5. 
 
N = {1; 2; 3; 4; 5} 
 
A = {a;b;c;d;e) = A = {(1, 2); (2, 3); (3, 4); (4, 5); (5,1)} 
1 2 
5 
4 
3 
e 
a 
b 
c 
d 
 
g(a)= 1-2 
g(b)=2-3 
g( c)=3-4 
g(d)=4-5 
g(e)=5-1 
 
Uma breve explicação para tripla ordenada G = (V, A, g), onde: 
G (grafo): são as representações formais dos elementos que compõem um grafo. 
V (vértices): conjuntos de nós não vazio. Dado um grafo, representado por G, onde os 
elementos do conjunto V:= V (G) são chamados de vértices de G. 
A (arestas): são os arcos encontrados entre os vértices. 
Dessa forma, denota-se os elementos de E := E(G) são chamados de arestas de G. 
g (relação V X A): são funções de associação para cada arco a um par não ordenado 
entre os nós. Denomina-se V X A := (V X A)(G) como a lei de incidência do grafo G.