Aldemir M. de Oliveira

Obs: Muitos slides foram cedidos por Adolfo Almeida Duran (UFBA/UFPE)2011

Grafos / Matemtica Discreta*Porque estudar GrafosImportante ferramenta matemtica com aplicao em diversas reas do conhecimento Gentica, qumica, pesquisa operacional, telecomunicaes, engenharia eltrica, redes de computadores, conexo de vos areos, restries de precedncia, fluxo de programas, dentre outrosUtilizados na definio e/ou resoluo de problemas.Introduo

*Porque estudar GrafosEm computao: estudar grafos mais uma forma de solucionar problemas computveis

Os estudos tericos em grafos buscam o desenvolvimento de algoritmos mais eficientes.

Grafos / Matemtica Discreta*O que so Grafos

Tipicamente um grafo representado como um conjunto no vazio de pontos ou vrtices ligados por retas, que so chamadas de arestasFerramenta de modelagemAbstrao matemtica que representa situaes reais atravs de um diagrama.

Grafos / Matemtica Discreta*As pontes de Knigsberg

O rio Pregel divide o centro da cidade de Knigsberg (Prssia no sculo XVII, atual Kaliningrado, Rssia) em quatro regies. Essas regies so ligadas por um complexo de sete (7) pontes, conforme mostra a figura. Discutia-se nas ruas da cidade a possibilidade de atravessar todas as pontes, voltando ao lugar de onde se saiu, sem repetir alguma. Havia-se tornado uma lenda popular a possibilidade da faanha quando Euler, em 1736, provou que no existia caminho que possibilitasse tais restries.

*As pontes de KnigsbergResolvido em 1736 por Leonhard EulerNecessrio um modelo para representar o problemaAbstrao de detalhes irrelevantes:rea de cada ilhaFormato de cada ilhaTipo da ponte, etc.

Grafos / Matemtica Discreta*As pontes de KnigsbergEuler generalizou o problema atravs de um modelo de grafos

*As pontes de KnigsbergEuler mostrou que no existe o trajeto proposto utilizando o modelo em grafos Verifique nos grafos abaixo se o trajeto proposto possvel

Grafos / Matemtica Discreta*O problema das 3 casas possvel conectar os 3 servios s 3 casas sem haver cruzamento de tubulao?

gua luz telefoneA teoria dos grafos mostra que no possvel

*Quantas cores so necessrias para colorir o mapa do Brasil, sendo que estados adjacentes no podem ter a mesma cor?

Grafos / Matemtica Discreta*Questes sobre o caminho mnimoDe forma a reduzir seus custos operacionais, uma empresa de transporte de cargas deseja oferecer aos motoristas de sua frota um mecanismo que os auxilie a selecionar o melhor caminho (o de menor distncia) entre quaisquer duas cidades por ela servidas, de forma a que sejam minimizados os custos de transporte.

Grafos / Matemtica Discreta*

Grafos / Matemtica Discreta*Modelagem com grafos

Estamos interessados em objetos e nas relaes entre eles

Quem so eles nos problemas apresentados?

Como representar graficamente?

Grafos / Matemtica Discreta*Modelagem com grafosNo problema das casasVrtices so casas e serviosArestas so as tubulaes entre casas e serviosNo problema da colorao de mapasVrtices so estadosArestas relacionam estados vizinhosNo problema do caminho mais curtoVrtices so as cidadesArestas so as ligaes entre as cidades

*Trs desenvolvimentos isolados despertaram o interesse pela rea Formulao do problema das 4 cores (De Morgan 1852). Qual a quantidade mnima de cores para colorir um mapa de tal forma que pases fronteirios possuam cores diferentes? Apresenta-se um exemplo em que 3 cores no so suficientes. Uma prova de que 5 cores suficiente foi formulada. Conjecturou-se ento que 4 cores seriam suficientes. Esta questo ficou em aberto at 1976 quando Appel e Haken provaram para 4 cores

Grafos / Matemtica Discreta*Trs desenvolvimentos isolados despertaram o interesse pela rea

Problema do ciclo Hamiltoniano (Hamilton 1859) Existem n cidades. Cada par de cidades pode ser adjacente ou no arbitrariamente. Partindo de uma cidade qualquer, o problema consiste em determinar um trajeto que passe exatamente uma vez em cada cidade e retorne ao ponto de partida.

Grafos / Matemtica Discreta*Trs desenvolvimentos isolados despertaram o interesse pela rea

Teoria das rvores - Kirchoff (1847) - problemas de circuitos eltricos - Cayley (1857) - Qumica Orgnica

