(2) Introdução à Teoria dos Grafos: Afinal, o que são grafos?

Prévia do material em texto

Introdução à Teoria dos Grafos 
 
Afinal, o que são grafos? 
 
Um grafo consiste em um conjunto finito de pontos (vértices) e um conjunto finito de arestas (ou 
arcos), e cada uma destas arestas conecta dois vértices (não necessariamente distintos). Ele permite 
codificar relacionamentos entre pares de “objetos”. 
 
• Esses “objetos” podem ser: Pessoas, cidades, empresas, países, etc.; 
• E os relacionamentos: Amizade, conectividade, produções, língua falada, etc. 
 
Dessa forma, os objetos são os vértices e os relacionamentos são as arestas do grafo: 
 
 
 
Exemplo: Transporte aéreo. 
• Objeto: Cidades; 
• Relacionamentos: Voo comercial entre duas cidades. 
 
 
 
Porque estudar a Teoria dos grafos 
 
Os grafos e suas aplicações estão presentes em diversos campos de estudo, como na Física, Química, 
Biologia, Economia e Matemática, onde são estudadas suas aplicações em resistores, estrutura 
química de moléculas, energia, cadeia alimentar, crescimento populacional, rotas de tráfego aéreo e 
terrestre, modelos de contagem, etc. 
Essa gama de aplicabilidade faz com que, apesar de “antiga”, a teoria dos grafos seja constantemente 
estudada no meio acadêmico e nos setores da indústria e comércio, a fim de gerar modelos 
otimizados às suas áreas.