Teoria dos Grafos - UNESP: Câmpus de São José do Rio Preto … · 2014-09-30 · Modelar problemas de forma a serem resolvidos utilizando conceitos e resultados de Teoria dos Grafos

Teoria dos Grafos

Valeriano A. de OliveiraSocorro Rangel

Departamento de Matemática [email protected], [email protected]

AULA 1Introdução, Conceitos Iniciais, Isomorfismo

Preparado a partir do texto:Rangel, Socorro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.

Introdução

Introdução Aplicações Conceitos Iniciais Isomorfismo

O que é um Grafo?Introdução Aplicações Conceitos Iniciais Isomorfismo

Teoria dos Grafos (Antunes&Rangel) – 3

Um grafo G é constituído de um conjunto V não-vazio de objetos,chamados vértices (ou nós), e um conjunto A de pares não ordenados deelementos de V , chamados de arestas. Denotamos o grafo por G(V,A)ou simplesmente G.

Exemplo 1.

a) V = {v1, v2, v3, v4, v5} eA = {(v1, v2), (v1, v3), (v2, v4), (v3, v4), (v4, v5), (v1, v2), (v2, v2)}.

b) V = {1, 2, 3, 4, 5} e A = {(1, 2), (2, 3), (1, 4), (1, 3)}.

c) V = {a, b, c} e A = { }.



Os grafos podem ser representados através de um diagrama onde osvértices são representados por pontos e cada aresta é representada poruma linha ligando os pares de vértices que a definem. A representaçãográfica dos grafos dados no Exemplo 1 são dadas na figura a seguir.

v1

v2

v3 v

4

v5

1

2

3

4

5

a

b c

Em algumas aplicações, as arestas são definidas como pares ordenadosde vértices. Neste caso dizemos que o grafo é orientado ou direcionado eo chamamos de Digrafo.

O que é um Digrafo?Introdução Aplicações Conceitos Iniciais Isomorfismo


Um grafo orientado (ou direcionado) G(V,A) é constituído pôr umconjunto V não-vazio de objetos, chamados vértices (ou nós), e umconjunto A de pares ordenados de elementos de V , chamados de arestasou arcos.

Os digrafos podem ser desenhados através de um diagrama onde osvértices são representados por pontos e cada aresta (vi, vj) érepresentada por uma linha ligando vi a vj com uma seta apontandopara vj.



Exemplo 2. V = {v1, v2, v3, v4, v5} eA = {(v1, v2), (v1, v3), (v2, v4), (v3, v4), (v4, v5), (v1, v2), (v2, v2)}.

v1

v2

v3

v4

v5



Um mesmo grafo, ou um mesmo digrafo, pode ter diferentesrepresentações gráficas. Ver figura abaixo:

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

Figura 1: Um mesmo grafo com diferentes representações gráficas.



O que é que caracteriza um grafo? O conjunto de vértices e de arestas,ou seja, um conjunto de objetos (vértices) e a relação entre estes objetos(arestas). Durante o curso, a distinção entre grafos e digrafos será feitade acordo com o tópico estudado.

Assim, podemos dizer que a Teoria de Grafos é um ramo damatemática que estuda as relações entre os objetos de umdeterminado conjunto.

Objetivos do curso:

■ Desenvolver a Teoria dos Grafos

■ Modelar problemas de forma a serem resolvidos utilizando conceitose resultados de Teoria dos Grafos.

Aplicações


O problema das pontes de KönigsbergIntrodução Aplicações Conceitos Iniciais Isomorfismo


Na cidade de Konigsberg (Hoje Kaliningrado - Rússia) sete pontescruzam o rio Pregel estabelecendo ligações entre uma ilha e o continenteconforme a figura abaixo:

Será que é possível fazer um passeio pela cidade, começando eterminando no mesmo lugar e passando pôr cada uma das pontes apenasuma vez?

Problema do Carteiro ChinêsIntrodução Aplicações Conceitos Iniciais Isomorfismo


Determinar a rota de menor custo que saia da agência central doscorreios, passe pôr todas as ruas de um determinado bairro, e volte aorigem.

O Problema de ligações de eletricidade, gás e água



Considerem que existam 3 casas e que cada uma delas precisa ser ligadaao sistema de eletricidade, gás e água. Por questões de segurança,deseja-se saber se é possível fazer as ligações sem que haja cruzamentodas tubulações. Represente este problema através de um grafo.