Grafos / Matemtica Discreta*Dois tipos de elementosVrtices ou nsArestasDefiniesv1v2v3v4v5v6

Grafos / Matemtica Discreta*G = (V,E)V um conjunto finito no-vazio de vrtices (ou ns)E um conjunto de pares no ordenados de elementos distintos de V, chamados de arestasCada aresta e pertencente ao conjunto E ser denotada pelo par de vrtices {x,y} que a formaDizemos que os vrtices x e y so extremos (ou extremidades) da aresta e.Grafo Simples

Grafos / Matemtica Discreta*G = (V,E)

*Dois vrtices x e y so ditos adjacentes ou vizinhos se existe uma aresta e unindo-os. Os vrtices u e v so ditos incidentes na aresta e, se eles so extremos de e. Duas arestas so adjacentes se elas tm ao menos um vrtice em comum. A aresta e={x,y} incidente a ambos os vrtices x e y.

Grafos / Matemtica Discreta*v1v2v3v4v5v6e1V = {v1, v2, v3, v4, v5, v6}E = {{v1,v2},{v1,v3},{v1,v4},{v2,v4},{v3,v4},{v4,v5}}Grafo simplese1 incidente a v4 e v5

*ExemploExerccioDesenhe a representao geomtrica do seguinte grafo simples: V = {1,2,3,4,5,6}; E ={(1,2),(1,3),(3,2),(3,6),(5,3),(5,1),(5,6),(4,6), (4,5),(6,1),(6,2),(3,4)}

Grafos / Matemtica Discreta*Multigrafo G=(V,E)Funo f de E em {{u,v } | u,v V,u v }As arestas e1 e e2 so chamadas de arestas mltiplas ou paralelas se f(e1) = f(e2)

Lao uma aresta formada por um par de vrtices idnticos. Pseudografo G=(V,E)Funo f de E em {{u,v } | u,v V}Permitem laos: f(e) = {u,u}={u}Mais definies

Grafos / Matemtica Discreta*ExerccioDefina formalmente o grafo abaixo e identifique os conceitos de lao, aresta mltipla e multigrafo no mesmo:

Grafos / Matemtica Discreta*Grau de um vrticeGrau de um vrtice v (grau(v)) o nmero de arestas que incidem em v. O grau de um vrtice v tambm pode ser definido como o nmero de arestas adjacentes a v.Obs.: Um lao conta duas vezes para o grau de um vrtice Grau(b) = 3Grau(d) = 2Grau(a) = 2

Grafos / Matemtica Discreta*Qualquer vrtice de grau zero um vrtice isolado

Qualquer vrtice de grau 1 um vrtice pendente

Um vrtice mpar tem um nmero mpar de arestas

Um vrtice par, tem um nmero par de arestas

Grafos / Matemtica Discreta*

Grafo Regular (k-regular) todos os vrtices tm o mesmo grau (k)

v1v2v4v3

Grafos / Matemtica Discreta*v1v2v3v4v5v6e1V6 um vrtice isolado, grau(v6)=0V5 um vrtice pendente, grau(v5)=1V2 um vrtice par, grau(v2)=2V1 um vrtice mpar, grau(v1)=3

Grafos / Matemtica Discreta*ExerccioIdentificar no grafo abaixo os vrtices isolados, pendentes, mpares e pares. ReflexoO que podemos concluir sobre a soma dos graus de um grafo?

Grafos / Matemtica Discreta*Soma dos graus de um grafo:O resultado sempre par, e corresponde formula abaixo:

A prova inspirada no Teorema do Aperto de Mos que diz: Se vrias pessoas se apertam a mo o nmero total de mos apertadas tem que ser par. Precisamente porque duas mos esto envolvidas em cada aperto.

Grafos / Matemtica Discreta*Soma dos graus de um grafo:

Em grafos, cada aresta contribui duas unidades para o cmputo geral do grau dos vrtices, pois cada aresta possui dois extremos. Portanto, a soma total par e duas vezes o nmero de arestas do grafo. Se o grafo for regular de grau r, a soma dos graus dos vrtices tambm igual a r vezes o nmero de vrtices.

Grafos / Matemtica Discreta*A soma dos graus de um grafo sempre par:

Quando o grafo regular de grau r, temos:

Grafos / Matemtica Discreta*Corolrio Em qualquer grafo, o no de vrtices com grau mpar deve ser PAR ProvaPara a soma ser par, o primeiro somatrio tem que gerar um resultado par, portanto |Vmpar| par.

