Teoria dos Grafos

Profa. Alessandra Martins Coelho

fev/2014

Avaliação• 2 Provas – 30 pontos cada;• 3 Implementações – 10 pontos cada;• 1 Seminário – 10 pontos;• Listas de exercícios

– Listas não valem nota, entretanto...– as provas serão baseadas nas listas– (pequena) ajuda no final (se necessário)

Bibliografia

Paulo Oswaldo Boaventura Netto. Grafos: Teoria, modelos, algoritmos. 5ª ed. Editora Bluscher. São Paulo. 2012. ISBN: 9788521206804

http://www.blucher.com.br/livro.asp?Codlivro=04732

Paulo Oswaldo Boaventura Netto; Samuel Jurkiewicz. Grafos: Introdução e Prática. Editora Bluscher. São Paulo. 2009. ISBN: 9788521204732

http://www.blucher.com.br/livro.asp?Codlivro=06804

Biblioteca

Bibliografia

Biblioteca

Capítulo 7ZIVIANI, Nivio. Projeto de algoritmos: com implementações em Pascal e C. 3. ed. rev. e ampl.. São Paulo, SP: Cengage Learning

Marco Cesar Goldbarg; Elizabeth Goldbarg. Grafos: Conceitos, algoritmos e aplicações. Rio de Janeiro: Elsevier, 2012.

http://www.elsevier.com.br/site/produtos/Detalhe-Produto.aspx?tid=90343&seg=3&cat=274&tit=GRAFOS

Ementa

• Conceitos Básicos• Exemplos de aplicação dos modelos em

Grafos• Caminhos• Subconjunto de vértices e arestas• Coloração• Fluxo em redes• Árvores

Primeiras Ideias

Primeiras Ideias

• O que é um grafo?• Um grafo é uma estrutura representada

