CONCEITO DA TEORIA DE GRAFOS

Prévia do material em texto

07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 1/15
CONCEITO DA TEORIA DE GRAFOS
TEM POR OBJETIVO APRESENTAR O CONCEITO DA PESQUISA OPERACIONAL
AUTOR(A): PROF. CLAUDINEIA HELENA RECCO
TEORIA DE GRAFOS
 
Considerações Históricas (ANDRADE, 1980 apud Marins (2009, p. 99)) Os habitantes da cidade de
Königsberg, atualmente denominada Kaliningrado, exclave russo entre a Polônia e a Lituânia, à beira do
Mar Báltico, estavam muito intrigados com um problema que se aparecia em seus costumeiros passeios a
duas ilhas do Rio Pregel. Essas ilhas ligavam-se às margens do rio por intermédio de 6 (seis) pontes, além
de uma sétima que interligava as duas ilhas. Tudo conforme aparece na figura 1.
A curiosidade surgiu, pois nenhum dos frequentadores do local era capaz de percorrer essas sete pontes
sem passar mais de uma vez por uma delas.
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 2/15
O matemático Euler, em 1735, apresentou à Academia de S. Petersburgo a primeira demonstração de
impossibilidade de resolução do referido problema. Euler usou uma representação esquemática (modelo de
grafo) onde cada ponte foi representada por um segmento de reta (aresta) e cada ilha ou margem do rio por
um ponto (nó ou vértice); conforme figura 2, onde as Ilhas são os pontos B e D e as Margens são os pontos A
e C.
Nota-se que a representação esquemática apresentado na figura 2 apresenta a mesma situação apresentado
na figura 1, sob o ponto de vista de ordem e continuidade. Euler demonstrou a impossibilidade de se
percorrer toda a figura 2 sem levantar o lápis do papel (o que equivaleria passar por todas as pontes) e sem
percorrer mais de uma vez a mesma aresta.
Esta foi a primeira notícia do emprego de um modelo de grafos, na demonstração de uma propriedade
geométrica. Euler denominou de grau de um nó (ou vértice) o número de arestas que tocam nesse nó. Por
exemplo, A, D e C são nós do terceiro grau, enquanto B é do quinto. Euler concluiu de que somente os
grafos onde todos os seus nós têm grau par podem oferecer a propriedade geométrica de poderem ser
desenhados de uma só vez, sem levantar o lápis do papel. (Marins, 2009, p. 99)
Diversos problemas de programação linear, inclusive os problemas de transporte, podem ser modelados
como problema de fluxo de redes. Algoritmos específicos para determinados tipos de problemas podem ser
mais convenientes para a sua solução do que algoritmos mais genéricos. Antes de continuar, serão
apresentadas algumas definições da teoria dos grafos.
Conceitos Básicos de Grafos
Definições de Grafo
Definição 1: Um grafo é uma estrutura que corresponde a um par de conjuntos G = (V, A), onde: (Marins,
2009, p. 103)
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 3/15
(i) V é um conjunto não vazio, cujos seus elementos são denominados de vértices ou nodes e pode
representar o conjunto de entidades. Por exemplo, estas entidades podem estar associadas a pontos, locais,
pessoas, áreas geográficas.
(ii) A representa o conjunto de arestas, sendo estas um par ordenado a=(c, d), com c e d pertencente a A,
esse para ordenado (ou elementos) são ligações ou inter-relações entre os elementos de A. Por exemplo, as
ligações podem ser estradas, parentescos e fronteiras entre áreas geográficas
Exemplo 1. Explicação da definição de Grafo. (Marins, 2009, p. 103)
Observe-se que em (a), não se faz presente a ideia de orientação, este seria um exemplo de grafo não
orientado, enquanto que em (b), onde a orientação é importante, seria um grafo orientado.
 
Representações de um Grafo
O grafo pode ser representado geometricamente em forma de diagramas conforme a figuras 3, 4 e 5 ou sob a
forma de matriz.
 
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 4/15
 
Definição 2: Um grafo linear consiste em diversos nós, ou pontos, sendo que cada nó deve estar conectado
a um ou mais nós por arcos.
Um exemplo de um grafo linear é apresentado na figura 6.
Definição de Matriz de Adjacência
Considere G = (V, A), um grafo (orientado ou não). A matriz de adjacência é representada da seguinte forma:
(Marins, 2009, p. 104)
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 5/15
Exemplo 2. Um Grafo Não Orientado com 4 nós e 5 arestas e a sua matriz de adjacência X estão ilustrados
na figura 7. (Marins, 2009, p. 104)
Definição de Matriz de incidência
Seja G = (V, A) um grafo orientado. A matriz de incidência é representada da seguinte forma:
Exemplo 3. Um Grafo orientado com 6 nós e 8 arcos está apresentado pela figura 8. Na sequência apresenta-
se a sua Matriz de incidência. (Marins, 2009, p. 106)
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 6/15
 
