› marco › site_media › uploads › bcc204 › 01... · BCC204 - Teoria dos Grafos -...

BCC204 - Teoria dos Grafos

Marco Antonio M. Carvalho

(baseado nas notas de aula do prof. Haroldo Gambini Santos)Departamento de Computação

Instituto de Ciências Exatas e BiológicasUniversidade Federal de Ouro Preto

12 de agosto de 2019

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 1 / 41

Avisos

Site da disciplina:I http://www.decom.ufop.br/marco/

Lista de e-mails:I bcc204@googlegroups.com

Para solicitar acesso:I http://groups.google.com/group/bcc204

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 2 / 41

Na aula de hoje

1 Introdução

2 Exemplos

3 Terminologia

4 Representação

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 3 / 41

Grafos

Facebook em 2018: ≈ 2,234 bilhões de usuários ativos.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 4 / 41

Grafos

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 5 / 41

Grafos

Facebook Graph Search.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 6 / 41

Grafos

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 7 / 41

Grafos

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 8 / 41

Grafos

https://memoria.rnp.br/ceo/trafego/panorama.phpMarco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 9 / 41

Grafos

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 10 / 41

Grafos

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 11 / 41

Histórico

Edsger Dijkstra:“A Ciência da computação tem tanto a ver com o computador como aAstronomia com o telescópio, a Biologia com o microscópio, ou a Químicacom os tubos de ensaio. A Ciência não estuda ferramentas, mas o quefazemos e o que descobrimos com elas.”

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 12 / 41

Grafos

HistóricoUm grafo é uma estrutura de abstração muito útil na representação esolução de problemas computacionais, por representarem relações deinterdependência entre elementos de um conjunto.

O primeiro registro de uso data de 1736, por Euler.

O problema era encontrar um caminho circular por Königsberg (atualKaliningrado) usando cada uma das pontes sobre o rio Pregel (ou Pregolya,Pregola) exatamente uma vez.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 13 / 41

Histórico

1736: Euler e as Pontes de Königsberg

Pergunta:Partindo de uma das margens, pode-se encontrar um percurso que passesomente uma vez em cada ponte e retorne ao ponto de partida?

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 14 / 41

Pontes de Königsberg - O Grafo

m1

i1

m2

i2

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 15 / 41

Grafos

Definição FormalGrafo G = (V ,A)

I Conjunto V com n vértices (também chamados nós){v1, v2, . . . , vn}

I Conjunto A com m arestas ou arcos{a1, a2, . . . , am}

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 16 / 41

Grafos

Definição FormalGrafo G = (V ,A)

I Conjunto V com n vértices (também chamados nós){v1, v2, . . . , vn}

I Conjunto A com m arestas ou arcos{a1, a2, . . . , am}

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 16 / 41

Grafos

Definição FormalGrafo G = (V ,A)

I Conjunto V com n vértices (também chamados nós){v1, v2, . . . , vn}

I Conjunto A com m arestas ou arcos{a1, a2, . . . , am}

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 16 / 41

GND - Grafo Não Direcionado

v1

v2

v3

v4

v5

I Ligações expressas em ArestasI Se o vértice a está ligado a b, a recíproca é verdadeira;I Cada aresta é representada por um conjunto {v1, v2}, indicando os

dois vértices envolvidos.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 17 / 41

GD - Grafo Direcionado

v1

v2

v3

v4

v5

I Ligações expressas em Arcos →I Cada arco é representada por um par ordenado (v1, v2), indicando os

dois vértices envolvidos.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 18 / 41

Exemplos: Redes Sociais Analógicas

Chains of AffectionPeter Bearman, James Moody, and Katherine Stovel. Chains of affection:The structure of adolescent romantic and sexual networks. AmericanJournal of Sociology, 110(1):44- 99, 2004.

Pesquisa com 800 estudantes de uma escola secundária americana.

A estrutura das relações românticas e sexuais da Jefferson High School.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 19 / 41

Exemplos: Redes Sociais Analógicas

MachoFêmea

12 9

63

2

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 20 / 41

Exemplos: Projeto VLSI

O Problema de Steiner em Grafos

Dado um conjunto de pontos, ligue-os por uma rede de menor tamanhopossível (em número de ligações): eventualmente, outros pontos e ligaçõespodem ser adicionados.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 21 / 41

Terminologia

LaçoUma aresta cujas duas extremidades incidem em um mesmo vértice.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 22 / 41

Terminologia

Arestas ParalelasMais de uma aresta associada ao mesmo par de vértices.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 23 / 41

