Grafos e Modelos de Grafos - WordPress.comEncontrar o caminho mais curto entre duas cidades em uma rede de transporte; Distinguir compostos químicos com a mesma fórmula molecular,

Cícero C. Quarto – Engcomp/UEMA (2020.2)

1

Engenharia da Computação

1

Grafos e Modelos de Grafos

Prof. Cícero QuartoDepartamento de Engenharia da Computação (DECOMP/UEMA)

MATEMÁTICA DISCRETA AVANÇADA


2

Objetivos

Introduzir informalmente o conceito de grafo

Especificar aplicações de

grafos na solução de problemas do

mundo real

Definir formalmente o que é um grafo

Descrever modelos de

grafos

12

34


3

Conceito informal de grafo

Os grafos são estruturas discretas que consistem em vértices e arestas que ligam estes vértices.

aresta

vértice Conceitos

Estabelece relações entre os conceitos


4

Aplicação de grafos

■Modelagem da competição de espécies

diferentes em um nicho ecológico;■Modelagem dos relacionamentos entre pessoas;■Modelagem da colaboração entre

pesquisadores;■ Otimização de tarefas.


5

Aplicação de modelos de grafos na resolução de problemas do

mundo real

■ Percorrer todas as ruas de uma cidade sem

passar por uma rua duas vezes;■ Colorir cidades vizinhas de um mapa tal que não

haja duas cidades vizinhas (adjacentes) compartilhando a mesma cor;■ Encontrar o caminho mais curto entre duas

cidades em uma rede de transporte;■ Distinguir compostos químicos com a mesma

fórmula molecular, mas estruturas diferentes.


6

Grafos

Definição 1: Um grafo G = (V, E) consiste em V, um conjunto não vazio de vértices (ou nós), e E, um conjunto de arestas. Cada aresta tem dois vértices associados a ela, chamados de suas extremidades.

Uma Rede de Computadores

Centro de Dados

Link de Comunicação


7

Grafos simples

São grafos no qual cada aresta conecta dois vértices diferentes e duas arestas nunca conectam o mesmo par de vértices.

u

v

{u,v}


8

Multigrafos

São grafos que tem arestas múltiplas conectando o mesmo par de vértices. Quando existem marestas diferentes associadas ao mesmo par não ordenado de vértices {u, v}, dizemos também que {u, v} é uma aresta de multiplicidade m, isto é, podemos pensar neste conjunto de arestas como mcópias diferentes de uma aresta {u, v}.


9

Grafos com Laços

São grafos que tem arestas que conectam um vértice a si mesmo. Estas arestas são chamadas de laços.

Grafos que incluem laços, e possivelmente arestas múltiplas que conectam o mesmo par de vértices, são, algumas vezes, chamados de pseudografos (Rosen, 2009).


10

Grafos Orientados

Definição 2: Um grafo orientado (ou dígrafo) (V, E) consiste em um conjunto não vazio de vértices V e um conjunto de arestas orientadas (ou arcos) E. Cada aresta orientada está associada a um par ordenado de vértices. É dito que aresta orientada associada ao par ordenado (u, v) começa em u e termina em v.

Links simples orientados

Links múltiplos orientados


11

Modelos de Grafos

Grafos de Superposição de Nichos em

Ecologia

Grafos de Relacionamento

Grafos de Influência

O Grafo de Hollywood

Torneios Round-Robin

Grafos de Colaboração

Grafos de Chamadas

O Grafo da Web

Grafos de Precedência e Processamento Concomitante

Mapas Rodoviários


12

Modelos de Grafos

Grafos de Superposição de Nichos em Ecologia

■ Grafos usados que modelam a interação entre diferentes

espécies de animais. Por exemplo, a competição entre espécies em um ecossistema.

■■ Cada espécie é representada por um vértice. Uma

aresta não orientada conecta dois vértices se as duas espécies representadas por esses vértices competem (isto é, algumas das fontes de alimentos que elas usam são as mesmas).

■■■ Um grafo de superposição de nichos é um grafo simples, pois não são necessários nem laços nem arestas múltiplas neste modelo.

■■■■ O grafo na Figura 6, Rosen (2009, p. 593),

modela o ecossistema de uma floresta.


13

Modelos de Grafos

Grafos de Superposição de Nichos em Ecologia

Vemos a partir do grafo que esquilos e guaxinins competem, mas que corvos e musaranhos não.


14

Modelos de Grafos

Grafos de Relacionamento

■ Grafos usados para representar diversas relações entre as

pessoas. Por exemplo, podemos usar um grafo simples para representar se duas pessoas se conhecem, ou seja, se elas têm um relacionamento. Cada pessoa, em um grupo particular de pessoas, é representada por um vértice. Uma aresta não orientada é usada para ligar duas pessoas quando elas se conhecem. Nenhuma aresta múltipla, e em geral nenhum laço, são usados.


15

Modelos de Grafos

Grafos de Influência

■ Nos estudos de comportamento de grupo é observado que