Definição de Grafos Valorados
A cada nó de grafo e/ou a cada aresta (ou arco) pode estar associado um número (peso, custo ou valor).
Neste caso, diz-se que G = (V, A) é um grafo valorado (ver figura 9). (Marins, 2009, p. 106)
 
Definição de Cadeia num Grafo
Uma cadeia de um grafo é uma sequência de arcos, ou arestas, de modo que cada arco tenha uma das suas
extremidades em comum com os arcos antecedente e subsequente, com exceção do arco inicial e do arco
terminal da cadeia. (Marins, 2009, p. 106)
 
Definição Grafo Direto
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 7/15
Um grafo direto (ou rede direta) é um grafo em que o fluxo ao longo de um arco pode ser efetuado apenas
em um sentido. Entretanto, pode-se substituir um arco com fluxo nos dois sentidos por dois arcos em
sentidos opostos. Desta forma, podemos utilizar redes diretas sem que o modelo esteja perdendo a sua
generalidade.
 
Definição de Caminho num Grafo
Definição 1: Um caminho ou canal é um conjunto ordenado de arcos que conectam dois nós através de nós
intermediários, cada um dos quais estando exatamente em dois arcos do canal.
Um exemplo de canal no grafo apresentado na figura 6 é o conjunto dos arcos 1, 5 e 7, que conectam os nós
a e c através dos nós b e e.
Definição 2: Um caminho é uma cadeia na qual todos os arcos possuem a mesma orientação. Na figura 9
exemplifica-se uma cadeia e um caminho num grafo com 7 nós e 9 arcos. (Marins, 2009, p. 107)
 
Definição de Comprimento de uma Cadeia ou de um Caminho em Grafos Valorados
Se o grafo é valorado, o comprimento é obtido através da soma dos valores associados aos arcos que
compõem a Cadeia ou o Caminho. (Marins, 2009, p. 107)
 
Definição Grafo Conectado
Um grafo conectado é um grafo no qual existe caminho entre qualquer par de nós.
O grafo das figuras 6 e 10 são grafos conectados.
 
Definição
Um laço é um canal que conecta um nó a ele mesmo. Em G apresentado na figura 11 há três ocorrências
de laços para um grafo não orientado.
3
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 8/15
Voltando a figura 6 nota-se que os arcos 1, 5, 7, 8, 9 e 2 formam um laço conectando o nó a (ou qualquer
outro nó do canal) e a si mesmo.
 
Definição de Ciclo num Grafo
Um ciclo é uma cadeia fechada simples. (Marins, 2009, p. 108)
 
Definição de Circuito num Grafo
Um circuito é um ciclo formado por arcos que têm a mesma orientação. (Marins, 2009, p. 108)
Na figura 12 têm-se uma ilustração de um ciclo e de circuito num grafo com 4 nós e 5 arcos.
 
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 9/15
Definição de Grafo Conexo e Grafo Desconexo
Um grafo G = (V, A) é conexo, quando para qualquer par de nós (i, j) de V existe uma cadeia em A, cujas
extremidades estão em i e j (ver figura 13). De outra forma G é dito ser desconexo. Todo grafo desconexo
pode ser decomposto em componentes conexas (ver Figura 14) (Marins, 2009, p. 108)
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 10/15
 
Definição deÁrvore
Uma árvore é um grafo conectado que não contém laços.
Exemplos de árvores no grafo da figura 6 incluem os arcos 1, 3, 4, 6, 8 ou os arcos 2, 3, 4, 5, 8. O conjunto de
arcos 1, 2, 3, 4, 7, 8 contém um laço (1, 2, 3), portanto não é uma árvore; o conjunto de arcos 1, 3, 7, 8, apesar
de não conter laços, não forma uma árvore por não ser um grafo conectado. Pode ser provado que uma
árvore com n nós possui (n - 1) arcos e há pelo menos dois extremos (nós em apenas um arco) em uma
árvore.
 
