Universidade Federal de Minas GeraisInstituto de Ciencias ExatasDepartamento de MatematicaGrafos, Matrizes e o Teorema da AmizadeGleicyTerezinhaFerreiraCesarOrientador: Prof. AlbertoSarmientoBeloHorizonte,setembrode2007iDedicatoriaA meus lhos Joao pedro e Maria LuzaiiAgradecimentosComeco meus agradecimentos agradecendo a Deus, por que sem ele nada epossvel. A Alberto Berly Sarmiento Vera, professor coordenador desta mono-graa e cujo empenho em sua realizacao foi muito importante para a conclusao.Agradecotambemaosmeuspaisquenuncamedemesforcosparaqueeudecontinuidade a meus estudos. A todos os amigos(as) que z durante o curso, emespecial a meu conterraneo e co-piloto Fabio. Ao Romulo por ter sido pacienteaminhasausencias. Emmagradecoatodosquedeumaformaoudeoutracontriburam para que eu chegasse ate o m.iiiSumario1 NocoesbasicasdeAlgebraLinear 21.1 Matrizes, Autovalor e Autovetor . . . . . . . . . . . . . . . . . . 21.2 Diagonalizacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Determinantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 GrafoseCaminhos 142.1 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2 Matriz de Adjacencia . . . . . . . . . . . . . . . . . . . . . . . . . 172.3 N umero de Caminhos Possveis . . . . . . . . . . . . . . . . . . . 183 TeoremadaAmizade 233.1 Demonstracao do teorema da amizade . . . . . . . . . . . . . . . 28Apendice: Interpolacao Polinomial.1 Interpolacao Polinomial . . . . . . . . . . . . . . . . . . . . . . . 30.2 Formula da Interpolacao de Lagrange . . . . . . . . . . . . . . . 31References 33SUMARIO 1INTRODUC AOEsta monograa trata-se do estudo do Teorema da amizadeO captulo 1 introduz denicoes basicas: Matrizes,Autovalor e Autovetor,Diagonalizaaoepor mDeterminantes. Essas denicoes seraousadas parademonstracao do Teorema da Amizade.No captulo 2 denimos os tipos,o comprimento de um caminho,o grau eociclodeumgrafo. Exemplicamosasvariasformasderepresentacao,comoamatrizdeadjacencia. EparanalizaressecaptulooN umerodecaminhosPossveis.Ocaptulo3eo ultimo, esseededicadoademonstracaodoTeoremadaAmizade. Comecando relatando o problema seguindo da sua representa cao naversao de grafos e matricial, logo apos provamos diversos lemas essenciais parasuademonstracao. Nasegundapartedessecaptulotemos ademonstracaopropriamente dita, divida em:A. Se u e um vertice de grau maximo e x um vertice de grau nao maximo, entaox e adjacente au (x u).B. Existe um unico vertice de grau maximo.2Captulo1Noc oesbasicasdeAlgebraLinear1.1 Matrizes,AutovaloreAutovetorUma matriz A, mn (m por n), e uma tabela de mn n umeros dispostos emmlinhas e ncolunasA =__a11a12. . . a1na21a22. . . a2n... . . ....am1am2. . . amn__.A i -esima linha de A eV= _ai1ai2. . . ainparai = 1, . . . , m e a j -esima coluna de A eV=__a1ja2j...amj__paraj= 1, . . . , n. Usamos tambem a notacaoA = (aij)mxn. Dizemos queaijou [A]ije o elemento ou a entrada de posicaoi, jda matriz A. Sem = n, dize-mos que A e uma matriz quadrada de ordem ne os elementosa11, a22, . . . , annformam a diagonal (principal) de A.UmamatrizquadradaA=(aij)nxneinvertvelounaosingular, seexisteuma matrizB = (bij)nxntal queAB = BA = In,CAPITULO1. NOCOESBASICASDEALGEBRALINEAR 3em queIn e a matriz identidade. A matriz B e chamada de inversa de A. Se Anao tem inversa, dizemos que A e nao invertvel ou singular.Denicao 1.1. Seja A uma matriz de ordemn n. Um n umero e chamadoautovalor de A, se existe um vetor nao nuloV=__v1v2...vn__de Rntal que (AI)V= 0.Umvetornaonuloquesatisfazaequacaoacima, echamadoautovetordeA.Paracada, osautoespacoassociadosasaoosvetoresnaonulosdasolucao do sistema acima.Seja A uma matrizn n.(a) Os autovalores (reais) de A sao as razes reais do polinomiop(t) = det(AtIn)(b) Para cada autovalor , os autovetores associados a sao os vetores naonulos da solucao do sistema(AIn)X = 0.Denicao1.2. Seja A uma matriznxn. O polinomiop(t) = det(AtIn)e chamado polinomio caracterstico de A.Exemplo1. : Vamos determinar os autovalores e autovetores da matriz:A =__2 0 12 1 21 0 2__Para isto, calculamos:SolucaoP() = det.(A.I) = det__2 0 12 1 21 0 2 __ =(2 ).(1 ).(2 ) [1.(1 ).1] = 0(1 ).(2 )2(1 ) = 0 (1 )((2 )21) = 0CAPITULO1. NOCOESBASICASDEALGEBRALINEAR 4(1 )2(3 ) = 0Como os autovalores de A sao as razes reais dep(), temos que os autovaloresde A sao1 = 1 e2 = 3. Agora, vamos determinar os autovetores associadosaos autovalores1 = 1 e2 = 3.Para isto vamos resolver os sistemas (A 1I3)X= 0 e (A 2I3)X= 0.O sistema (A1I3)X = 0 e__1 0 12 0 21 0 1__.__xyz__ =__000__Resolvendo o sistema temosx + z = 0, vamos fazerz = entaox = ey = a nossa solucao geral e (, , ) = (, 0, ) + (0, , 0) = (1, 0, 1) +(0, 1, 0), logo os autovetores que geraoW1 sao (1, 0, 1) e (0, 1, 0)ondeW1 = [(; ; )/, R], que e o conjunto de todos os autovetores asso-ciados a1 = 1 acrescentado o vetor nulo.Enquanto o sistema (A2I3)X = 0 e__1 0 12 2 21 0 1__.__xyz__ =__000__Resolvendo agora esse sistema gerado pela matriz acima temos x + z = 0,vamoschamarz=entaox=ey=2easolucaogerale(, 2, )=(1, 2, 1) , logo os autovetores que geramW2 sao (1, 2, 1) que e o conjunto detodos os autovetores associados a2 = 3 acrescentado o vetor nulo.1.2 DiagonalizacaoCertos processos sao descritos em cada estagio por uma matriz A quadradae em k estagios pela potencia k da matriz A, Ak, em que k e um n umero inteiropositivo. Suponha que desejamos saber a matriz que corresponde a kestagios,para kum inteiro positivo qualquer. Se a matriz A e diagonal,A =__10 . . . 00 2. . . 0.........0 . . . 0 n__, entaoA =__k10 . . . 00 k2. . . 0.........0 . . . 0 kn__,Se a matriz A nao e diagonal, mas existe uma matriz P tal queA = PDP1, em queA =__10 . . . 00 2. . . 0.........0 . . . 0 n__,CAPITULO1. NOCOESBASICASDEALGEBRALINEAR 5A2= (PDP1)(PDP1) = PD(P1P)DP1= PD2P1.queAk1= PDk1P1, temos queAk= Ak1A = (PDP1)k1(PDP1)= (PDk1P1)(PDP1) = PDk1(P1P)DP1PDkP1= P__k10 . . . 00 k2. . . 0.........0 . . . 0 kn__P1podemos facilmente encontrar a k-esima potencia de A.SejaA =_1 14 1_,P=_1 12 2_eD =_3 00 1_ sao tais queA = PDP1.Assim,Ak= PDKP1=_1 12 2_ _3k00 (1)k_ _1 12 2_1Ak= PDP1=_3k(1)k23k2(1)k_14_2 12 1_ =14_2(3k+ (1)k) (1)k3k4((1)k3k) 2(3k+ (1)k)_Denicao 1.3. Dizemos que uma matriz A, de ordem nn, e diagonalizavel,se existem matriz quadrada invertvel P ematrizdiagonal DtaisqueA = PDP1, ou equivalentemente,D = P1AP.Suponhamos que a matriz A e diagonalizavel, como na denicao acima.Dado o polinomiof(x) = a0 + a1x + a2x2+ . . . + anxnPodemos calcular o polinomio na matriz A da seguinte formaf(A) = a0I..=PIP1+a1A..=PDP1+a1A2..=(PDP1)2+. . . + anAn..=(PDP1)nf(A) = a0(PIP1) + a1(PDP1) + a2(PD2P1) + . . . + an(PDnP1)Logo:f(A) = Pa0IP1+ P(a1D)P1+ P(a2D2)P1+ . . . + P(anDn)P1= P(a0IP1+ (a1D)P1+ (a2D2)P1+ . . . + (anDn)P1)= P((a0I + a1D + a2D2+ . . . + anDn)P1CAPITULO1. NOCOESBASICASDEALGEBRALINEAR 6f(A) = P(f(D))P1Concluindo, e mais facil obterf(D) do quef(A).Denicao1.4. Uma matriz quadradaA = (aij) de ordem n tal queaij= aji,i = j, ou seja,A = At, e chamada dematrizsimetrica.Exemplo2. A =__3 5 65 2 46 4 8__ e simetricapoisA = AtSeA eumamatrizsimetrica, entaoexisteumamatrizPinvertveleumamatriz diagonal D tal queD = P1AP.Assim, se A e simetrica, entao ela e diagonalizavel.Lema1.1. : Sejam1, 2, . . . , nautovaloresdamatrizAdiagonalizavel deordemn n. Sefegsao polinomios tais que:f(i) = g(i), para todoi = 1, 2, 3, . . . , n. f(A) = g(A)Prova: Seja P a matriz invertvel tal queA =PDP1onde D e a matrizdiagonal correspondente, na diagonal aparecem os autovalores de A. Entao, daobservacao anteriorf(A) = Pf(D)P1= P__f(1) 0f(2)...0 f(n)__P1P__g(1) 0g(2)...0 g(n)__P1== Pg(D)g1= g(A)CAPITULO1. NOCOESBASICASDEALGEBRALINEAR 71.3 DeterminantesVamosinicialmentedenirodeterminantedematrizes1 1. Paracadamatriz A = [a] denimos o determinante de A, indicado por det(A), por det(A)= a. Vamos, agora, denir o determinante de matrizes 22 e a partir da vamosdenir para matrizes de ordem maior. A cada matriz A, 2 2, associamos umn umero real, denominado determinante de A, por:det(A) = det_a11a12a21a22_ = a11a22 a21a12Para denir o determinante de matrizes quadradas maiores, precisamos deniro que sao os menores de uma matriz. Dada uma matrizA = (aij)nn, xado oelementoaij, denotado porAij, e a submatriz (n 1) (n 1) de A obtidaeliminando-se a i-esima linha e a j-esima coluna de A.Por exemplo, seA = (aij)33,A =__a11a12a13a21a22a23a31a32a33__ A11 =_a22a23a32a33_ A2,3_a11a12a31a32_Agora, vamos denir os cofatores de uma matriz quadrada A = (aij)nn. Ocofator do elementoaij, denotado por aij, e denido poraij = (1)i+jdet(Aij);ou seja, o cofatoraij, do elementoaije igual a mais ou menos o determinantedo menorAij, o sinal (1)i+j; da a seguinte regra: para os termos da diagonal(i, j) e psempre positivo, a partir disto vemos que o sinal alterra, assim, no caso4x4 ca:,__+ + + ++ + + +__Exemplo3. Vamos, agora, denir o determinante de uma matriz 3 3. SeA =__a11a12a13a21a22a23a31a32a33__entao, o determinante de A xada a primeira linha e igual `a soma dos produtosdos elementos da primeira linha pelos seus cofatores.det(A) = a11a11 + a12a12 + a13a13 =CAPITULO1. NOCOESBASICASDEALGEBRALINEAR 8a11det_a22a23a32a33_a12det_a21a23a31a33_+ a13det_a21a22a31a32_= a11(a22a33 a32a23) + a12(a21a33 a31a23) + a13(a21a32 a31a22).Da mesma forma que a partir do determinante de matrizes 2 2, denimoso determinante de matrizes 3 3, podemos denir o determinante de matrizesquadradas de ordem maior. Supondo que sabemos como calcular o determinantede matrizes (n 1) (n 1)Vamos denir o determinante de matrizesn n.SejaA = (aij)nn. O determinante de A, denotado por det(A), e denidopor det(A)=a11a11 + a12a12 + + a1na1n= nj=1 a1ja1j; emque a1j=(1)1+jdet(A1j) eocofatordoelementoa1j. Aexpressao echamadadesen-volvimento em cofatores do determinante de A em termos da 1a. linha.SejaA = (aij) uma matriz de ordemn n, denotemos porv1, v2, . . . , vnaslinhas da matriz A, assim temos:A =__v1v2...vn__SejaA = (aij) uma matriz de ordemn n, denotemos porc1, c2, . . . , cnascolunas da matriz A, assim temos:A = _c1c2. . . cnO determinante e uma funcao que associa cada matriz quadrada um escalar,satisfazendo as seguintes propriedades:1. O determinante da matriz identidade e 1A = det__1 0 . . . 00...0.........0 . . . 0 1__= 12. O determinante troca de sinal se duas linhas ou colunas forem trocadas deposicao.3. Se uma la (linha ou coluna) da matriz e composta de zeros, entao o deter-minante desta matriz sera zero.CAPITULO1. NOCOESBASICASDEALGEBRALINEAR 94. Se uma linha de A e soma de dois vetores digamos v +w o det(A) segue estaregra:det(A) = det__v1v2...v + w...vn__= det__v1v2...v...vn__+ det__v1v2...w...vn__=5. Sevi = kvdet =__v1v2...kv...Vn__=k.det__v1v2...v...Vn__6. Seduaslinhasparalelasdeumamatrizforemiguais, ouproporcionais, odeterminante desta matriz e nulo.Das propriedades anteriores temos que:Odeterminantenao ealteradoseumalinhaoucolunaforsubstitudaporessa mesma linha ou coluna somada a uma combinacao linear das outras linhas.Isto e:det =__v1...vi...vj + kvi...vn__=det__v1...vi...vj...vn__Com efeito,det =__v1...vi...vj + kvi...vn__4..= det__v1...vi...vj...vn__+ kdet__v1...vi...vi...vn__CAPITULO1. NOCOESBASICASDEALGEBRALINEAR 10Como__v1...vi...vi...vn__= 0EntaoA =__v1...vi...vj + kvi...vn__=det__v1...vi...vj...vn__A =__v1...vi...vj + kvi...vn__=__v1...vi...vj...vn__Oseguintelemaeumresultadofundamental pararesolveroteoremadaamizade no captulo 3.Lema1.2. :det(A) = det__t 1 . . . 11 t . . . 11 1 t.........11 . . . t__nn=(t 1)n1(t + n 1)Prova:CAPITULO1. NOCOESBASICASDEALGEBRALINEAR 11A =__v1v2v3...vn__=__v1 v2v2v3...vn__=__v1 v2v2 v3v3...vn__=. . . =__v1 v2v2 v3v3 v4...vn1 vnvn__=Realizando essa sequencia de operacoes na matriz A temos o seguinte resul-tadoA =__t 1 1 t 0 0 . . . 00 t 1 1 t 0 . . . 0... 0 t 1 1 t . . . 0...... 0......0............t 1 1 t1 1 1 . . . 1 t__Notemos que em cada linha podemos fatorar o termo (t 1), por exemplona linha 1, e da forma:(t 1)_1 1 0 0 0 0 0 Pelas propriedades do determinante temos quedet(A) = det(A).Logo:det(A) = (t1)n1. det__1 1 0 0 . . . 00 1 1 0 . . . 00 0 1 1 . . . 0..................0 0 0 . . . 1 11 1 1 . . . 1 t__nn= (t1)n1. det(u)Paramostrarolema, basta calcular que odeterminantedamatrizUe(t + n 1). Paraissovamoscalcularodeterminanteporcofatorxandoaprimeira linha.Assim:det(U) = det__1 1 0 0 . . . 00 1 1 0 . . . 00 0 1 1 . . . 0..................0 0 0 . . . 1 11 1 1 . . . 1 t__(n1)(n1)+CAPITULO1. NOCOESBASICASDEALGEBRALINEAR 12det__0 1 0 0 . . . 00 1 1 0 . . . 00 0 1 1 . . . 0..................0 0 0 . . . 1 11 1 1 . . . 1 t__(n1)(n1)Vamos calcular a segunda parcela e veremos que e 1:det__0 1 0 0 . . . 00 1 1 0 . . . 00 0 1 1 . . . 0..................0 0 0 . . . 1 11 1 1 . . . 1 t__(n1)(n1)Fixandoaprimeiralinha, odeterminante eigualaodeterminantedeumamatriz semelhante porem de ordem (n 2) (n 2). Com o mesmo processoobteremos uma matriz (n 3) (n 3) e assim sucessivamente ate chegarmosem uma matriz 3 3 que e:= det__0 1 00 1 11 1 t__ = det_0 11 t_ = 1Podemos concluir quedet(U) = det__1 1 0 0 . . . 00 1 1 0 . . . 00 0 1 1 . . . 0..................0 0 0 . . . 1 11 1 1 . . . 1 t__(n1)(n1)+ 1Novamente xamos a 1alinha temos:det(U) = det__1 1 0 0 . . . 00 1 1 0 . . . 00 0 1 1 . . . 0..................0 0 0 . . . 1 11 1 1 . . . 1 t__(n2)(n2)+CAPITULO1. NOCOESBASICASDEALGEBRALINEAR 13det__0 1 0 0 . . . 00 1 1 0 . . . 00 0 1 1 . . . 0..................0 0 0 . . . 1 11 1 1 . . . 1 t__(n2)(n2)+ 1Entao:det(U) = det__1 1 0 0 . . . 00 1 1 0 . . . 00 0 1 1 . . . 0..................0 0 0 . . . 1 11 1 1 . . . 1 t__(n2)(n2)+ 2det(U) = . . . =det(U) = . . . = det__1 1 00 1 11 1 t__(n(n3))(n(n3))+ (n 3)det(U) == 1(t + 1) + (1) + n 3 = t + 1 + 1 + n 3 = t + n 1.14Captulo2GrafoseCaminhosLeonhardEuler emSetePontes deKonigsbergeconsideradooprimeiroresultado da teoria dos grafos.E tambem considerado um dos primeiros resul-tadostopologicosnageometria; isto e,naodependentedequaisquermedidas.Isso ilustra a profunda conexao entre a teoria dos grafos e topologia.A palavra graco e, muitas vezes, usada para qualquer representa cao visualde dados, outras formas incluem o graco de barras, o graco pictorio e o gracoem setores. Os gracos que trataremos agora sao chamados de grafos. Usaremosduas denicoes de grafos: uma e baseada em uma representa cao visual e a outrae uma denicao mais formal que nao fala nada sobre uma representacao visual.Osgrafossaogeralmenterepresentadosgracamentedaseguintemaneira:e desenhado um crculo para cada vertice, e para cada aresta e desenhado umarcoconectandosuasextremidades. Seografofordirecionado, seusentidoeindicado na aresta por uma seta.Note que essa representacao graca (o layout) nao deve ser confundida com ografo em si (a estrutura abstrata, nao-graca). Varios diferentes layouts podemcorresponder ao mesmo grafo2.1 GrafosA Teoria dos Grafos e uma area da Matematica que estuda as propriedadesde grafos , principalmente na representa cao de circuitos e redes de comunicacao:Umgrafo eumconjuntonaovaziodenos(vertices)eumconjuntodearcos(arestas) tais que cada arco conecta dois nos. Dependendo da aplicacao, arestaspodem ou nao ter direcao, pode ser permitido ou nao arestas ligarem um verticea ele proprio e vertices e/ou arestas podem ter um peso (numerico) associado. Seas arestas tem uma direcao associada (indicada por uma seta na representacaograca) temos um grafo direcionado, ou dgrafo.Umgrafocomum unicoverticeesemarestaseconhecidocomoografotrivial ou o ponto.CAPITULO2. GRAFOSECAMINHOS 15Denicao2.1. Umgrafo que denotamos por G(V, A), ondeV e um conjunto nao vazio de nos (vertices)A e um conjunto de arcos (arestas)G e uma funcao que associa cada arco a um par nao ordenado de nos, chama-dos as extremidades de a.Denicao2.2. Doisverticesdografosaoconsideradosadjacentesseexisteuma aresta ligando eles.Exemplo 4. Neste exemplo iremos ligar pessoas amigas com uma aresta e cadapessoaseraumvertice. NotemosqueMaria eamigadePedro,Pedro eamigode Joana e Luiz, Maria e amiga de Joana mas Joana e Maria nao sao amigasde LuizMaria PedroJoanasssssssssLuizFigura 1Denicao2.3. Dado um grafo G, umcaminho no grafo e uma sequencia deverticesv1, v2, . . . , vkde modo que todo par de verticevi, vi+1sao adjacentes.Um caminhoechamadosimples se nenhum dos vertices no caminho serepete.Doiscaminhos saoindependentessenaotiveremnenhumverticeemcomum, exceto o primeiro e o ultimo.Denicao 2.4.Considerando cada aresta como um caminho a percorrer, dene-se o comprimentodeumcaminho como sendo o n umero de arestas a serempercorridas para se deslocar de um vertice a outro.6bbbbbbb4 5bbbbbbb13 2gura 3CAPITULO2. GRAFOSECAMINHOS 16DadoografocomconjuntodeverticesV = {1, 2, 3, 4, 5, 6}econjuntodearestasE = {(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)}(ver gura 3)Nografoanterior, osvertices1e2saoadjacentes, masosvertices2e4naosao. Oconjuntodevizinhosdeumverticeconsistedetodososverticesadjacentesaele. Nografo-exemplo, overtice1possui2vizinhos: vertice2evertice 5.No grafo de exemplo 3, (1, 2, 5, 1, 2, 3) e um caminho com comprimento 5, e(5, 2, 1)e um caminho simples de comprimento 2. Se for possvel estabelecer um cam-inho de qualquer vertice para qualquer outro vertice de um grafo, diz-se que ografo e conexo.Denicao2.5. UmgrafoG(V,A)editoserconexosehapelomenosumcaminho ligando cada par de vertices deste grafo G.x1x2x3x4x5x6gura 4Denicao 2.6. Umgrafo G(V,A) e dito ser desconexo se ha pelo menos umpar de vertices que nao esta ligado por nenhum caminho.x1x2x3x4x5x6gura 5Denicao2.7. Umverticeechamadodevertice parseesomenteseumn umero par de arestas partem desse vertice. Para um n umero mpar de arestaspartindo do vertice, o mesmo e chamado de vertice mpar.Com relacao aos vertices e arestas de um grafo temos as propriedades:P1 - A quantidade de vertices mpares e sempre par.P2 - So e possvel sair de um vertice e retornar ao mesmo percorrendo todasas arestas se todos os vertices forem pares.GrauO grau de um vertice e dado pelo n umero de arestas que lhe sao incidentes.Em gura 1, por exemplo: grau (Pedro)= 3CAPITULO2. GRAFOSECAMINHOS 17 grau (Maria)= 2Grafo Regular Se todos os vertices do grafo tem o mesmo grau d, dizemosque o grafo e regular. Um grafo e dito ser regular quando todos os seus verticestem o mesmo grau. O grafo G4, por exemplo, e dito ser um grafo regular-3 poistodos os seus vertices tem grau 3.CicloCiclodeumgrafoeumcaminhofechado. Emtermos umtantovagos,umcicloemumgrafoeumcaminhofechadosemvertices repetidos. Maisprecisamente, um ciclo e um caminho com (v0, a1, v1, a2, . . . , ak, vk) comk 1ondevk = v0masv0, v1, v2, . . . , vk1sao distintos dois a dois.Chamamosdequadrado, aumciclodecomprimentoquatrocomverticesdiferentes.Chamamos de triangulo, a um ciclo de comprimento tres .x yw zyx

zQQQQQQQQQQQQQfigura 102.2 MatrizdeAdjacenciaNa computacao, um grafo nito direcionado ou nao-direcionado (digamos, nvertices) e geralmente representado por sua matriz de adjacencia: uma matrizde ordemn n cujo valor na linhai e colunajfornece o n umero de arestas doi -esimo ao j -esimo vertices.Umamatrizdeadjacencias eumadasformasdeserepresentarumgrafo.DadoumgrafoGcomnvertices,digamosv1, v2, . . . , vnpodemosrepresentaro grafo por uma matrizMnn, da seguinte forma a entradamije o n umero dearestas que ligam o vertice i ao vertice j.CAPITULO2. GRAFOSECAMINHOS 18Em grafos nao direcionados, as matrizes de adjacencia sao simetricas, isto e,mij = mji. Para todoi = j. Matrizes de adjacencia de grafos direcionados, noentanto, nao sao assim.Exemplo 5. Seja o grafoG(V, A) com vertices emV= {1, 2, 3, 4, 5} e arestasemA = {(1, 2), (1, 3), (1, 5), (2, 4), (3, 4)}.A qual podemos representar gracamente assim:5 1IIIIIIIIIIIIII2||||||||4 3gura 6A matriz de adjacencia associado a este graco e:A =__0 1 1 0 11 0 0 1 01 0 0 1 00 1 1 0 01 0 0 0 0__2.3 N umerodeCaminhosPossveisNamatrizdoexemploanterior, vamos encontrar on umerodecaminhospossveis para ir do vertice i ao vertice j com comprimento 2.Denotemos pora2ija entradaijda matrizA2A2=__3 0 0 2 00 2 2 0 10 2 2 0 12 0 0 2 00 1 1 0 1__a2ijeon umerodecaminhospossveisparairdoverticei aoverticej comcomprimento2. Porexemplo, aentradaa223= 2, esten umerorepresentaquetemos2caminhosdistintosparirdovertice2aovertice3comcomprimento2asaber(2, 4, 3)(2, 1, 3). Analiticamentebastanotarquea223=a21.a13 +a22.a23 + . . . + a25a53que podemos representar no diagrama abaixo.CAPITULO2. GRAFOSECAMINHOS 191223345aaaaaaaaaa21222324251323433353Notequecadasegmentoa2iai3e0ou1, poisoutemosumcaminhodovertice 2 ao vertice 3 passando por i neste casoa2i= 1 eai3= 1 ou nenhumisto ea2iouai3 = 0.O seguinte teorema generaliza este exemplo.Teorema 2.1.:Seja Anxn = (aij) matriz de adjacencia ao grafo de n- vertices.Se Am= (amij), entao a i-j-esima entrada da matriz Am, amije o n umero de cam-inhos possveis para ir do verticei ao verticejcom caminhos de comprimentom.Prova(Inducao)Paran = 1, A1= por denicao a 1Suponhamos que vale paran = k, isto e, seAk = (akij)nn eakije o n umerode caminhos de comprimento k para ir de i ao vertice j, Paran = k + 1 temos:Ak+1=Ak.A=(Ak+1ij)nn. Vamosmostrarpeloprocessocombinatoriooscaminhos de comprimentok + 1.HipotesedeInducaoVale paran = k, isto e, seAk = ((Ak)ij)nxn(Ak)ijeon umerodecaminhosdecomprimentokparairdoverticei aovertice j.Paran = k + 1 temosAk+1= Ak.A = ((Ak+1)ij)nxnVamos mostrar peloprocessocombinatorioos caminhos decomprimentok + 1xado ij, (ak+1ij) = (aki1).a1j + (aki2).a2j + . . . + (akin).anj, que podemos rep-resentar no diagrama abaixo.Como(akil)pelahipotesedeinducaoeon umerodecaminhosparairdovertice i ao vertice l, entao se (alj) e zero, nao teremos nenhum caminho parair de i a j passando pelo vertice l no pen ultimo vertice.CAPITULO2. GRAFOSECAMINHOS 2012i jnn-1aaa aa aaai1i2i(n-1)in1j2j(n-1)jnj()()() ()() ()()()kkk kk kkkSealj= 1, entao o n umero de caminhos para ir de i a j passando por l nopen ultimovertice e(akil).(alj). Assimvariandolde1atentemosque(ak+1ij)CAPITULO2. GRAFOSECAMINHOS 21Exemplo6. Calcularquantoscaminhosdecomprimento100vaodovertice1ao vertice 6 no grafo do acima (octaedro).Considere o grafo dado pelos vertices do octaedro12 3456A matriz de adjacencia associada a esse grafo eA =__0 1 1 1 1 01 0 1 0 1 11 1 0 1 0 11 0 1 0 1 11 1 0 1 0 10 1 1 1 1 0__Para encontrar o polinomio caracterstico vamos calcular o determinante dedet(AI) =__ 1 1 1 1 01 1 0 1 11 1 1 0 11 0 1 1 11 1 0 1 10 1 1 1 1 __Usando o Maple obtemos o polinomioP(x) = x612x416x3Exemplo7. Calcularquantoscaminhosdecomprimento1000vaodovertice1 ao vertice 6 no grafo do acima (octaedro).Do teorema (2.1) basta calcular A1000, e ver a entrada (1, 6) (a100016) de A1000A = PDP1em que1 = 0, 2 = 2 e3 = 4 sao auto valores.A10005x5= PD1000P1os autovalores sao 1 = 0, 2 = (2)1000e 3 = 41000CAPITULO2. GRAFOSECAMINHOS 22f(x) = x1000f(A) = A1000Vamos propor outro polinomiop(x) = (41000+ 2.2100024)x2+ (410004.2100012)x.este polinomio e obtido por interpolacao, veja Apendice 1.p(0) = f(0) = 0p(2) = f(2) = (2)1000p(4) = f(4) = 41000p(x) = (41000+2.2100024)x2+ (410004.2100012)xp(0) = 0p(2) = (2)1000p(4) = 41000Assim do lema (1) temos quef(A) = P(A) = 0A1000= a(41000+2.2100024)A2+ b(410004.2100012)A23Captulo3TeoremadaAmizadeEm uma festa imagine que todo mundo se conhece. Mas digamos que forampessoas sorteadas ao acaso e que, portanto, podem ou nao se conhecer. O quepodemosdizersobreomodocomoessaspessoasseagrupam? Ouseja, seraquepodemosdizerquenecessariamentehaumgrupodequatropessoasqueconhecemumas`asoutras? Ouexisteumgrupodequatrodelasquenaoseconhecem?Quatro ou tres?Quantas?Se duas pessoas sao amigas, isso quer dizer que elas se conhecem. Muito bem.O que vamos mostrar e que, em qualquer grupo de pessoas, sempre existem tresdelas que: se conhecem mutuamente ou nao se conhecem mutuamente.Talvez seja difcil ver a complexidade do que queremos demonstrar. Faca oseguinte, entao. Acompanhe a demonstracao desse teoremaTeorema 3.1.Uma festa com n pessoas onde cada duas pessoas tem exatamenteum amigo comum. Entao alguem da festa conhece todas as pessoas.Notemos que o problema e trivial se na festa fzem parte apenas tres pessoas,nesta situacao cada uma das tres pessoas conhecem as outras, o grafo associadoe um triangulo.Assim, resta resolver os casos que temos mais de tres pessoas.Amatrizdeadjacenciadoproblemadaamizadesatisfazasseguintespro-priedade:- A matriz e simetrica. - Todas as entradas de 0

s ou 1

s -Diagonal principale toda de zeros.- Os 1

s na linhai e o grau do verticei ou n umero de amigos dei.Teorema3.2. (versao grafos)SeG(V, A) eumgrafocomn umeron =V 4,tal queacada2verticesdistintosxeyhaexatamenteum unicoverticeztal quex zey z=existe um unico vertice u tal quex u x G\{u}Teorema3.3. (versao matricial)CAPITULO3. TEOREMADAAMIZADE 24xvvvvvvvv1234567nSeA = (aij)nxneumamatrizsimetricadeordemn 4,cujasentradassao0

sel

s,comdiagonal dezeroseparatodoi, jcomi =jhaum unicoktal queaik=ajk= 1. Entaoexisteexatamenteuma unicalinhacheiade1

sexceto a diagonal.A =__0...01 1 1 0 1 1...0__O seguinte lema sera necessario para mostrar o teorema da amizade.Lema3.1. :Sed Z, comd > 2, entaodd1nao ZProva:1)Se(d 1)nao equadradoperfeito=d 1 eirracional=dd1eirracional (nao e inteiro).2)Se(d 1) equadradoperfeito=(d 1 Z). m.d.c(d, d 1) = 1(d 1)e(_(d 1))temosmesmosfatoresprimos=m.d.c(d,d 1) = 1dd1 Q\ZLogodd1nao pertence a ZSejaG(V, A)umgrafocomascondicoesdoTeorema(verversaografos).Assim temos os seguintes lemas.Lema3.2. : G nao tem quadrados;Prova: Suponhamos por absurdoque x, y, v, wsaoos vertices de umquadrado (um ciclo de comprimento quatro)x yw vCAPITULO3. TEOREMADAAMIZADE 25figura 12os vertices y e w possuem vertices x e v simultaneamente adjacentes ao par ywisto contradiz a propriedade de G. Logo o lema esta demonstrado.Lema3.3. : Cada aresta pertence exatamente a um triangulo.Prova: Peloabsurdo, suponhamosqueaarestadeverticesyewpertenceaos triangulos x, y, w e v, y, wx yw {{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{vfigura 12= x, y, v, w e quadrado, isto e um absurdo, pois contradiz o lema 3.2.Lema3.4. : Todo vertice tem grau par e maior ou igual a 2Prova: Fixamosu V , sex V \u, para o par ux existe y o unico verticetal queu y ex y Do lema 3.3 a aresta uy pertence a um unico triangulo.x xu yuwy(a) (b)Figura 3.1:Logo o grau(u) 2Se nenhum outro vertice sai de u, acabou, o grau e 2.Se temos que uz e uma aresta novamente pelo lema 3.3, ha um unico triangulou = p ondep = yep = w pois nao existe quadrado gura (b), logo temos doistriangulos uyw e uzp, que geram pelo menos 4 arestas saindo de u. Pelo anteriora cada aresta nova saindo de u temos um triangulo cujas arestas sao disjuntas dasarestas dos triangulos anteriores, como o n umero de vertice e nito, so podemoster um n umero par de arestas saindo de u. Sendo u um vertice arbitrario o lemaesta demonstrado.Lema3.5. : Existe um vertice de grau 4.CAPITULO3. TEOREMADAAMIZADE 26Prova: Fixemos umaarestadenotemos xy, dolema3.3existeum unicotriangulo xyz. Como V 4 seja w V \x, y, z. Para o par yw, existe um unicovertice p tal quey p ew p.Temos dois casos: Sep =x ou reciprocamentep =z= o vertice x teriagrau 3 ver gura (a), pelo lema 3.4 e par = grau(x) 4.Se p=xgura(b) =graudey 3logodolema3.4grau(y)4Denicao3.1. DistanciaEmumgrafoconexo, adistanciaentredoisverticeseocomprimentodocaminho mais curto.Lema3.6. : A distancia entre dois vertice quaisquer e 1 ou 2.Prova: Seja x, y e V oux y ouxy. Sex y a distancia e 1.E sexy existe z tal quex z ey z logo a distancia e 2.xy zQQQQQQQQQQQQQProposicao1. :O grafo G(V, A) do problema da amizade nao e regularProva: Pelo metodo de solucao ao absurdo, suponha que G e regular de grauddo lema 3.5 e 3.6 de par ed 4. Denotemos porn = V .Fixemosv V ,como o grau(v) =d, v1, v2, . . . , vdos vertices adjacentes, aarestav.v1temum unicotriangulo, cujooutroverticeealgumvicomi =j.Fazendo isso sucessivamente e re-enumerando temosd2triangulos com verticesem comum d gura (14).Do lema 3.6, todos os outros vertices exceto v, v1, v2, . . . , vd estao a distancia2 dev.Fixandov1 quantos vertices estao a distancia 2 de v, usando caminhos pas-sando porv1?Como o grau(v1) = d, e temos uma aresta que vai para v e outra que vai parav2(distancia devav2 e 1), entaov1contribui com (d 2) vertice a distancia2dev. Omesmoacontececomviparai=1, 2, 3, . . . , dlodon=verticesdedistancia zero de V + vertices distancia 1 de v + vertices de distancia 2 de v.n = 1 + d + d(d + 2) = d2d + 1A = (aij)nxn matriz simetrica de adjacencia ao grafo. Cada linha tem d1so resto das entradas e zero.CAPITULO3. TEOREMADAAMIZADE 27Armacao: o vetorW=__1111...1__e autovetor de A com autovalores d.A.W= A.__1111...1__=__dddd...d__= d__1111...1__= d.WComo, toda matriz simetrica e diagonalizavel, existe M matriz invertvel talqueMAM1=__10 . . . 00 2. . . 00 0...00 0 . . . n__(MAM1).(MAM1) = MA2M1=__210 . . . 00 22. . . 00 0...00 0 . . . 2n__Por outro lado, a matrizA2e da seguinte forma__d 1 . . . 11 d . . . 10 0...11 1 . . . d__Poiscada2verticesi =jexisteum unicocaminhodecomprimento2. Opolinomio caracterstico deA2e:Comon = d2d + 1 temosdet(A2xI) = (d 1 x)n1(d2x)logo (d 1) ed2sao autovalores deA2.O polinomio caracterstico da matrizA2e:p(x) = det(A2xId) = det_______d x 1 1 11 d x 1 11 1 d x 1...............1 1 1 d x_______CAPITULO3. TEOREMADAAMIZADE 28Do lema 1.2, cap 1, fazendot = d x temos que:p(x) = (d 1 x)n1(d +n 1 x) = (d 1 x)n1(d +(d2d +1) 1 x)P(x) = (d 1 x)(n1).(d2x)Entao os valores proprios deA2sao as razes deP(x) = 0, logo :21 = d2,22 = d 1,23 = d 1, ,2n = d 1.Como ja temos observado que d e valor proprio da matriz A, entao 1 = d osoutros valores proprios da matriz A sao i = d 1, digamos que p deles saoiguais a +d 1 e q deles sao iguais a d 1. Como a diagonal da matriz Ae composta de zeros, entao a traca da matriz e zero, isto e:0 = 1 + 2 + 3 + + n = d + (p q)d 1,obtendod = (q p)d 1, logodd 1= (q p).Esta ultima igualdade e um absurdo, pois comod 4, do lema 3.1,dd 1nao e inteiro, mais (qp) e inteiro. Logo temos mostrado que o grafo nao e regu-lar.3.1 DemonstracaodoteoremadaamizadeSejaG(V, A)umgrafosatisfazendoashipotesesdoteoremadaamizade,daproposicaoanteriortemosquenemtodososverticestemomesmograu.O primeiro passo da demonstracao e vericar que o vertice de grau maximo eadjacente a todos os outros vertices, o que mostra a existencia.A.Seueumverticedegraumaximoexeumverticequenaotemdegraumaximo, entaox e adjacente au (x u).Comefeito, peloabsurdo, suponhaquexnaoeadjacenteau. Sejau1o unicoverticequeeadjacenteaoparuex, edenotemosporu2, u3, , ud;onded 4 e grau maximo e sabemos que e par. Por outro lado denotemos porx1, x2, , xkosverticesadjacentesax eclaroquek d 2(ktambem epar). Como nao existe quadrados no grafo temos que{u1, u2, , ud} {x1, x2, , xk} = {u1 = x1}CAPITULO3. TEOREMADAAMIZADE 29uuuuuuxxxxxu=x12345d 1234kNotemos que x nao e adjacente a nenhum dos u2, u3, , ud, porque formariaum quadrado. Para cadauicomi = 2, 3, , d o vertice adjacente a x euieum dosxj. comok d 2, entao temos que existeui,ujdiferentes de modoque o mesmoxl e adjacente comum para os paresx,uiex,uj. logou,ui,xl,ujseria um quadrado o que e um absurdo e prova A.Para terminar mostraremos que ha so um unico vertice de grau maximo, oque mostra por completo o teorema da amizade.B. Existe um unico vertice de grau maximo.Comefeito, por ser umn umeronitodevertices entaoograudecadavertice e nito, como o grafo nao e regular, ha pelo menos um de grau maximo,mostraremosquenao podeexistirmaisdeumdegraumaximo. Suponhamosquex1ex2s aodoisverticesdistintoscomgraumaximo, paracadaumde-lesosoutrosverticesdegraumenor(digamos, u1, , uk)saoadjacentesaamboslogox1, u1, x2, u2seriaumquadradooque eumabsurdoeprovaB.30Apendice.1 InterpolacaoPolinomialAinterpolacaopolinomial consisteemdeterminarumafuncaopolinomialcujo graco contem um certo n umero de pontos xados apriori.A interpolacao polinomial pode-se revelar desadequada se os pontos de inter-polacao nao forem escolhidos convenientemente. De um modo geral, o conjuntodas funcoes interpoladoras e determinado por um n umero nito de parametrosquedeveraserigual aon umerodecondicoesimpostas, paraquehajaapenasuma solucao. Nos casos que veremos, a determinacao dos parametros, que de-nem a funcao interpoladora, ira levar-nos `a resolucao de um sistema linear.Suponha que (n+1) pontos sejam dados:(x0, f0), (x1, f1), . . . (xn, fn) ondex0, x1. . . xnsao distintos. O polinomio de grau nque passa por (n+1) pontospode ser escrito assim:g(x) = a0 a1x + a2x2+ ... + anxnondeaisao coecientes indeterminados. O ajustamento do polinomio para os(n + 1) pontos gera o sistema de equacoes linearesf0 = a0 + a1x0 + a2x20 + ... + anxn0f1 = a0 + a1x1 + a2x21 + ... + anxn1...fn = a0 + a1xn + a2x2n + ... + anxnnEmbora os coecientes, ai possam ser determinados pela solucao do sistemadeequacoeslinearesusandoumprogramadecomputador,taltentativanao edesejavel por duas razoes. Primeira, seria necessario um programa para resolverum conjunto de equacoes lineares, e, segunda, a solucao por computador podenao ser exata.Felizmente existem muitos metodos para determinar a interpolacao polino-mial sem resolver o sistema de equacoes lineares. Um destes metodos e a formulaCAPITULO3. TEOREMADAAMIZADE 31deinterpolacao,usandoasformulasdeLagrangeoudeNewton,quereduzemsignicativamente o n umero de operacoes envolvidas.O polinomio de grau nque passa por (n + 1) pontos e unico. Isso signica,sem considerar a formula de interpolacao, que todas as interpolacoes ajustadaspara os mesmos pontos sao matematicamente identicos..2 FormuladaInterpolacaodeLagrangeDados os (n + 1) pontos no plano (x0, f0), . . . , (xn, fn), comx0, x1, . . . , xn,distintos. Pelo metodo de Interpolacao de Lagrange, vamos encontrar umpolinomio de grau ncujo graco passa pelos pontos dados.Primeiramente considere o produto de fatores:L0(x) = (x x1)(x x2)...(x xn)A funcao L0 e um polinomio de grau n em x, notemos que dividindo L0(x)porL0(x0), obtemos a funcao polinomial de grau n:L0(x) =L0(x)L0(x0)=(x x1)(x x2)...(x xn)(x0 x1)(x0 x2)...(x0 xn)Notemos queL0(x0) = 1 eL0(x1) = . . . = L0(xn) = 0.De modo similar consideremos parai = 1, 2, . . . , n.Li(x) =Li(x)Li(xi)=(x x1)(x x2) . . . (x xi1)(x xi+1) . . . (x xn)(xi x0)(xi x1) . . . (xi xn)Logo a funcaoLi(x) e um polinomio de grau ne satisfaz queLi(xi) = 1 eLi(x1) = . . . = Li(x)i1 = Li(xi+1) = . . . = Li(xn) = 0).Assim multiplicando os polinomiosL0(x), L1(x), ..., Ln(x) porf0, f1, ..., fn,respectivamente, e adicionando-os, a soma e um polinomio de grau n, denotadopor g:g(x) = L0(x).f0 + L0(x).f1 + . . . + Ln(x).fng(x) =(xx1)(xx2)...(xxn)(xix0)(xix1)...(xixn)f0 +(xx1)(xx2)...(xxn)(x1x0)(x1x1)...(xxn)f1 + . . . ++(x x0)(x x1)...(x xn1)(xn x0)(xn x1)...(xn xn1)fnAssim temosg(xi) = fipara todoi = 0, 1, . . . , n.O polinomio ge chamado de PolinomiodeLagrange.A seguinte interpolacao sera usada no captulo 2.CAPITULO3. TEOREMADAAMIZADE 32Exemplo8. :Considere os 3 pontos (0, 0), (2, (2)1000), (4, 41000) e encontreo Polinomio de Lagrange de grau 2 associado a estes tres pontos.Solucao: Notemosquex0=0, x1= 2ex2=4ef(x0)=0, f(x1)=(2)1000,f(x2) = 41000, entaop(0) = 0,p(2) = (2)1000,p(4) = 41000.Como queremos interpolar 3 pontos o polinomio de Lagrange sera de grau2.p(x) = (2)1000L1(x) + 4100L2(x)p(x) = 0.L0(x) + (2)1000((xx0)(xx1)(x1x0)(x1x2) + 41000((xx0)(xx1)(x2x0)(x2x1)p(x) = (2)1000[x(x4)(2)(6) + 41000[x(x+2)4(6)]Fazendo (2)1000= me 41000=n entao teremosp(x) =mx2124mx12+nx224+2nx24p(x) = (m12 +n24)x2+(2n24 4m12 )xE agora chamamosa =2m+n24eb =2n24 4m12substituindo em a e b os valoresde m e n camos coma =2.21000+4100024eb =2.41000244.(2)1000120 -2 4Logo:p(x) = (41000+ 2.2100024)x2+ (410004.2100012)x.33References[SW]Seinbruch, Alfredo, Winterle, Paulo.`AlgebraLinear. PearsonEduca-tion, (1987).1J. PlnioOSantos, MargaridaP. Mello Idani C. Murari. Int.AAnaliseCombinatoria. Ed. Unicamp (1995).2Judith L. Gersting Fundamentos Matematicos para a Ciencia da Computacao.LTC Editora (2001).3GarrettBirkho, SaundersMaclaneAlgebraModernaBasica. Ed. Guan-abara Dois (1980).4TOMEI, Carlos. Autovalores e autovetores - alem de n = 2. Departamentode Matematica, PUC - Rio. Disponvel em tomei@mat.puc-rio.br. Acessoem 28 jan. 2007.5BRUNAT, J.;Uma demostracio del Teorema de lamistat per metdes elemen-tals. Butll, SCM. 7 (1992) p.75-80.6SANTOS, Reginaldo J.;Introducao `aAlgebra Linear Ed. Universitaria (2007)