Terminologia

Grafo simplesGrafo que não possui laços e nem arestas paralelas.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 24 / 41

Terminologia

Vértices AdjacentesVértices que são os pontos finais de uma mesma aresta.A função Γ(i) retorna o conjunto de vértices adjacentes ao vértice i .

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 25 / 41

Terminologia

Grau de um VérticeO grau (d(i)) de um vértice i em um grafo não direcionado é igual onúmero de arestas incidentes a i .O grau de entrada (d−(i)) de um vértice i em um grafo direcionado é igualo número de arestas que entram em i .O grau de saída (d+(i)) de um vértice i em um grafo direcionado é igual onúmero de arestas que saem de i .

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 26 / 41

Conceito

Teorema do Aperto de Mãos HandshakingA soma dos graus de todos os vértices de um GND G é duas vezes onúmero de arestas de G .

n∑i=1

d(i) = 2m

CorolárioO número de vértices de grau ímpar em um GND é par.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 27 / 41

Conceito

Teorema do Aperto de Mãos HandshakingA soma dos graus de todos os vértices de um GND G é duas vezes onúmero de arestas de G .

n∑i=1

d(i) = 2m

CorolárioO número de vértices de grau ímpar em um GND é par.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 27 / 41

Terminologia

Grafo CompletoUm grafo completo com n vértices, denominado Kn é um grafo simplescontendo exatamente uma aresta para cada par de vértices distintos.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 28 / 41

Terminologia

Grafo RegularGrafo no qual todos os vértices possuem o mesmo grau.Obs: qualquer grafo completo é regular.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 29 / 41

Terminologia

Vértice IsoladoVértice com nenhuma aresta incidente.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 30 / 41

Terminologia

Grafo ConexoPara todo par de vértices i e j de G existe pelo menos um caminho entre ie j .

Grafo DesconexoConsiste de 2 ou mais grafos conexos, chamados de componentes.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 31 / 41

Grafo Complemento

DefiniçãoSeja G = (V ,E ) um grafo simples não direcionado, o complemento de G ,G (ou C (G )), é um grafo formado da seguinte maneira:I Os vértices de G são todos os vértices de G ;I As arestas de G são exatamente as arestas que faltam em G para

formarmos um grafo completo.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 32 / 41

Grafo Bipartido

DefiniçãoUm grafo é bipartido se o conjunto de vértices V pode ser particionado em2 subconjuntos V1 e V2 tal que todas as arestas do grafo são incidentes aum vértice de V1 e a um vértice de V2.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 33 / 41

Grafo Bipartido Completo

DefiniçãoUm grafo bipartido é completo (K|V1|,|V2|) se cada vértice do subconjuntoV1 é adjacente a todos os vértices do subconjunto V2 e vice-versa.

Exemplo de grafos completos (1) e bipartidos completos (2 e 3).

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 34 / 41

Grafos - Representação Computacional

Matriz de AdjacênciasMatriz An×n, sendo que:

aij =

{1 se existe a aresta/arco (vi , vj)0 caso contrário

Propriedades:I Simétrica para grafos não direcionados;I Consulta existência de uma aresta/arco com um acesso à memória:

O(1);I Ocupa Θ(n2) de espaço mesmo para grafos esparsos.

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 35 / 41

Matriz de Adjacências - Grafo Não Direcionado

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 36 / 41

Matriz de Adjacências - Grafo Direcionado

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 37 / 41

Grafos - Representação Computacional

Lista de AdjacênciasI Usa n listas, uma para cada vértice;I Lista de vi (o i-ésimo vértice) contém todos os vértices adjacentes a

ele.

Propriedades:I Ocupa menos memória: O(m);I No entanto, a complexidade da operação de determinar uma

adjacência é limitada por O(n).

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 38 / 41

Lista de Adjacências - Grafo Não Direcionado

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 39 / 41

Exercícios

1 Determine o número de vértices para os seguintes grafos:I G tem 9 arestas e todos os vértices têm grau 3;I G é regular com 15 arestas;I G tem 10 arestas com 2 vértices de grau 4 e todos os outros de grau 3.

2 Dê exemplo de um grafo sem arestas paralelas com 8 vértices com osseguintes graus: 1, 1, 1, 2, 3, 4, 5, e 7

3 Dê exemplo de um grafo conexo sem loops com 7 vértices com osseguintes graus: 1, 1, 2, 3, 4, 5, e 7

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 40 / 41

Dúvidas?

Marco Antonio M. Carvalho (UFOP) BCC204 12 de agosto de 2019 41 / 41