Teoria dos GrafosTeoria dos Grafos

Conceitos PreliminaresConceitos Preliminares

Prof. Renato Melo

Visão geral e conceitos básicos História da teoria dos grafos Componentes dos grafos Tipos básicos de grafos Representação computacional Busca

Em profundidade Em largura

Motivação Por que estudar grafos?

Importante ferramenta matemática com aplicação em diversas áreas do conhecimento

Utilizados na definição e/ou resolução de problemas

Existem centenas de problemas computacionais que empregam grafos com sucesso.

História da Teoria dos Grafos Leonhard Euler (1707-

1783), no ano de 1736, resolveu um problema na cidade de Königsberg (antiga Prússia), criando assim o primeiro registro na história referente aos grafos.

Euler criou tal estrutura para resolver o clássico problema das Sete Pontes de Königsberg.

O problema era: É possível visitar todas as partes de terra desta cidade passando por cada ponte exatamente uma vez?

História da Teoria dos Grafos

A cidade de Königsberg foi construída numa região onde haviam dois braços do Rio Pregel e uma ilha. Foram construídas sete pontes ligando diferentes partes da cidade, como mostrado na figura:

• Problema: É possível que uma pessoa faça um percurso na cidade de tal forma que inicie e volte a mesma posição passando por todas as pontes somente uma única vez?

História da Teoria dos Grafos

Apesar do problema ser uma brincadeira dos matemáticos da época, possui fundamental importância.

Euler isolou completamente a essência do problema, ficando apenas o que era importante para o pensamento em sua solução, que passou então a ser trivial.

Modelagem proposta por Euler

Todos os “pontos” de uma dada área de terra podem ser representados por um único ponto já que uma pessoa pode andar de um lado para o outro sem atravessar uma ponte.

Um ponto é conectado a outro se houver uma ponte de um lado para o outro.

História dos Grafos

Pensamento trivial de Euler: Não existe solução para o problema: Saindo de A, não é possível voltar para A passando

por todas as pontes sem utilizar a mesma ponte mais de uma vez porque existem faixas de terra que são conectadas com um número impar de pontes.

História dos Grafos

O formalismo proposto por Euler ficou mais de 100 anos sem ser utilizado, vindo a ser referenciado apenas no século XIX com os trabalhos de:

Gustav Kirchoff (circuitos elétricos) Arthur Cayley (química – desenhos de

hidrocarbonetos)

Butano

O problema das 3 casas É possível conectar os 3 serviços às

três casas sem haver cruzamento de tubulação?

A teoria dos grafos

mostra que não é

possível!

Coloração de Mapas

Quantas cores são necessárias para colorir o mapa do Brasil, sendo que estados adjacentes não podem ter a mesma cor?

Questões sobre o caminho mínimo

De forma a reduzir seus custos operacionais, uma empresa de transporte de cargas deseja oferecer aos motoristas de sua frota um mecanismo que os auxilie a selecionar o melhor caminho (o de menor distância) entre quaisquer duas cidades por ela servidas, de forma a que sejam minimizados os custos de transporte.

Modelagem com grafos Estamos interessados em objetos e nas

relações entre eles;

Quem são eles nos problemas apresentados?

Como representar graficamente?

Modelagem com grafos No problema das casas

Vértices são casas e serviços Arestas são as tubulações entre casas e serviços

No problema da coloração de mapas Vértices são estados Arestas relacionam estados vizinhos

No problema do caminho mais curto Vértices são as cidades Arestas são as ligações entre as cidades

O que são grafos? Tipicamente um grafo é representado

como: um conjunto não vazio de pontos ou vértices ligados por retas, que são chamadas de

arestas; Ferramenta de modelagem; Abstração matemática que representa

situações reais através de um diagrama.

Componentes do Grafo

Um grafo é uma estrutura matemática que contém dois tipos básicos de entidades:

Vértices Arestas

G(V,A), onde:V = {e1, e2}A = { (e1,e1), (e1,e2) }

e1 e2

G

Exemplo

G = (V, E)

V = {a,b,c,d,e}E = {{a,b},{a,c},{b,c},{b,d},{c,d},{c,e}} = { e1, e2, e4, e5, e7, e9}

a

e

b c

d

G = (V, E)

V = {a,b,c,d,e}E = {{a,b},{a,c},{b,b},{b,c},{b,d},{c,d},{c,d},{c,d},{c,e}} = { e1, e2, e3, e4, e5, e6, e7, e8, e9}

Grafo simples

Multigrafo

e1 e2

e3

e4

e5

e6e7

e8e9

Tipos básicos

Os grafos podem ser:

Dirigidos (G1) Não dirigidos (G2)