Grafos / Matemtica Discreta*Grafo Nulo (vazio) Grafo cujo nmero de arestas zero. Ou, grafo regular de grau zero.

Outros tipos de grafos1432Nn um grafo nulo com n vrtices Exemplo: N4 V={1,2,3,4}; E={ }.

Grafos / Matemtica Discreta*Grafo Completo Grafo simples em que existe exatamente uma aresta entre cada par de vrtices distintos. Ou, grafo regular de grau n-1, onde n=|V|. Kn um grafo completo com n vrtices.

Exemplo: K4

Grafos / Matemtica Discreta*Quantas arestas tem o Kn? Veja que |E| = ( r * |v| ) / 2, onde r o grau e v o nmero de vrtices. Logo |E| = (( n - 1 ) n ) / 2 Podemos provar tambm com anlise combinatria. O nmero de arestas igual ao nmero de combinaes de n vrtices dois a dois. Cn,m = n! / ( m! (n m)! )

Grafos / Matemtica Discreta*Complemento de um grafo Seja G um grafo simples com um conjunto de vrtices V. G complemento de G se

V = V edois vrtices so adjacentes em G, se e somente se, no o so em G

Grafos / Matemtica Discreta*Complemento de um grafo

Grafos / Matemtica Discreta*Complemento de um grafoExerccio:

D exemplos que confirmem as propriedades acimaPropriedade 1Um grafo regular tem complemento regularPropriedade 2 O complemento de Kn Nn

Grafos / Matemtica Discreta*Grafo BipartidoUm grafo dito ser bipartido quando seu conjunto de vrtices Vpuder ser particionado em dois subconjuntos V1 e V2, tais que toda aresta de G une um vrtice de V1 a outro de V2. 143256V1V2

*Grafo BipartidoSejam os conjuntos H={h | h um homem} e M={m | m um mulher} e o grafo G(V,E) onde:

V = H U M E = {{v,w} | (v H e w M) e }

Grafos / Matemtica Discreta*Grafo Bipartido Completo Km,n,n um grafo bipartido em V1 e V2, sendo que cada elemento de V1 adjacente a cada elemento de V2.|V1| = m e |V2|=nK3,3V1V2

Grafos / Matemtica Discreta*Subgrafo Um grafo Gs(Vs, As) dito ser subgrafode um grafo G(V,A)quando Vs V e As A. O grafo G2, por exemplo, subgrafo de G1

G1G2

Grafos / Matemtica Discreta*Subgrafo PrprioUm subgrafo G2 dito prprio, quando G2 subgrafo distinto de G1Subgrafos podem ser obtidos atravs da remoo de arestas e vrtices.

Grafos / Matemtica Discreta*Subgrafo InduzidoSe G2 um subgrafo de G1 e possui toda a aresta (v, w) de G1 tal que ambos, v e w, estejam em V2, ento G2 o subgrafo induzido pelo subconjunto de vrtices V2.32145V1= {1,2,3,4,5}G13214V2= {1,2,3,4}G2V2 induz G2

Grafos / Matemtica Discreta*CliqueDenomina-se clique de um grafo G a um subgrafo (induzido) de G que seja completo

Grafos / Matemtica Discreta*Isomorfismo de GrafosDois grafos simples G1 e G2 so isomorfos se existe uma correspondncia um a um entre os vrtices (funo f ) de G1 e G2, com a propriedade de que a e b so adjacentes em G1 se e somente se f(a) e f(b) so adjacentes em G2, para todo a,b V1.

A funo f chamada de isomorfismo.

Grafos / Matemtica Discreta*Isomorfismo de Grafos (em outras palavras)Sejam dois grafos G1(V1,A1) e G2(V2,A2). Um isomorfismo de G1 sobre G2 um mapeamento bijetivo f: V1 V2 tal que {x,y} A1 se e somente se {f(x),f(y)} A2, para todo x,y V1. Funo: { (a2), (b 1), (c 3), (d 4), (e 6), (f 5) }

Grafos / Matemtica Discreta*Isomorfismo de Grafos (exemplo)f(u) = azul, f(v) = lils, f(w) = vermelho,f(x) = verde, f(y) = amarelo, f(z) = rosa

Grafos / Matemtica Discreta*Isomorfismo de Grafos Preserva:

Simetria: G1 G2 G2 G1Reflexividade: G1 G1Transitividade: G1 G2 e G2 G3 G1 G3

Proposies vlidas se G1 G2 (invariantes)

G1 e G2 tm o mesmo nmero de vrticesG1 e G2 tm o mesmo nmero de arestasG1 e G2 tm os mesmos graus de vrtices