Estudante

TEORIA DOS GRAFOS
INTRODUÇÃO, MOTIVAÇÃO E
CONCEITOS BÁSICOS
Profa. Patrícia D. L. Machado, DSC/UFCG, 2014.1

INTRODUÇÃO


Muitas situações no mundo real podem ser descritas por meio de um diagrama formado por pontos e linhas que unem estes pontos.



O objetivo é observar se dois ou mais pontos estão conectados e o padrão desta conexão.



Partindo desta observação e de propriedades gerais da Teoria dos Grafos, é possível analisar e resolver problemas de interesse. Image from http://www.24point0.com/product-reviews-and-applications/presenting-social-networking-strategies-in-powerpoint-with-24point0-products/

MOTIVAÇÃO


Grafos constituem uma forma natural e conveniente de representar relacionamentos
(arestas) entre objetos (vértices).



Modelo matemático para representação e solução de problemas:


Existenciais: Existe ...? É possível ... ?



Construção: Se ... Existe, como pode ser construído?



Enumeração: Quantos ... existem, podem ser listados?



Otimização: Existem muitos ... qual o melhor?

MOTIVAÇÃO
O PROBLEMA DE KONISBERG





Existencial: Existe uma trilha que passe por cada uma das pontes apenas uma vez?
Construção: Se esta trilha existe, como pode ser construída? Enumeração: Quantas trilhas fechadas existem? Podemos enumerar todas?
Otimização: Que trilhas representam o caminho mais curto? Figure from http://www.transtutors.com/homework-help/Discrete+Mathematics/Graph+Theory/konisberg-multigraph-bridge.aspx

MOTIVAÇÃO
PROBLEMA DAS 4 CORES



Quantas cores são necessárias para colorir um mapa de forma que países vizinhos possuam cores diferentes?
É sempre possível colorir com apenas 4 cores

Figure from http://daveagp.wordpress.com/2007/10/12/better-know-a-theorem-an-easy-chromatic-number/

Figure from http://www.leda-tutorial.org/en/unofficial/ch05s03s07.html

MOTIVAÇÃO
PROBLEMA DA COBERTURA DE TESTES


Existencial: Existe um conjunto