Nos grafos dirigidos, as arestas representam pares ordenados.

e1 e2

e1 e2

G1

G2

Características – Rotulado ou Valorado

Os grafos podem ser:

Rotulados (G3) Não Rotulados

Os rótulos indicam alguma característica para cada par de vértices, ou seja, para cada aresta.

BH AL370

0 0

G3

Teoria dos Grafos

Conceitos

• Dois vértices que são incidentes a uma mesma aresta são ditos adjacentes.

• Duas arestas que são incidentes a um mesmo vértice são ditas adjacentes.

u v

eu e v são adjacentes

e1 e e2 são adjacentes

ue2

e1

Teoria dos Grafos

Observação

O conceito de incidência ou adjacência

é importante para a representação

da estrutura de um grafo como um diagrama

Teoria dos Grafos

Conceitos

• O número de vértices de um grafo G é denotado por n. O valor n também é conhecido como ordem de G

• O número de arestas de um grafo é denotado por m

• Se n e m são finitos, o grafo é finito. Caso contrário é dito infinito.– Exemplo de grafo infinito: malhas

Teoria dos Grafos

Conceitos

• O número de arestas incidentes a um vértice v é denominado grau(v) e representado por d(v).

• Grau também é conhecido como valência.

a

e

b c

d

d(a) = 3d(b) = 5d(c) = 4d(d) = 2d(e) = 2

CC/EC/Mestrado Teoria dos Grafos

Conceitos

• Vértice isolado é o vértice que não possui arestas incidentes (grau nulo)

• Vértice folha ou terminal é o vértice que possui grau 1

• Vizinhos de um vértice são os vértices adjacentes a ele.

b

a

cd

e

d é um vértice folha e e é um vértice isoladob e c são vizinhos de a

Teoria dos Grafos

Conceitos

• Pares de vértices (ou de arestas) não adjacentes são denominadas independentes.

• Um conjunto de vértices (ou arestas) é independente se nenhum par de seus elementos é adjacente.

CC/EC/Mestrado Teoria dos Grafos

Exemplo

a

b c

d

f

eg

e10

e1 e2

e3

e4e5

e6e7

e8

e9

•e1 e e5 são independentes•a e d são independentes•{b,e,g} é um conjunto independente•{e1, e5 } é um conjunto independente

Algumas aplicações

As aplicações de grafos nos dias de hoje são vistas nas mais diversas áreas da ciência, por exemplo:

Mapas (localização de caminhos mínimos, alternativos, etc)

Redes de computadores (roteamento de pacotes) Teoria de Linguagens (autômatos) Química (moléculas) Física (circuitos) Otimização (fluxo em redes) Arquitetura de Computadores (Grafos planares)

Representando um grafo em um programa Que tipos de estruturas de software são

adequadas para modelar um grafo? Começando pelos nós

Geralmente é conveniente representar um nó por um objeto de uma classe de nó.

Ex:

Representação computacional: Arestas Uma abordagem diferente para

representar arestas é preferível àquela usada para árvores.

Dois métodos são comumente utilizados para grafos: Matriz de adjacência e Lista de adjacência.

Matriz de Adjacência Uma matriz de adjacência é um vetor

bidimensional no qual os elementos indicam se uma aresta está presente em dois nós. Se um grafo tem N nós, a matriz de

adjacência será uma matriz NxN. O nós são cabeçalhos tanto para linha como

para coluna.

Lista de Adjacência A lista em lista de adjacência refere-se a

uma lista encadeada. Na verdade é um vetor de listas

Cada lista individual mostra a quais nós um dado nó é adjacente.

Adicionando nós e arestas á um grafo Para adicionar um nó a um grafo, é

preciso inserir um objeto em um vetor de nó. vetorVertices[nVertices] = new Vertice(‘R’);

Uma aresta pode ser adicionada utilizando uma matriz ou lista de adjacência. Usando uma matriz: matrizAdj[1][3] = 1; matrizAdj[1][3] = 1;

A classe Grafo.java

Buscas Assuma que se tenha criado um grafo. Agora precisará de um algoritmo que

forneça uma maneira de iniciar em um nó especificado

e então se mova ao longo das arestas para outros nós.

De tal modo que ao final tenha a garantia de ter visitados todo nó conectado ao inicial.

Há duas abordagens comuns Busca em profundidade Busca em largura

Busca em Profundidade Usa uma pilha para lembrar para onde

deve ir quando atingir um ponto sem saída.

Busca em Largura Nesta busca visita-se todos os nós

adjacentes ao nó inicial e apenas então vai mais adiante.

Esse tipo de busca é usado implementando uma fila.