Noções da teoria dos grafos

Prévia do material em texto

Noc¸o˜es da Teoria dos Grafos
Andre´ Arbex Hallack
I´ndice
1 Introduc¸a˜o e definic¸o˜es ba´sicas.
Passeios eulerianos 1
2 Ciclos hamiltonianos 7
3 A´rvores 11
4 Emparelhamento em grafos 15
5 Grafos planares:
Colorindo grafos e mapas 19
Refereˆncias 25
i
Cap´ıtulo 1
Introduc¸a˜o e definic¸o˜es ba´sicas.
Passeios eulerianos
Introduc¸a˜o histo´rica
O Problema das pontes de Ko¨nigsberg
Na cidade de Ko¨nigsberg, sete pontes cruzavam o rio Pregel, estabelecendo ligac¸o˜es entre duas
ilhas e entre as ilhas e as margens opostas do rio, conforme a ilustrac¸a˜o abaixo:
Figura 1.1: As pontes de Ko¨nigsberg
Problema: Seria poss´ıvel fazer um “passeio” pela cidade, cruzando cada ponte exatamente uma vez?
1
2 CAPI´TULO 1
Em 1736, Euler publicou um artigo demonstrando que tal passeio era imposs´ıvel. Mais importante
e´ o fato de Euler ter formulado um crite´rio geral para resolver o problema acima, o que e´ considerado
como o primeiro teorema da chamada TEORIA DOS GRAFOS, a qual possui desdobramentos e
aplicac¸o˜es nas mais diversas a´reas.
Definic¸a˜o 1.1. Um GRAFO e´ uma colec¸a˜o G = (N,A) constitu´ıda por um conjunto na˜o-vazio e
finito N de NO´S (ou pontos, ou ve´rtices) e um conjunto (finito) A de ARCOS (ou arestas), sendo
que cada arco liga dois no´s (na˜o necessariamente distintos).
Exemplos:
Figura 1.2: Exemplos de grafos
Um grafo e´ dito SIMPLES quando cada par de no´s e´ ligado por no ma´ximo um arco e nenhum
no´ e´ ligado a si pro´prio (nenhum lac¸o). Caso contra´rio, temos o chamado MULTIGRAFO.
Um arco e´ dito INCIDENTE nos no´s aos quais esta´ associado e vice-versa.
Um no´ e´ dito ISOLADO quando na˜o esta´ ligado a nenhum outro.
Dois arcos incidentes num mesmo no´ sa˜o ditos ADJACENTES. Dois no´s incidentes num mesmo
arco sa˜o ditos adjacentes.
O GRAU de um no´ e´ o nu´mero de arcos incidentes no no´, sendo que cada lac¸o conta como dois
arcos.
Introduc¸a˜o e definic¸o˜es ba´sicas.
Passeios eulerianos 3
Teorema 1.2. (Euler) A soma dos graus dos no´s de um grafo e´ igual ao dobro do nu´mero de arcos.
Prova: Ao somarmos os graus contamos cada arco duas vezes, uma vez em cada extremidade.
Corola´rio 1. O nu´mero de no´s de grau ı´mpar de todo grafo e´ sempre par.
De fato, se denotarmos por di o grau de cada no´ i no grafo G = (N,A) , temos:
2 ·#A =
∑
i∈ IN
di =
∑
di par
di +
∑
di ı´mpar
di
Como 2 ·#A e
∑
di par
di sa˜o pares, enta˜o
∑
di ı´mpar
di e´ par e para que a soma de nu´meros
ı´mpares seja par, devemos ter uma quantidade par de nu´meros ı´mpares.
Exerc´ıcio: Prove que numa festa com 51 pessoas existe sempre uma pessoa que conhece um
nu´mero par de outras pessoas.
Passeios eulerianos
Definic¸a˜o 1.3. Um PASSEIO entre os no´s i e j de um grafo e´ uma sequeˆncia alternante de
no´s e arcos, comec¸ando em um dos no´s i ou j e terminando no outro, tal que cada arco percorrido
e´ incidente aos no´s que o cercam na sequeˆncia. Um passeio e´ dito FECHADO quando comec¸a e
termina no mesmo no´.
Exemplo:
Figura 1.3: Um passeio entre os no´s 6 e 1
Um CAMINHO e´ um passeio que na˜o conte´m no´s repetidos. Dois no´s esta˜o CONECTADOS
se existe um caminho entre eles no grafo. Um grafo e´ dito CONEXO quando cada par de no´s esta´
conectado, caso contra´rio ele e´ dito DESCONEXO.
4 CAPI´TULO 1
Um passeio em um grafo e´ dito EULERIANO quando passa por todo arco exatamente uma vez.
A` luz das definic¸o˜es acima, o Problema das pontes de Ko¨nigsberg refere-se exatamente a` existeˆncia
ou na˜o de um passeio euleriano pela cidade (grafo), quando se considera as pontes como arcos e os
territo´rios (ilhas ou margens) como no´s:
Figura 1.4: Grafo correspondente a`s pontes de Ko¨nigsberg
O argumento de Euler para as pontes de Ko¨nigsberg: Consideremos um dos territo´rios
(ilhas ou margens), que chamaremos de territo´rio I. Suponhamos que o passeio na˜o comec¸a em I.
Enta˜o entramos em I pela primeira vez atrave´s de uma ponte que e´ incidente em I e sa´ımos de I por
outra ponte incidente em I. Cada entrada-e-sa´ıda de I corresponde ao uso de duas pontes. Como I
tem um nu´mero ı´mpar de pontes incidentes, na u´ltima vez que usamos uma ponte incidente em I,
entramos em I e na˜o podemos mais sair, ou seja, o passeio termina necessariamente em I. Assim, pelo
mesmo argumento, se o passeio comec¸a em qualquer territo´rio, deve necessariamente terminar nos
outros treˆs (contradic¸a˜o!), pois todos teˆm um nu´mero ı´mpar de pontes incidentes.
O argumento anterior leva ao seguinte teorema:
Teorema 1.4. (Euler)
(a) Se um grafo conexo tem mais que dois no´s com grau ı´mpar, enta˜o ele na˜o admite um passeio
euleriano.
(b) Se um grafo conexo tem exatamente dois no´s com grau ı´mpar, enta˜o ele admite passeio eu-
leriano e todo passeio euleriano tem que comec¸ar em um desses no´s de grau ı´mpar e terminar no
outro.
(c) Se um grafo conexo na˜o tem no´s com grau ı´mpar, enta˜o ele admite passeio euleriano e todo
passeio euleriano e´ fechado.
Exerc´ıcio: Prove a partir do teorema acima que um grafo conexo tem um passeio euleriano
fechado se, e somente se, todo no´ tem grau par.
Introduc¸a˜o e definic¸o˜es ba´sicas.
Passeios eulerianos 5
Exerc´ıcio: Quais dos grafos abaixo admitem um passeio euleriano? Em caso afirmativo, indique
um passeio euleriano.
Exerc´ıcio:
(a) Construa ou destrua UMA ponte em Ko¨nigsberg para que se tenha um passeio euleriano
(indique o passeio).
(b) Mostre como se pode ter um passeio euleriano fechado construindo mais DUAS pontes em
Ko¨nigsberg (indique o passeio).
(c) Mostre como se pode ter um passeio euleriano fechado construindo UMA ponte e destruindo
OUTRA em Ko¨nigsberg.
(d) O que ocorre se destruirmos DUAS pontes em Ko¨nigsberg?
6 CAPI´TULO 1
Cap´ıtulo 2
Ciclos hamiltonianos
Problema: Seis cidades (no´s) sa˜o ligadas por uma rede de estradas (arcos) conforme o mapa
(grafo) abaixo:
Um vendedor pretende, partindo de uma cidade, passar exatamente uma vez em cada uma das
demais cidades, terminando a viagem na cidade de origem.
E´ poss´ıvel realizar uma viagem nas condic¸o˜es acima?
Definic¸a˜o 2.1. Um CICLO e´ um passeio fechado no qual apenas o no´ inicial-terminal se repete.
Um CICLO HAMILTONIANO e´ um ciclo que conte´m todos os no´s de um grafo.
7
8 CAPI´TULO 2
Observac¸o˜es:
(a) O problema acima equivale a perguntar se o grafo formado admite um ciclo hamiltoniano.
(b) E´ claro que para um grafo admitir um ciclo hamiltoniano e´ NECESSA´RIO que ele seja conexo.
(c) Na˜o existem resultados gerais de caracterizac¸a˜o dos grafos que admitem ciclos hamiltonianos.
(d) Problema do caixeiro viajante: achar um ciclo hamiltoniano de custo mı´nimo, sendo o custo
de um ciclo a soma dos custos dos arcos percorridos no ciclo.
Proposic¸a˜o 2.2. Num ciclo com treˆs ou mais no´s sa˜o percorridos exatamente dois arcos incidentes
em cada no´ do ciclo.
Corola´rio 1. Um grafo que tenha treˆs ou mais no´s e algum no´ de grau menor ou igual a 1
na˜o admite um ciclo hamiltoniano.
Exerc´ıcio: Resolva o problema inicial (do vendedor e as seis cidades): indique um ciclo hamilto-
niano caso exista soluc¸a˜o ou prove que na˜o existe ciclo hamiltoniano algum.
Exerc´ıcio: Responda se os grafos abaixo admitem ou na˜o um ciclo hamiltoniano. Indique um
ciclo hamiltoniano em caso afirmativo ou prove que na˜o admite, no caso negativo.
Ciclos hamiltonianos 9
Exerc´ıcio: Um grafo G = (N,A) e´ dito BIPARTIDO quando seu conjunto N de no´s pode ser
particionado em DOIS subconjuntos tais que no´s pertencentes a um mesmo subconjuntos na˜o sa˜o
adjacentes.
(a) Prove que se um grafo bipartido G = (N,A) admite um ciclo hamiltoniano enta˜o os dois
subconjuntos da partic¸a˜o de N teˆm o mesmo nu´mero de elementos.
(b) Conclua que o grafo abaixo NA˜O ADMITE um ciclo hamiltoniano.
(c)Construa um grafo bipartido com um nu´mero par de no´s, todos com grau maior ou igual a
dois, e que na˜o admite um ciclo hamiltoniano.
10 CAPI´TULO 2
Cap´ıtulo 3
A´rvores
Problema: Atrave´s de cabos telefoˆnicos (arcos) entre pares de cidades (no´s), deseja-se configurar
uma rede de comunicac¸o˜es (grafo) entre as sete cidades do mapa abaixo, de modo que possa haver
comunicac¸a˜o entre cada par de cidades, ou seja, cada par de cidades esteja conectado por pelo menos
um caminho na rede de comunicac¸o˜es (o grafo e´ conexo).
(a) E´ poss´ıvel obter uma rede (grafo) conexa com exatamente um caminho conectando cada par
de cidades? (neste caso e´ fa´cil ver que o grafo sera´ MINIMALMENTE CONEXO, ou seja, a remoc¸a˜o
de qualquer arco ira´ tornar o grafo desconexo).
(b) Dentre todas as redes (grafos) conexas possivelmente obtidas na letra (a) acima, e´ poss´ıvel
obter uma de menor custo (O´TIMA)?
11
12 CAPI´TULO 3
Definic¸a˜o 3.1. Uma A´RVORE e´ um grafo simples tal que para cada par de no´s existe exatamente
um caminho que os conecta.
Observac¸o˜es:
(a) O problema inicial equivale a perguntar se e´ poss´ıvel formar uma a´rvore com os no´s (cidades)
dados e, em caso afirmativo, se existe uma a´rvore de menor custo.
(b) Um grafo G e´ uma a´rvore se, e somente se, G e´ conexo e a remoc¸a˜o de qualquer um de seus
arcos resulta em um grafo desconexo (uma a´rvore e´ um grafo MINIMALMENTE CONEXO).
(c) Uma a´rvore na˜o admite ciclos com treˆs ou mais no´s (pois se admitisse haveria mais de um
caminho conectando dois no´s) e a adic¸a˜o de um arco ligando dois no´s que na˜o eram ligados por um
arco gera um ciclo com treˆs ou mais no´s (uma a´rvore e´ um grafo MAXIMALMENTE LIVRE DE
CICLOS COM TREˆS OU MAIS NO´S).
Exemplos:
• PROCEDIMENTO DE CRESCIMENTO DE A´RVORE (como obter a´rvores)
- Comece com um simples no´.
- Repita o que se segue um nu´mero (FINITO) qualquer de vezes: Se G e´ o grafo ate´ enta˜o formado,
crie um novo no´ e ligue-o por um arco novo a qualquer no´ de G.
A´rvores 13
Teorema 3.2. Todo grafo obtido pelo procedimento de crescimento de a´rvore e´ uma a´rvore e toda
a´rvore pode ser obtida desta maneira.
Corola´rio 1. Toda a´rvore com n no´s tem n− 1 arcos.
• O ALGORI´TMO GULOSO DE KRUSKAL (encontrando a a´rvore o´tima)
- Considere n no´s e nenhum arco.
- Construa um arco de menor custo entre dois no´s distintos que na˜o estejam ligados por um arco
e de maneira que na˜o se obtenha um ciclo com treˆs ou mais no´s.
- Repita o procedimento acima ate´ que se tenha n− 1 arcos.
Teorema 3.3. Dados n no´s e nenhum arco, o Algor´ıtmo Guloso produz uma a´rvore de menor custo
(a´rvore o´tima) entre todas as poss´ıveis a´rvores com os n no´s inicialmente dados.
Observac¸a˜o: Uma tentativa de adaptac¸a˜o do Algor´ıtmo Guloso pode na˜o funcionar para obter
um ciclo hamiltoniano o´timo (Problema do caixeiro viajante).
Exerc´ıcio: (a) USANDO O PROCEDIMENTO DE CRESCIMENTO DE A´RVORE, resolva
a letra (a) do problema inicial, obtendo uma rede de comunicac¸o˜es minimalmente conexa entre as
cidades dadas. (b) Considerando os custos proporcionais a`s distaˆncias, USE O ALGORI´TMO GU-
LOSO e obtenha uma rede de comunicac¸o˜es minimalmente conexa e de menor custo poss´ıvel (o´tima)
entre as cidades dadas, resolvendo assim a letra (b) do problema inicial:
14 CAPI´TULO 3
Exerc´ıcio: Prove a Observac¸a˜o apo´s o Teo 3.3
(Sugesta˜o: considere os pontos A(0, 0), B(1, 0), C(0, 1) e D(9, 1))
Exerc´ıcio: Para cada um dos grafos dados abaixo, fac¸a o que se pede.
- Responda se o grafo e´ uma a´rvore.
- Se o grafo na˜o for uma a´rvore, justifique.
- Se o grafo for uma a´rvore, responda se e´ uma a´rvore de menor custo (custos proporcionais a`s
distaˆncias) considerando os no´s dados. Se na˜o for uma a´rvore de menor custo, exiba uma a´rvore de
menor custo com os no´s dados.
Cap´ıtulo 4
Emparelhamento em grafos
Problema: Temos um conjunto de seis tarefas (no´s) a ser realizadas e seis funciona´rios (no´s)
para realizar as tarefas. Quando um funciona´rio tem habilidade para realizar uma tarefa, ambos
sera˜o ligados por um arco.
Cada funciona´rio Fi tem habilidade para realizar um conjunto {Tj} de tarefas, conforme o grafo
abaixo:
E´ poss´ıvel atribuir exatamente uma tarefa a cada funciona´rio de modo que todas as tarefas sejam
realizadas?
15
16 CAPI´TULO 4
Definic¸a˜o 4.1. Uma grafo G = (N,A) e´ dito BIPARTIDO quando seu conjunto N de no´s pode ser
particionado em dois subconjuntos tais que os no´s pertencentes a um mesmo subconjunto na˜o sa˜o
adjacentes.
Um EMPARELHAMENTO PERFEITO em um grafo bipartido e´ um conjunto de arcos A′ ⊂ A
tal que cada no´ do grafo e´ incidente em exatamente um arco do conjunto A′.
Observac¸o˜es:
(a) O problema inicial equivale a perguntar se o grafo dado tem um emparelhamento perfeito.
(b) E´ claro que se um grafo bipartido G = (N,A) , sendo N = N1 ∪N2 a partic¸a˜o de N , tem
um emparelhamento perfeito enta˜o #N1 = #N2 e N e´ obrigatoriamente par.
Teorema 4.2. (Teorema do emparelhamento) Um grafo bipartido G = (N,A) , sendo N = N1∪N2
a partic¸a˜o de N , tem um emparelhamento perfeito se, e somente se, #N1 = #N2 e para qualquer
subconjunto N ′1 ⊂ N1 temos pelo menos #N ′1 no´s em N2 adjacentes aos no´s de N ′1.
Observac¸a˜o: Vale a simetria no teorema acima.
Corola´rio 1. Se em um grafo bipartido todo no´ tem mesmo grau d ≥ 1 , enta˜o o grafo conte´m um
emparelhamento perfeito.
Exerc´ıcio: Usando o Teorema 4.2, verifique se o problema inicial das seis tarefas para os seis
funciona´rios tem soluc¸a˜o.
Exerc´ıcio: Prove o Corola´rio do Teorema 4.2.
Exerc´ıcio: Desenhe um grafo cujos no´s sa˜o os subconjuntos de {a, b, c} e dois no´s sa˜o adjacentes
se, e somente se, eles sa˜o subconjuntos que diferem por exatamente um elemento.
(a) Qual e´ o nu´mero de arestas e no´s nesse grafo?
(b) Esse grafo e´ conexo? Ele tem um emparelhamento perfeito? (exiba um caso tenha) Ele admite
um ciclo hamiltoniano? (exiba um caso admita)
Emparelhamento em grafos 17
Exerc´ıcio: Verifique (justifique) se os grafos abaixo teˆm emparelhamentos perfeitos e exiba tais
emparelhamentos nos casos afirmativos.
Exerc´ıcio: Numa festa ha´ 286 convidados. Cada homem conhece 30 mulheres e cada mulher
conhece 30 homens (o conhecimento e´ mu´tuo). A organizac¸a˜o da festa deseja saber qual o nu´mero
ma´ximo de casais que podem estar danc¸ando simultaneamente para providenciar o espac¸o adequado.
Que nu´mero e´ esse? (prove).
18 CAPI´TULO 4
Cap´ıtulo 5
Grafos planares:
Colorindo grafos e mapas
Definic¸a˜o 5.1. Uma grafo simples e conexo e´ chamado PLANAR quando ele pode ser desenhado
como um mapa no plano: seus no´s correspondem a pontos distintos no plano e seus arcos sa˜o
curvas plana (ligando os no´s) as quais na˜o se intersectam em pontos que na˜o sejam os no´s.
EXEMPLO: K4 = grafo completo sobre 4 no´s = grafo com 4 no´s onde cada no´ esta´ ligado a
todos os demais:
Observac¸a˜o: Um grafo planar, quando representado de forma planar, divide o plano em uma
quantidade finita de regio˜es, sendo uma delas ilimitada e as demais (se existirem) limitadas.
19
20 CAPI´TULO 5
EXEMPLO:
Teorema 5.2. (Fo´rmula de Euler) Seja G um grafo planar. Se v e´ o nu´mero de no´s de G, a e´ o
nu´mero de arcos de G e f e´ o nu´mero de regio˜es do plano determinadas pela sua forma planar, enta˜o
v − a+ f = 2
Corola´rio 1. Um grafo planar sobre n ≥ 3 no´s tem no ma´ximo 3n− 6 arcos. (Exerc´ıcio)
Exerc´ıcio: Existem 3 casas e 3 fontes. Podemos construir um caminho de toda casa para toda
fonte de modo que esses caminhos na˜o se cruzem? (os caminhos na˜o sa˜o necessariamente linhas retas)
Exerc´ıcio: Prove que K5 (grafo completo sobre 5 no´s) na˜o e´ um grafo planar.
Exerc´ıcio: O grafo obtido pela omissa˜o de um arco de K5 e´ planar?
Exerc´ıcio: O Grafo de Petersen e´planar?
Grafos planares:
Colorindo grafos e mapas 21
• Colorindo grafos
Regra para colorac¸a˜o de grafos: no´s adjacentes teˆm que ser coloridos com cores diferentes.
Se podemos colorir um grafo com k cores (dentro da regra acima), dizemos que o grafo e´
k−COLORI´VEL.
O menor valor de k para o qual o grafo e´ k−color´ıvel e´ chamado de NU´MERO CROMA´TICO do
grafo.
Observac¸o˜es:
(a) E´ o´bvio que se um grafo tem n no´s enta˜o n cores sa˜o sempre suficientes para colori-lo (o grafo
e´ n−color´ıvel) e seu nu´mero croma´tico e´ menor ou igual a n.
(b) Um grafo e´ 2−color´ıvel se, e somente se, ele e´ bipartido.
Teorema 5.3. (Teorema de Brooks) Se todo no´ em um grafo tem grau no ma´ximo d, enta˜o o grafo
pode ser colorido com d+ 1 cores.
Exerc´ıcio: Obtenha o nu´mero croma´tico dos grafos a seguir:
A) K5
B)
C) Grafo de Petersen
D)
22 CAPI´TULO 5
• Colorindo mapas
Consideremos agora o problema de colorir um mapa que seja uma representac¸a˜o plana de diversas
regio˜es (pa´ıses, estados, etc.) CONEXAS (dois pontos de uma mesma regia˜o podem ser “ligados por
uma estrada dentro da pro´pria regia˜o”).
E´ natural pedirmos que regio˜es vizinhas (com fronteira de comprimento na˜o-nulo comum) tenham
cores diferentes.
IDE´IA: Cada regia˜o conexa sera´ representada por um no´ e regio˜es (no´s) vizinhas sera˜o ligadas
por um arco, formando assim um GRAFO DUAL do mapa original. O grafo dual assim obtido sera´
um grafo planar (desafio: tente provar) e o nosso problema de colorir o mapa original se reduz ao
problema de colorir seu grafo dual.
Exerc´ıcio: Obtenha os grafos duais (em suas representac¸o˜es planares) para os mapas dados
abaixo:
Exerc´ıcio: Obtenha os nu´meros croma´ticos dos grafos duais obtidos no exerc´ıcio anterior e colora
os grafos e os mapas segundo os nu´meros obtidos.
Exerc´ıcio: Deˆ exemplo de um mapa para mostrar que se admitirmos regio˜es desconexas, o grafo
dual obtido na˜o e´ necessariamente planar.
Teorema 5.4. (Teorema das 4 cores) Todo grafo planar pode ser colorido com 4 cores.
Corola´rio 1. Todo mapa que e´ representac¸a˜o planar de regio˜es conexas pode ser colorido com 4 cores.
Exerc´ıcio: Exiba um mapa que precise de mais do que 4 cores para ser colorido.
Grafos planares:
Colorindo grafos e mapas 23
Exerc´ıcio: Um grafo G′ e´ dito um SUBGRAFO de um grafo G quando G′ e´ obtido a partir de
G eliminando-se no´s (e seus arcos incidentes) ou arcos de G.
(a) Prove que se todo subgrafo de um grafo G tem um no´ de grau menor ou igual a d enta˜o G e´
d+ 1 color´ıvel. (Sugesta˜o: induc¸a˜o sobre o nu´mero de no´s de G)
(b) Prove que todo grafo planar tem um no´ de grau menor ou igual a 5. (Sugesta˜o: use o Corola´rio
do Teorema 5.2)
(c) Conclua que todo grafo planar pode ser colorido com 6 cores (“Teorema das 6 cores”)
24 CAPI´TULO 5
Refereˆncias
[1] Lova´sz, L. e outros, Matema´tica Discreta, Colec¸a˜o Textos Universita´rios, SBM, Rio de
Janeiro, 2003.
[2] Santos, J. P. O. e outros, Introduc¸a˜o a` Ana´lise Combinato´ria, Editora Unicamp, Campinas,
2002.
25