certas pessoas podem influenciar o pensamento de outras. Um grafo orientado chamado de grafo de influência pode ser usado para modelar este comportamento. Cada pessoa do grupo é representada por um vértice. Há uma aresta orientada do vértice a para o vértice b quando a pessoa representada pelo vértice a influencia a pessoa representada pelo vértice b. Este grafo não contém laços nem arestas orientadas múltiplas

Deborah pode influenciar Brian, Fred e Linda, mas ninguém pode influenciá-la. Além disso, Yvonne e Brian podem influenciar um ao outro.


16

Modelos de Grafos

O Grafo de Hollywood

■ O grafo de Hollywood representa atores por vértices e

liga dois vértices quando os atores representados por esses vértices já tiverem trabalhado juntos em um filme. Este grafo é um grafo simples porque suas arestas são não orientadas, ele não contém arestas múltiplas nem laços. De acordo com o Internet Movie Database, em janeiro de 2006 o grafo de Hollywood tinha 637.099 vértices que representavam atores que apareceram em 339.896 filmes, e tinha mais de 20 milhões de arestas.


17

Modelos de Grafos

Torneios Round-Robin

■ Um torneio em que cada time joga com cada outro time

exatamente uma vez é chamado de torneio round-robin. Tais torneios podem ser modelados usando grafos orientados em que cada time é representado por um vértice. Observe que (a, b) é uma aresta se o time a ganhou do time b. Este grafo é um grafo orientado simples, que não contém nem laços nem arestas orientadas múltiplas (pois nem um par de times se enfrenta mais de uma vez).

Vemos que o Time 1 ainda não foi derrotado neste torneio e que o Time 3 ainda não ganhou.


18

Modelos de Grafos

Grafos de Colaboração

■ Um grafo chamado de grafo de colaboração pode ser

usado para modelar autoria conjunta de artigos científicos. Em um grafo de colaboração, os vértices representam pessoas e as arestas ligam duas pessoas se elas tiverem escrito um artigo em conjunto. Este é um grafo simples porque ele contém arestas não orientadas e não tem laços ou arestas múltiplas. O grafo de colaboração para pessoas que trabalham juntas em artigos de pesquisa em matemática tem mais de 400.000 vértices e 675.000 arestas.


19

Modelos de Grafos

Grafos de Chamadas

■ Os grafos podem ser usados para modelar chamadas

telefônicas feitas em uma rede, tais como uma rede de telefones de longa distância. Em particular, um multigrafo orientado pode ser usado para modelar chamadas, em que cada número de telefone é representado por um vértice e cada chamada telefônica é representada por uma aresta orientada. A aresta que representa uma chamada começa no número de telefone do qual a chamada foi feita e termina no número de telefone para o qual a chamada foi feita.


20

Modelos de Grafos

O Grafo da Web

■ A World Wide Web pode ser modelada como um grafo

orientado no qual cada página da Web é representada por um vértice e no qual uma aresta começa na página a da Web e termina na página b da Web se existir um link em a que direcione para b. Atualmente, o grafo da Web tem mais de três bilhões de vértices e 20 bilhões de arestas. Muitas pessoas estão estudando as propriedades do grafo da Web para entender melhor a natureza da Web, por exemplo, índices de páginas da Web.


21

Modelos de Grafos


■ Os programas de computador podem ser executados mais

rapidamente pela execução de certas instruções concomitantemente. É importante não executar uma instrução que exija resultados de uma instrução que ainda não foi executada. A dependência de instruções das instruções prévias pode ser representada por um grafo orientado. Cada instrução é representada por um vértice e existe uma aresta de um vértice para um segundo vértice se a instrução representada pelo segundo vértice não puder ser executada antes de a instrução representada pelo primeiro vértice ter sido executada. Este grafo é chamado de grafo de precedência. Veja um exemplo desta modelagem no slide seguinte.


22

Modelos de Grafos


O grafo mostra que a instrução S5 não pode ser executada antes das instruções S1, S2 e S4 terem sido executadas.


23

Modelos de Grafos

Mapas Rodoviários

■ Os grafos podem ser usados para modelar mapas

rodoviários. Em tais modelos, os vértices representam intersecções e as arestas representam estradas. As arestas não orientadas representam estradas de mão dupla, e as arestas orientadas representam estradas de mão única. As arestas não orientadas múltiplas representam estradas de mão dupla múltiplas que conectam as mesmas duas intersecções. Arestas orientadas múltiplas representam estradas de mão única múltipla que começam em uma intersecção e terminam na segunda intersecção. Os laços representam estradas em laço. Grafos mistos são necessários para representar mapas rodoviários que incluam tanto estradas de mão única quanto de mão dupla. Veja um exemplo desta modelagem no slide seguinte.


24

Modelos de Grafos

Mapas Rodoviários

Este mapa pode ser modelado usando grafo


2525

Referências


26

Obrigado pela atenção de todos e até a nossa próxima aula!!!

Prof. Cícero C. [email protected]://www.cicerocq.com

http://www.cicerocq.com/

Documents

Grafos e Modelos de Grafos - WordPress.comEncontrar o caminho mais curto entre duas cidades em uma rede de transporte; Distinguir compostos químicos com a mesma fórmula molecular,