O problema do caixeiro viajanteIntrodução Aplicações Conceitos Iniciais Isomorfismo


Um viajante necessita visitar um certo número de cidades. É possíveldeterminar um roteiro de viagem tal que cada cidade seja visitada apenasuma vez?

Considere, por exemplo, um trecho do mapa rodoviário que inclui acidade de São José do Rio Preto (SJRP). Suponha que o viajante tenhaque sair de SJRP e visitar as cidades de Marilia, Araçatuba, Bauru e SãoCarlos. Represente este problema através de um grafo.

É possível encontrar uma rota que passe pôr todas as cidades apenasuma vez e retorne a cidade SJRP? Caso existam mais de uma rota, qualé a rota que minimiza o trecho viajado?



ExercíciosIntrodução Aplicações Conceitos Iniciais Isomorfismo


1. Considere o problema de ligações de eletricidade, gás e água.Desenhe grafos representando as seguintes situações:(a) 2 casas e 3 serviços;

(b) 4 casas e 4 serviços (água, eletricidade, gás e telefone).

2. Descreva 10 situações (jogos, atividades, problemas, etc.) quepodem ser representadas através de grafos ou digrafos. Explique oque os vértices e as arestas estão representando. Sugestão deleitura: Capitulo 1, seção 1.3 de [2] e Capítulo3 e 5 de [3].

3. O Problema da decantação - Considere três vasos, A, B, e C comcapacidades de 8, 5 e 3 litros respectivamente. O vaso A está cheioe os vasos B e C estão vazios. Divida o líquido que está no vaso Aem duas quantidades iguais. Represente o problema usando umgrafo.

BibliografiaIntrodução Aplicações Conceitos Iniciais Isomorfismo


1. N. Deo, Graph Theory with applications to engineering andcomputer science, 1974.

2. R.K. Ahuja, T. Magnanti e J.B. Orlin, Network Flows, PrenticeHall, 1993.

3. R.J.Wilson, Introduction to graph theory, 3rd ed. The pitman PressLtda, Bath, 1985.

Conceitos Iniciais




Definição 3. Seja G(V,A) um grafo. Dada uma arestaa = (vi, vj) ∈ A dizemos que:

a) vi e vj são os extremos da aresta a.

b) A aresta a é dita ser incidente nos vértices vi e vj.

c) vi e vj são chamados de vértices adjacentes.

d) Se vi = vj a aresta a é chamada de loop ou laço.

e) Se existir uma aresta f = (v , v ) tal que v = v e v = v , as arestas



Exercício Analise o grafo da figura abaixo e exiba exemplos dos termoscitados na Definição 3.

v1

v2

v3 v

4

v5

Figura 2:



Definição 4. Um grafo é simples se não possui loops e/ou arestasparalelas.

Definição 5. Duas arestas são ditas adjacentes se elas incidem nomesmo vértice.

Definição 6. O grau de um vértice v, d(v), em um grafo sem loops édeterminado pelo número de arestas incidentes em v. Caso haja loops,estas arestas contribuem com grau 2.

Exemplo 7. Determine os graus dos vértices do grafo dado na figuraacima.



Definição 8. Dizemos que:

a) Um vértice v é isolado se d(v) = 0.

b) Um vértice v é pendente se d(v) = 1.

c) Um grafo G(V,A) é dito nulo se o conjunto de arestas é vazio.

d) Um grafo G(V,A) é dito regular se todos os seus vértices tem omesmo grau.

e) Um grafo G(V,A) é dito completo se existe uma aresta entre cadapar vértices. É representado por Kn, onde n é o número de vérticesdo grafo.

f) Um grafo G(V,A) é dito valorado (ou rede) se são atribuídos valorespara os vértices e/ou arestas.



Figura 3: Grafos regular e nulo.

Figura 4: Grafos completos K4 e K5.



Proposição 9. Dado um grafo G com n vértices, v1, v2, . . . , vn e m

arestas, temos que:n∑

i=1

d(vi) = 2m. (1)

Porque este resultado é válido? Observe que cada aresta contribui com 2graus para cada vértice. Assim a soma dos graus de todos os vértices éigual a duas vezes o número de arestas.

Teorema 10. O número de vértices de grau ímpar em um grafo ésempre par.



Demonstração. Vamos dividir a soma em (1) em duas parcelas. Osvértices com grau par e os vértices com grau ímpar:

n∑

i=1

d(vi) =∑

grau par

d(vi) +∑

grau ímpar

d(vi). (2)

O lado esquerdo da equação (2) é par (pela Proposição 9). A primeiraparcela do lado direito também é par, pois é a soma de números pares.Para que a igualdade seja válida, a segunda parcela em (2) também deveser par: ∑

grau ímpar

d(vi) é par. (3)

Como cada parcela d(vi) em (3) é ímpar temos que ter um número parde elementos para que a soma seja um número par (lembre-se que umnúmero ímpar é da forma 2k + 1).



Exercícios:

1. Desenhe todos os grafos simples com 1,2, 3 e 4 vértices.

2. Represente os seguintes compostos orgânicos através de grafos: (a)CH4; (b) C2H2; (c) N2O3.

3. Convença a você mesmo que o grau máximo de um vértice em umgrafo simples com n vértices é n− 1.

Isomorfismo




Nós já vimos que é possível representar um mesmo grafo de váriasmaneiras. Como determinar se dois grafos são equivalentes, ou seja sepossuem as mesmas propriedades? Isto é como determinar se dois grafossão isomorfos? A palavra isomorfismo vem do grego iso (mesmo) emorfo (mesma forma).

Definição 11. Dizemos que dois grafos G e H são isomorfos se existiruma correspondência biunívoca entre os vértices de G e os vértices de H

que preserve a relação de adjacência entre vértices e arestas. Em outraspalavras, é possível obter o grafo H a partir de uma nova rotulação dosvértices de G.



Exemplo 12. Considere os grafos da Figura 5. Construir acorrespondência biunívoca.

a

b

c

1 2

3 4

5

Figura 5:



Aplicações: O estudo de isomorfismo pode ser aplicado na descobertade novos compostos orgânicos. Os químicos mantém uma tabela decompostos orgânicos. Cada vez que um novo composto é descoberto énecessário determinar se ele é isomorfo a algum composto já existente.



Aplicações: O estudo de isomorfismo pode ser aplicado na descobertade novos compostos orgânicos. Os químicos mantém uma tabela decompostos orgânicos. Cada vez que um novo composto é descoberto énecessário determinar se ele é isomorfo a algum composto já existente.

Determinar se dois grafos são isomorfos não é uma tarefa muito simples.De fato a determinação de isomorfismos é uma área de intensa pesquisaem teoria de grafos. Condições necessárias para que dois grafos sejamisomorfos são facilmente determinadas através da Definição 11:



Condições necessárias para Isomorfismos entre os dois grafos G

e H:

1. G e H devem possuir o mesmo número de vértices;

2. G e H devem possuir o mesmo número de arestas;

3. G e H devem possuir o mesmo número de vértices com umdeterminado grau.

As condições 1,2 e 3 acima são suficientes?



Vamos verificar este fato através do seguinte exemplo:

G: H:

x

u

v

y

w

Observe que G e H:

a) possuem mesmo número de vértices;

b) possuem mesmo números de arestas;

c) possuem: 3 vértices com grau 1; 2 vértices com grau com grau 2; 1vértice com grau 3. Porém...



Porém estes dois grafos não são isomorfos! Não é possível fazer umacorrespondência biunívoca entre os vértices que preserve a relação deadjacência entre vértices e arestas. Observe que é necessário associar ovértice x do grafo G ao vértice y do grafo H, pois não existe nenhumoutro vértice com grau 3 em H. Mas o vértice y é adjacente a apenasum vértice de grau 1, enquanto que x em G é adjacente a dois vérticesde grau 1. Portanto, não é possível fazer uma correspondência biunívocaentre os vértices de G e H que preserve a relação de adjacência entrevértices e arestas.

No capítulo 11, seção 11.7 de [N. Deo, Graph Theory with applicationsto engineering and computer science, 1974] é feita uma discussão arespeito de algoritmos para se determinar isomorfismos entre grafos.



Exercícios:

1. Desenhe todos os grafos simples, não isomorfos com 1,2, 3 e 4vértices.

2. Verifique se os grafos abaixo são isomorfos:

(a)G: H:

(b) G: H:

Documents

Teoria dos Grafos - UNESP: Câmpus de São José do Rio Preto … · 2014-09-30 · Modelar problemas de forma a serem resolvidos utilizando conceitos e resultados de Teoria dos Grafos