como um conjunto de pontos (vértices) ligados por retas (arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por setas.

Primeiras Ideias• O que é um grafo? Abstração que permite representar o

relacionamento entre pares de elementosOnde:Elementos – vértices do grafo(computadores, empresas, cidades, países,

pessoas, páginas web, etc...)Relacionamentos – arestas do grafo(conexão, distância, amizade, custo, etc...)

Primeiras Ideias

• Graficamente, aparece representado por uma figura com nós ou vértices, significando os elementos, unidos por um traço denominado aresta configurando a relação imaginada

Primeiras Ideias

• Exemplo: Tráfego Rodoviário/AéreoTransporte comercial entre cidades

Primeiras Ideias

• Matematicamente chama-se grafo a um par G=(V,A), tal que V=V(G)={v1, . . . ,vn} é o conjunto dos vértices (não vazio e finito) e A=A(G) é o conjunto das arestas ou ligações entre os vértices, isto é, A(G)={a1, . . . , am}, com ak={vki,vkj},

para k ∈ {1, . . . ,m}, (|V|= n, |A|= m).

Primeiras Ideias

• Para se conhecer um grafo precisamos saber quais são seus vértices e “quem está ligado com quem”.

• V={1,2,3,4,5,6}• A={(1,2), (1,3), (2,4),(3,4), (4,5) e (5,6)}

Primeiras ideias

• Pontes de Königsberg • Euler• 1736 - 1º registro de um problema

relacionado com o que hoje em dia se chama de teoria dos grafos.

Pontes de Königsberg• No rio Pregel, que corta a cidade de Königsberg (hoje kaliningrad –

Rússia) haviam duas ilhas que, na época, eram ligadas entre si por uma ponte. As duas ilhas se ligavam ainda às margens por mais seis pontes. Dizia-se que os habitantes da cidade, nos dias soalheiros de descanso, tentavam efetuar um percurso que os obrigasse a passar por todas as pontes, mas apenas uma vez em cada uma. Como as suas tentativas foram sempre falhadas, muitos deles acreditavam que não era possível encontrar tal percurso. Será que tinham razão?

Primeiras Ideias• Euler:

– raciocínio muito simples. – Transformar os caminhos em

retas e suas intersecções em pontos, criando possivelmente o primeiro grafo da história.

A

B D

C

Existe o trajeto de percorrertodas as pontes uma única veze retornar ao ponto inicial?

Resposta: NÃO. Porque?

Primeiras Ideias• Ciclo Euleriano Passando por todas as arestas uma única vez e

retornando ao ponto inicial:– este percurso (ciclo) só existe se o grau dos vértices

(retas) for par. Onde, o grau de um vértice é o número de arestas incidentes.

A

B D

C

A – grau 3B – grau 5C – grau 3D – grau 3

Não existe Ciclo Euleriano neste exemplo

Primeiras Ideias

• Ciclo Euleriano – Teorema• Um grafo G conexo, possui ciclo

euleriano se e somente se todo vértice de G possuir grau par.

• Um grafo é conexo se existir caminho entre quaisquer dois vértices.

Grafo vazio

• é aquele que contém exclusivamente vértices.

Grafo de jogos antes do início do campeonato

Grafo Trivial

• Um grafo é dito trivial ou singleton quando possui somente um vértice

Grafo Direcionado

• Um grafo é dito direcionado ou orientado quando o sentido das ligações entre os vértices é importante. Nesse caso, as arestas possuem um sentido marcado por uma seta e recebem o nome de arcos.

Grafo rotulado• Um grafo é dito rotulado se existem

atribuições associadas a suas arestas ou vértices (numéricas ou alfanuméricas)

Pseudografo

• Um grafo que contém no mínimo um laço é denominado pseudografo.

Multigrafo

• Um grafo não direcionado que possui no mínimo duas arestas paralelas é denominado multigrafo.

Multigrafo direcionado

• Um grafo direcionado que possui dois ou mais arcos de mesma direção ligando um mesmo par de vértices é denominado multigrafo direcionado.

Grafo reflexivo

• É um grafo em que todos os vértices possuem um laço associado.

Buquê• é um grafo que contém apenas um vértice

com n laços.

Hipergrafo• é um conjunto H=(V,ξ), onde V representa

o conjunto de vértices de H e ξ é uma família das partes de N.

• N={1,2,3,4,5,6}• ξ={(1,2,3); (3,4); (4,5,6)}

Grafo Ponderado• Um grafo é ponderado ou valorado se

existem pesos associados às suas arestas ou vértices

Grafo misto

• Um grafo pode possuir simultaneamente arcos e arestas. Neste caso, são chamados de grafos mistos.

Exemplos de grafos direcionados e transformação do grafo misto

Ordem e tamanho de um grafo• Ordem de um grafo é

o número de vértices que ele possui.

• Tamanho que um grafo é o número de ligações que ele possui

• Grafo (1) ordem ?? e tamanho??

• Grafo (2) ordem ?? e tamanho??

Grafo finito

• Um grafo é dito finito quando possui um número finito de vértices, caso contrário, é infinito.

Adjacência de vértices• Dois vértices i e j são vizinhos ou adjacentes

quando existe uma aresta que liga i a j ou vice-versa.

• O conjunto de vértices vizinhos do vértice i é denominado N(i) ou Γ(i).

• A noção de vizinhança de vértices é associada a grafos não orientados.

Vértices adjacentes ao vértice 3

Vértice sucessor e antecessor• Um vértice j é sucessor de i se existe pelo

menos um arco ligando i a j. Os sucessores do vértice i são Γ+(i).

• No caso da ocorrência da relação inversa diz-se que o vértice j é antecessor de i. Os antecessores do vértice i são Γ-(i).

Conjunto de antecessores do vértice 3, Γ-(3)= {1} e o conjunto de sucessores de 3, Γ+(3) ={4,5}

Arestas Adjacentes

• Duas arestas são adjacentes quando compartilham o mesmo vértice.