Definição de Árvore, Floresta num Grafo.
Uma árvore (figura 16) é um grafo conexo sem ciclos, enquanto uma floresta é um grafo cujas componentes
conexas são árvores. (Marins, 2009, p. 110)
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 11/15
Teorema: Seja G = (V, A) um grafo, tal que se tem n = número de nós e n > 2. As seguintes proposições são
equivalentes: (Marins, 2009, p. 110)
(i) G é uma árvore;
(ii) G é conexo e sem ciclos;
(iii) G é sem ciclos e tem n-1 arestas;
 (iv) G é conexo e tem n-1 arestas;
(v) G é sem ciclos e por adição de uma aresta se cria um e somente um ciclo;
(vi) G é conexo, mas deixa de sê-lo se uma aresta é suprimida;
(vii) Todo par de nós de G é unido por uma e uma só cadeia simples.
 
Aplicações da teoria de Grafos
A seguir passa-se a descrever sucintamente algumas aplicações contemporâneas de Teoria dos Grafos
extraídas de Marins (2009, p. 101).
 
Um problema de montagem (ANDRADE, 1980 apud Marins (2009, p. 101))
Uma indústria dispõe de três setores de montagem (A, B e C) alimentados por três Departamentos (D1, D2 e
D3). Como a alimentação é feita por esteiras móveis, todas situadas num plano, é necessário estabelecer um
projeto de implantação de tal forma que uma esteira não intercepte a outra. Uma solução em estudo está
ilustrada na figura 17, onde há interferência da esteira do Departamento 2 que alimenta o setor de
montagem B na esteira do Departamento 3 que alimenta o setor A (indicado pela seta).
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 12/15
Verifica-se que o envio do abastecimento D3 para setor de montagem A intercepta o abastecimento D2 - B.
Neste tipo de grafo, conhecido como K3,3, não há solução, ou seja, qualquer outra tentativa levará sempre a
esta intersecção indesejável.
Em Teoria dos Grafos existe uma área denominada Grafos Planares em que se estuda esta situação. A
detecção desses pontos de cruzamento planar tem uma importância fundamental em vários outros casos,
como na implantação de viadutos em projetos viários ou na fabricação de chips para equipamentos
eletrônicos.
 
Um Problema de Localização
Uma indústria necessita instalar-se em qualquer uma das vinte cidades maiores consumidoras dos seus
produtos. A escolha desta cidade deve ser tal que o custo de distribuição dos seus produtos para os centros
consumidores seja o menor possível.
O problema é determinar qual a sequência de cidades, a partir daquela onde foi instalada a indústria, cujo
custo total de distribuição seja mínimo.
Trata-se, pois, de analisar, entre todas as permutações possíveis entre essas cidades, qual a mais
econômica. Há um número muito grande de possibilidades (20!) o que inviabiliza um procedimento
exaustivo de testar todas as possibilidades. A Teoria dos Grafos oferece uma importante ajuda na solução
deste problema.
ATIVIDADE FINAL
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 13/15
Dado o Grafo a seguir determine um caminho que liga o nó s ao nó t. 
 
A.   O grafo não apresenta um caminho de s a t 
B. Pode-se dizer que as arestas 10, 16 e 7 formam um caminho. 
C. Pode-se dizer que as arestas 8, 16 e 7 formam um caminho. 
D. Pode-se dizer que as arestas 10, 14 e 15 formam um caminho. 
Dado o Grafo a seguir determine um circuito.  
 
A. O grafo não apresenta um circuito. 
B. Pode-se dizer que as arestas 1, 3, 5, 7, 4 e 8 formam um circuito. 
C. Pode-se dizer que as arestas 13, 4 e 11 formam um circuito.
D. Pode-se dizer que as arestas 14, 13 e 2 formam um circuito.
Dado o Grafo a seguir identifique um laço.
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 14/15
 
A. Os nós 1, 2 e 5 formam um laço.  
B. Os nós 1, 5 e 6 formam um laço.
C. Os nós 1, 2 e 3 formam um laço.
D. O grafo não apresenta laço.
REFERÊNCIA
ANDRADE, M.C.Q. Criação no Processo Decisório. Rio de Janeiro: LTC, 1980.
MARINS, F. A. S. Introdução à Pesquisa Operacional. Guaratinguetá: UNESP, 2009.
MELLO, J. C. C.B. S. de. NOTAS DE AULA. POII-UFF. s/a.
07/03/2021 AVA UNINOVE
https://ava.uninove.br/seu/AVA/topico/container_impressao.php 15/15