4 1 - Tipos de grafo

Prévia do material em texto

<p>Tipos de grafo</p><p>Apresentação</p><p>Grafos estão presentes nas vidas das pessoas muito mais do que se pode imaginar. Quando alguém</p><p>acessa as redes sociais, como, por exemplo, o Facebook, ou quando compra algum produto na</p><p>Black Friday, ou ainda quando pesquisa a melhor rota para chegar em um local, está fazendo uso da</p><p>teoria dos grafos. Os sistemas de recomendações, aqueles que, quando alguém compra algo, eles</p><p>passam a oferecer produtos, utilizam modelagem a partir dos grafos para interpretar o</p><p>relacionamento dessa pessoa com os produtos que ela compra.</p><p>Por meio dos grafos, o entendimento do problema e a modelagem de sua solução ficam mais</p><p>perceptíveis, visto que, graficamente, se está visualizando o que está acontecendo. De igual modo,</p><p>as matrizes de adjacência, geradas a partir de grafos, são de extrema importância, pois recuperam</p><p>rapidamente uma série de informações dadas pelos grafos e são o elo mais próximo com os</p><p>sistemas computacionais.</p><p>Nesta Unidade de Aprendizagem, você irá aprender quais são os tipos mais conhecidos de grafos,</p><p>além de ilustrar como são suas representações geométricas. Por fim, entenderá quais são as</p><p>diferenças entre eles.</p><p>Bons estudos.</p><p>Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:</p><p>Descrever os principais tipos de grafos.•</p><p>Ilustrar as representações geométricas dos grafos.•</p><p>Apontar as diferenças entre os grafos usando exemplos práticos.•</p><p>Desafio</p><p>A teoria dos grafos é um importante instrumento da matemática para modelar e achar o caminho</p><p>para a solução de um problema. Em tempos de redes sociais, com pedidos de produtos via internet</p><p>e melhores trajetos para um destino, cada vez mais torna-se fundamental o trabalho com os grafos,</p><p>pois, com base em representações de vértices e arestas, é possível esquematizar uma situação de</p><p>forma simples e rápida.</p><p>A partir do exposto, represente todos os voos possíveis por meio de um grafo e, em seguida, crie a</p><p>matriz de adjacência.</p><p>Infográfico</p><p>Problemas são constantes na vida dos profissionais. O que difere um profissional de outro é o</p><p>modo como lida com as informações e chega às soluções. A proposta da utilização de grafos é de</p><p>esquematizar o problema na forma de elementos (vértices) e as relações entre eles (arestas) e, com</p><p>isso, entender plenamente sobre o que deverá ser feito, e, com o suporte visual do esquema</p><p>desenhado, fica mais fácil a criação de uma solução.</p><p>Veja nesta animação um exemplo de aplicação dos grafos para a representação de mapas. Isso</p><p>pode facilitar a solução de algumas perguntas, como: quantos caminhos existem para ir de uma</p><p>cidade X até a cidade Y? Qual é o menor ou melhor caminho entre X e Y? Existe um outro caminho</p><p>para ir de uma cidade a outra?</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>Em seguida, confira o Infográfico, que apresenta os conceitos que fundamentam os grafos e os seus</p><p>tipos.</p><p>https://grupoa-edtech.grupoa.education/object/eKsFWnogSqSz4Pf_gnTO9A</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/cf5ac1f9-31d9-4368-ae7c-68ff52b73910/15de45ee-1235-4673-9f67-cc0cf696d61a.jpg</p><p>Conteúdo do livro</p><p>Quando alguém se depara com problemas do dia a dia, é possível que tenha certa dificuldade em</p><p>propor soluções a partir de um primeiro olhar para a situação. Contudo, ao transportar o problema</p><p>para uma análise por meio de grafos, as possibilidades de soluções ficam mais evidentes. Isto</p><p>significa que os grafos ilustram todas as conexões que um problema tem, permitindo uma visão</p><p>ampliada sobre o cenário.</p><p>No capítulo Tipos de grafo, base teórica desta Unidade de Aprendizagem, você vai conhecer quais</p><p>são os principais tipos de grafo, terá uma visão geral sobre como são representados graficamente e</p><p>entenderá suas principais diferenças.</p><p>Boa leitura.</p><p>TEORIA DOS</p><p>GRAFOS E ANÁLISE</p><p>DE ALGORITMOS</p><p>OBJETIVOS DE APRENDIZAGEM</p><p>> Descrever os principais tipos de grafos.</p><p>> Ilustrar as representações geométricas dos grafos.</p><p>> Apontar as diferenças entre os grafos usando exemplos práticos.</p><p>Introdução</p><p>O estudo dos grafos é uma vertente da matemática que analisa e avalia as carac-</p><p>terísticas dos grafos, que são estruturas formadas por um conjunto de vértices</p><p>(pontos ou elementos) não vazios e por um conjunto de arestas (retas ou linhas)</p><p>que fazem alusão a uma relação binária. Ou seja, com os grafos conseguimos</p><p>representar elementos e suas possíveis relações.</p><p>Essa teoria surgiu no ano 1736, quando o matemático suíço Leonhard Euler</p><p>(1707–1783) propôs a solução para o problema das sete pontes que havia na cidade</p><p>de Königsberg e estavam ligadas a duas ilhas. O problema consistia em transpor</p><p>todas as sete pontes sem passar pela mesma ponte mais de uma vez. Euler, por</p><p>meio de grafos, conseguiu comprovar a impossibilidade de se realizar tal feito</p><p>(SAUTOY, 2018).</p><p>Desse modo, podemos afirmar que os grafos são representações muito im-</p><p>portantes que evidenciam as possíveis relações entre objetos que pertencem a</p><p>um determinado conjunto. Estudá-los é de fundamental importância dentro da</p><p>matemática, pois por meio deles conseguimos evidenciar conexões com o mundo</p><p>real de maneira eficaz. Assim, ao ser representado como um grafo, um problema</p><p>do mundo real pode ser estudado em profundidade, tendo suas múltiplas possi-</p><p>bilidades de soluções analisadas.</p><p>Tipos de grafo</p><p>Wheslley Rimar Bezerra</p><p>Neste capítulo, você vai estudar quais são os principais tipos de grafos e</p><p>suas características. Além disso, aprenderá a identificá-los considerando suas</p><p>representações geométricas. Por fim, observará suas diferenças por meio de</p><p>exemplos práticos.</p><p>Principais tipos de grafos</p><p>Muitas estruturas podem ser representadas em forma de grafos, ampliando</p><p>a dimensão de entendimento de uma situação ou problema em que estão</p><p>inseridas. Como exemplos dessas estruturas, podemos destacar:</p><p>� relações de parentesco entre grupos de pessoas;</p><p>� circuitos elétricos;</p><p>� redes de computadores (físicas ou lógicas);</p><p>� relações entre ruas de uma cidade ou estradas que ligam diferentes</p><p>cidades;</p><p>� rotas de aviões ou navios;</p><p>� redes de distribuição;</p><p>� vínculo entre páginas (telas) de um website ou sistema computacional;</p><p>� atores que trabalharam em um mesmo filme;</p><p>� alocação de professores em disciplinas de uma escola.</p><p>Considerando as partes de um grafo (vértices e arestas), vejamos no Quadro 1</p><p>uma representação mais detalhada de como é sua estrutura.</p><p>Quadro 1. Modelos usando grafos</p><p>Grafo Vértice Aresta</p><p>Comunicação Computadores,</p><p>satélites, centrais de</p><p>telefonia</p><p>Cabos de rede, fibra</p><p>óptica, ondas de rádio</p><p>Circuitos elétricos Portas lógicas,</p><p>registradores,</p><p>processadores</p><p>Filamentos</p><p>Sistema hidráulico Reservatórios de</p><p>água, estações de</p><p>bombeamento</p><p>Tubulações</p><p>(Continua)</p><p>Tipos de grafo2</p><p>Grafo Vértice Aresta</p><p>Sistema financeiro Ações, moeda Transações</p><p>Sistema de transporte Cidades, aeroportos,</p><p>rodoviárias</p><p>Estradas, ruas,</p><p>rodovias, vias aéreas</p><p>Internet Páginas web Hiperlinks</p><p>Relações sociais Pessoas, atores Amizades, trabalho</p><p>conjunto em filmes</p><p>Agora que conhecemos alguns dos possíveis contextos de uso dos grafos,</p><p>é preciso compreender seus diferentes tipos. Dentre os muitos exemplos,</p><p>podemos citar: grafo simples, bipartido, regular, vazio, trivial, direcionado</p><p>(dígrafo) e multigrafo (não) direcionado. Porém, antes de examinar cada um</p><p>deles, vamos definir formalmente o que é um grafo. Segundo Dasgupta,</p><p>Papadimitriou e Vazirani (2009), podemos entender um grafo como sendo um</p><p>modelo ou estrutura matemática que representa as relações entre objetos.</p><p>Assim, um grafo G = (V, E) consiste em um conjunto de vértices (também cha-</p><p>mados de nós) V que são conectados por um conjunto de arestas ou arcos,</p><p>representados por E. A seguir, vamos conhecer suas definições e visualizar</p><p>exemplos de como podem ser representados.</p><p>Simples</p><p>Este tipo de grafo é reconhecido por não ter laços (pontas</p><p>inicial e final do</p><p>arco coincidentes), nem mais de uma aresta conectando dois vértices (arestas</p><p>múltiplas). Em outras palavras, diz-se que um grafo é simples quando seus</p><p>vértices são isolados, ou seja, não são adjacentes com outros vértices. Além</p><p>disso, um grafo simples não é direcionado e suas arestas não são paralelas.</p><p>Observe a seguir um exemplo de sua representação:</p><p>V = {P1, P2, P3}</p><p>E = {{P1, P2}}</p><p>Essa representação indica um conjunto de vértices e elos em que</p><p>onde P1, P2 e P3 são os vértices, mas somente P1 e P2 estão conectados.</p><p>Como não há uma relação com o vértice P3, ele não aparece no conjunto</p><p>de elos.</p><p>(Continuação)</p><p>Tipos de grafo 3</p><p>Regular</p><p>Este tipo de grafo é elaborado de tal modo que cada vértice passa a ter o</p><p>mesmo número de adjacências. Além disso, cada vértice passa a ter o mesmo</p><p>grau (mesmo número de ligações), também chamado de valência. Nesse</p><p>contexto, grau refere à quantidade de arestas que se conectam a um vértice</p><p>(CONCEITOS..., [2010?]).</p><p>Vazio</p><p>Também conhecido como grafo nulo, é reconhecido por não ter arestas</p><p>em sua composição, possuindo apenas vértices. Veja sua representação</p><p>matemática:</p><p>V = {A, B, C, D}</p><p>E = { }</p><p>Esta definição indica que há quatro vértices, mas que não possuem</p><p>arestas.</p><p>Trivial</p><p>Este tipo de grafo é reconhecido por possuir um único vértice e não ter ares-</p><p>tas em sua estrutura (LIPSCHUTZ; LIPSON, 2013). Logo, podemos facilmente</p><p>representá-lo da seguinte maneira:</p><p>V = {1}</p><p>E = ∅</p><p>|V| = 1 e |E| = 0</p><p>Esta definição indica que há um vértice e zero arestas.</p><p>Direcionado (digrafo)</p><p>Este grafo é reconhecido por ter um sentido, ou seja, uma direção. Logo, se</p><p>temos as arestas Vi e Vj, uma é conectada a outra por meio de uma linha, com</p><p>uma seta saindo de Vi e apontando para Vj.</p><p>Tipos de grafo4</p><p>Multigrafo não direcionado</p><p>Lipschutz e Lipson (2013) afirmam que um multigrafo possui arestas múltiplas,</p><p>ou seja, que conectam os mesmos extremos. Um grafo G = (V, A) é definido como</p><p>um multigrafo quando em sua estrutura há duas ou mais arestas entre pares</p><p>de vértices de G. Assim, este grafo é reconhecido por conter arestas paralelas.</p><p>Bipartido</p><p>Segundo Fonseca (2016), este tipo de grafo é reconhecido por permitir que</p><p>seu conjunto de vértices, representado por V, seja particionado em dois sub-</p><p>grafos (V1 e V2), de modo que todo arco (aresta) do grafo conecta o vértice do</p><p>primeiro grafo ao vértice do segundo grafo. Veja a representação matemática:</p><p>V = V1 V2 tais que V1 ∩ V2 = ∅</p><p>Esta definição indica que V1 e V2 são dois grafos subconjuntos de V e a</p><p>intersecção de ambos é igual a vazio.</p><p>Ciclo euleriano (trilha euleriana fechada)</p><p>De acordo com Vulcani (2015), um grafo é dito como euleriano se houver um</p><p>ciclo em G que englobe todas as arestas de G. Do mesmo modo, uma trilha</p><p>euleriana fechada é um caminho em que se passa uma única vez por cada</p><p>elo (aresta) do grafo, conforme podemos visualizar no exemplo da Figura 1.</p><p>Figura 1. Grafo euleriano.</p><p>Fonte: Vulcani (2015, documento on-line).</p><p>Além disso, Vulcani (2015) afirma que, para um grafo ser considerado</p><p>euleriano, todos os vértices que o compõem devem ser de grau par.</p><p>Tipos de grafo 5</p><p>Ciclo hamiltoniano</p><p>No documento de Teoria de Grafos (TEORIA..., [201-?]b) afirma-se que um ciclo</p><p>hamiltoniano, por sua vez, refere-se aos grafos que possuem um ciclo em</p><p>que todos os seus vértices estão inclusos, repetindo-se apenas o primeiro</p><p>vértice de onde se iniciou o ciclo. Na Figura 2, a seguir, temos um exemplo</p><p>de grafo hamiltoniano.</p><p>Figura 2. Grafo hamiltoniano.</p><p>Fonte: Teoria... ([201-?]b, documento on-line).</p><p>Isomorfismo</p><p>São considerados isomorfos os grafos que contêm o mesmo número de</p><p>vértices e o mesmo número de arestas (elos). Além disso, o vértice do</p><p>primeiro grafo deve estar na mesma posição que o vértice do segundo</p><p>grafo, ou seja, devem ser correspondentes, conforme evidenciado no</p><p>exemplo da Figura 3.</p><p>Figura 3. Grafos isomorfos.</p><p>Fonte: Adaptada de Jurkiewicz (2009).</p><p>Tipos de grafo6</p><p>No exemplo apresentado na Figura 4, temos um grafo que exibe</p><p>múltiplas conexões entre dispositivos roteadores da internet. Esse</p><p>grafo faz parte de um projeto idealizado por Bill Cheswick e Hal Burch no ano de</p><p>1998, intitulado Internet Mapping Project (Projeto de Mapeamento da Internet).</p><p>Figura 4. Grafo de conectividade entre roteadores de internet.</p><p>Fonte: Cheswick ([201- ?], documento on-line).</p><p>Representações geométricas dos grafos</p><p>A partir deste ponto, vamos observar como são as representações gráficas</p><p>de alguns grafos estudados neste capítulo. Vale ressaltar, contudo, que nem</p><p>todos os grafos aqui mostrados exibem problemas reais, pois nosso foco é</p><p>apenas mostrar como são suas representações visuais.</p><p>Uma vez que um grafo é representado por um conjunto de vértices (V)</p><p>e por um conjunto de arestas ou elos (E), imagine um cenário de relações</p><p>sociais entre três pessoas: a primeira pessoa, denominada P1, conhece a</p><p>segunda pessoa, denominada P2. Contudo, ambas não conhecem a terceira</p><p>pessoa, denominada P3. Logo, temos um grafo simples, com as definições</p><p>ilustradas na Figura 5.</p><p>Tipos de grafo 7</p><p>Figura 5. Grafo simples de relação entre três pessoas.</p><p>Adiante, na Figura 6, temos outro exemplo de grafo simples, dessa vez</p><p>contendo cinco vértices e cinco arestas.</p><p>Figura 6. Exemplo de grafo simples com cinco vértices e cinco arestas.</p><p>Fonte: Teoria... ([201-?]a, documento on-line).</p><p>Já no exemplo apresentado na Figura 7, temos dois grafos regulares. Em</p><p>ambos, pode-se observar que todos os vértices estão conectados entre si e</p><p>possuem o mesmo grau, ou seja, cada vértice possui a mesma quantidade</p><p>de conexões.</p><p>Tipos de grafo8</p><p>Figura 7. Exemplo de grafos regulares.</p><p>Fonte: Rangel, Oliveira e Araujo (2018, documento on-line).</p><p>Por sua vez, no exemplo evidenciado pela Figura 8, temos um grafo vazio</p><p>(nulo) de quatro vértices (A, B, C e D), que não possuem conexões.</p><p>Figura 8. Exemplo de grafo vazio.</p><p>A seguir, representado pela Figura 9, temos um grafo trivial com o vértice 1.</p><p>Figura 9. Exemplo de grafo trivial.</p><p>Tipos de grafo 9</p><p>Na Figura 10, podemos observar um exemplo de um grafo direcionado</p><p>(digrafo), em que o vértice A é direcionado para os vértices B e C e o vértice</p><p>B é direcionado para C.</p><p>Figura 10. Exemplo de grafo direcionado (digrafo).</p><p>Na Figura 11, temos a representação visual de como podemos estruturar</p><p>um multigrafo de quatro vértices.</p><p>Figura 11. Exemplo de multigrafo.</p><p>Fonte: Lipschutz e Lipson (2013, p. 157).</p><p>Diferenças entre grafos, matriz de adjacência</p><p>e lista de adjacência</p><p>Apesar de muito eficazes visualmente, os grafos (representados por pontos</p><p>e linhas) não permitem ser manipulados por computador. Por este motivo,</p><p>utilizamos as matrizes de adjacências, que permitem essa interação. Assim, na</p><p>Tipos de grafo10</p><p>prática, uma matriz de adjacência é desenvolvida quando temos a necessidade</p><p>de representar um grafo em um modelo mais próximo do computacional.</p><p>Nela, todos os vértices de um grafo são adicionados nas linhas e colunas. Se</p><p>houver vínculo (aresta) entre os vértices, adiciona-se o valor 1 na matriz. Se</p><p>não houver, adiciona-se 0.</p><p>Como exemplo, considere a seguir o grafo da Figura 12.</p><p>Figura 12. Exemplo de grafo a ser traduzido em matriz de adjacência.</p><p>Dessa forma, temos:</p><p>� V1 se relacionando diretamente com V2, V5 e V6;</p><p>� V2 se relacionando diretamente com V1, V4 e V5;</p><p>� V3 se relacionando diretamente com V4;</p><p>� V4 se relacionando diretamente com V2, V3, V5 e V6;</p><p>� V5 se relacionando diretamente com V1, V2 e V4;</p><p>� V6 se relacionando diretamente com V1 e V4.</p><p>� Veja no Quadro 2, a seguir, a matriz de adjacência criada com base no</p><p>grafo anterior.</p><p>Tipos de grafo 11</p><p>Quadro 2. Matriz de adjacência</p><p>V1 V2 V3 V4 V5 V6</p><p>V1 0 1 0 0 1 1</p><p>V2 1 0 0 1 1 0</p><p>V3 0 0 0 1 0 0</p><p>V4 0 1 1 0 1 1</p><p>V5 1 1 0 1 0 0</p><p>V6 1 0 0 1 0 0</p><p>Além da matriz, temos a lista de adjacência, que, de maneira geral, é uma</p><p>lista que exibe as ligações de todos os vértices, conforme podemos observar</p><p>no exemplo a seguir (Figura 13), baseado em uma matriz de adjacência de</p><p>cinco vértices.</p><p>Figura 13. Matriz de adjacência e lista de adjacência.</p><p>Fonte: Nakamoto, Miyagi e Santos Filho (2015, documento on-line).</p><p>Se o grafo for direcionado, ou seja, se suas arestas possuírem sentido</p><p>de ligação, é considerado vizinho de um vértice apenas aquele que</p><p>tiver a aresta com sentido ao próximo vértice. Por exemplo: se o vértice V possuir</p><p>uma aresta direcionada para o vértice X e ao mesmo tempo houver uma aresta</p><p>oriunda do vértice U apontando para o vértice V, será considerado vizinho do</p><p>vértice V somente o vértice X.</p><p>Com base nos conteúdos aqui estudados, podemos perceber a importân-</p><p>cia que os grafos têm na representação de situações do mundo real. Essas</p><p>situações vão desde a programação de rotas de transportes aéreo, passando</p><p>Tipos de grafo12</p><p>pela alocação de professores em turmas de uma escola até a construção de</p><p>perfis de potenciais consumidores de um produto ou serviço, entre diversos</p><p>outros campos de aplicação.</p><p>Referências</p><p>CHESWICK, B. Internet mapping project: map gallery. [S. l.: s. n., 201-?] Disponível em:</p><p>http://cheswick.com/ches/map/gallery/index.html. Acesso em: 9 mar. 2021.</p><p>CONCEITOS básicos da teoria dos grafos. [S. l.: s. n., 2010?]. Disponível em: https://</p><p>www.inf.ufsc.br/grafos/definicoes/definicao.html. Acesso em: 9 mar. 2021.</p><p>DASGUPTA, S.; PAPADIMITRIOU, C.; VAZIRANI, U. Algoritmos. Porto Alegre: AMGH, 2009.</p><p>FONSECA, C. C. A teoria dos grafos como ferramenta na classificação de álgebras</p><p>de Leibniz. 2016. Dissertação (Mestrado em Matemática)- Universidade Federal de</p><p>Alagoas, Alagoas, 2016. Disponível em: http://www.repositorio.ufal.br/bitstream/</p><p>riufal/1339/1/A%20teoria%20dos%20grafos%20como%20ferramenta%20na%20</p><p>classifica%C3%A7%C3%A3o%20de%20%C3%A1lgebras%20de%20Leibniz.pdf. Acesso</p><p>em: 9 mar. 2021.</p><p>JURKIEWICZ, S. Grafos: uma introdução. São Paulo: OBMEP, 2009.</p><p>LIPSCHUTZ, S.; LIPSON, M. Matemática discreta. Porto Alegre: Bookman, 2013. (Coleção</p><p>Schaum).</p><p>NAKAMOTO, F. Y.; MIYAGI, P. E.; SANTOS FILHO, D. J. Um novo algoritmo para determinação dos</p><p>ciclos fechados de espera em grafo de alocação de recursos. [S. l.: s. n., 2015?]. Disponível</p><p>em: https://www.researchgate.net/profile/Francisco-Nakamoto/publication/268352773_</p><p>UM_NOVO_ALGORITMO_PARA_DETERMINACAO_DOS_CICLOS_FECHADOS_DE_ES-</p><p>PERA_EM_GRAFO_DE_ALOCACAO_DE_RECURSOS/links/559c7e4008aee2c16df1760c/</p><p>UM-NOVO-ALGORITMO-PARA-DETERMINACAO-DOS-CICLOS-FECHADOS-DE-ESPERA-EM-</p><p>-GRAFO-DE-ALOCACAO-DE-RECURSOS.pdf. Acesso em: 9 mar. 2021.</p><p>TEORIA dos grafos: conceitos básicos. [S. l.: s. n., 201-?]a. Disponível em: http://www.</p><p>gpec.ucdb.br/pistori/disciplinas/discreta/aulas/grafos.htm. Acesso em: 9 mar. 2021.</p><p>TEORIA dos grafos: grafos eulerianos e hamiltonianos. [S. l.: s. n., 201-?]b. Disponível</p><p>em: http://www.gpec.ucdb.br/pistori/disciplinas/discreta/aulas/geulham.htm. Acesso</p><p>em: 9 mar. 2021.</p><p>RANGEL, S.; OLIVEIRA, V. A. de; ARAUJO, S. A. Elementos de teoria dos grafos: notas de</p><p>aula. [São Paulo]: UNESP, 2018. Disponível em: https://www.ibilce.unesp.br/Home/De-</p><p>partamentos/MatematicaAplicada/docentes/socorro/grafos---notas-de-aula_set2018.</p><p>pdf. Acesso em: 9 mar. 2021.</p><p>SAUTOY, M. du. O enigma resolvido há 300 anos pelo matemático Leonhard Euler e</p><p>que hoje nos permite navegar na internet. In: TILT. [S. l.: s. n.], 2018. Disponível em:</p><p>https://www.uol.com.br/tilt/noticias/bbc/2018/05/20/o-enigma-resolvido-ha-300-</p><p>-anos-pelo-matematico-leonhard-euler-e-que-hoje-nos-permite-navegar-na-internet.</p><p>htm. Acesso em: 9 mar. 2021.</p><p>VULCANI, R. de L. M. et al. Grafos eulerianos e aplicações. 2015. Dissertação (mestrado</p><p>profissional) — Universidade Estadual de Campinas, Instituto de Matemática Esta-</p><p>tística e Computação Científica, Campinas, 2015. Disponível em: http://repositorio.</p><p>unicamp.br/bitstream/REPOSIP/306826/1/Vulcani_RenatadeLacerdaMartins_M.pdf.</p><p>Acesso em: 9 mar. 2021.</p><p>Tipos de grafo 13</p><p>Os links para sites da web fornecidos neste capítulo foram todos</p><p>testados, e seu funcionamento foi comprovado no momento da</p><p>publicação do material. No entanto, a rede é extremamente dinâmica; suas</p><p>páginas estão constantemente mudando de local e conteúdo. Assim, os editores</p><p>declaram não ter qualquer responsabilidade sobre qualidade, precisão ou</p><p>integralidade das informações referidas em tais links.</p><p>Tipos de grafo14</p><p>Dica do professor</p><p>Grafos são importantes na resolução de problemas e podem ser aplicados em, basicamente,</p><p>qualquer situação cotidiana, seja ela relacionada ao ambiente profissional ou pessoal. Entendendo</p><p>bem a teoria dos grafos, as possibilidades de soluções se ampliam e os benefícios para quem faz</p><p>uso dessa ferramenta ficam cada vez mais evidentes.</p><p>Pensando nisso, nesta Dica do Professor, você vai conhecer exemplos bem-sucedidos de áreas da</p><p>tecnologia em que os grafos são aplicados, gerando bons resultados.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/0d59fed9d7f634748dfd3e1aa524168d</p><p>Exercícios</p><p>1) Teoria dos grafos é um ramo da matemática que estuda as relações entre objetos de um conjunto.</p><p>Essas relações são formadas por vértices (que representam os elementos) e as arestas (os</p><p>relacionamentos entre os elementos).</p><p>Com base no grafo ilustrado, assinale a alternativa correta.</p><p>A) Vértices: 6</p><p>Arestas: 5</p><p>Grau do vértice 3: 4</p><p>B) Vértices: 7</p><p>Arestas: 8</p><p>Grau do vértice 3: 5</p><p>C) Vértices: 5</p><p>Arestas: 7</p><p>Grau do vértice 3: 4</p><p>D) Vértices: 6</p><p>Arestas: 5</p><p>Grau do vértice 3: 3</p><p>E) Vértices: 5</p><p>Arestas: 7</p><p>Grau do vértice 3: 3</p><p>2) Os grafos são representações de situações que foram pensadas para gerar soluções a respeito de</p><p>determinado problema. Uma das formas de representação de um grafo, para ser tratado na</p><p>programação de computadores, é a partir da sua matriz de adjacência.</p><p>Utilizando-se o grafo ilustrado, assinale o item que tem a matriz de adjacência correta.</p><p>A)</p><p>B)</p><p>C)</p><p>D)</p><p>E)</p><p>3) Uma lista de adjacência mostra, para cada vértice do grafo, uma relação de todos os outros vértices</p><p>com os quais ocorre o relacionamento.</p><p>A partir disso, escolha o grafo que representa a situação proposta pela lista de adjacência.</p><p>A)</p><p>B)</p><p>C)</p><p>D)</p><p>E)</p><p>4) Grafos isomorfos são aqueles que têm a mesma forma, mas este não é o único requisito para se</p><p>definir que é isomorfo. Deve-se fazer uma série de verificações e, de acordo com as respostas, é</p><p>possível ou não afirmar que o grafo é isomorfo, mesmo que o formato seja o mesmo.</p><p>Assinale a alternativa que exibe a resposta correta, ou seja, se os grafos G e H são isomorfos.</p><p>Considere Vg (número de vértices do grafo G), Vh (número de vértices do grafo H), Ag (número de</p><p>arestas do grafo G) e Ah (número de arestas do grafo H).</p><p>A) Não é isomorfo.</p><p>Vg =11, Ag =16</p><p>Vh =10, Ah = 15</p><p>f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 4, f(e) = 5, f(f) = 6, f(g) = 7, f(h) = 8, f(i) = 9, f(j) = 10</p><p>B) É isomorfo.</p><p>Vg = 10, Ag = 14</p><p>Vh = 10, Ah = 15</p><p>f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 4, f(e) = 5, f(f) = 6, f(g) = 7, f(h) = 8, f(i) = 9, f(j) = 10</p><p>C) É isomorfo.</p><p>Vg =10, Ag =10</p><p>Vh = 10, Ah = 10</p><p>f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 4, f(e) = 5, f(f) = 6, f(g) = 7, f(h) = 8, f(i) = 9, f(j) = 10</p><p>D) Não é isomorfo.</p><p>Vg = 11, Ag = 15</p><p>Vh = 10, Ah = 15</p><p>f(a) = 10, f(b) = 9, f(c) = 3, f(d) = 4, f(e) = 5, f(f) = 6, f(g) = 7, f(h) = 8, f(i) = 2, f(j) = 1</p><p>E) É isomorfo.</p><p>Vg = 10, Ag = 15</p><p>Vh = 10, Ah = 15</p><p>f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 4, f(e) = 5, f(f) = 6, f(g) = 7, f(h) = 8, f(i) = 9, f(j) = 10</p><p>A teoria dos grafos foi criada pelo matemático Leonhard Euler em 1736 para resolver o problema</p><p>das sete pontes da Cidade de Königsberg. Os habitantes daquela cidade perguntavam-se se era</p><p>possível cruzar as sete pontes em uma caminhada contínua sem passar duas vezes por qualquer</p><p>uma delas.</p><p>5)</p><p>Sobre a teoria dos grafos, relacione a letra do grafo (que contém o nome) com o número do grafo</p><p>(que contém a imagem) e escolha a resposta que tem o relacionamento correto.</p><p>A) 1c, 2d, 3b, 4e, 5a.</p><p>B) 1a, 2b, 3c, 4d, 5e.</p><p>C) 1e, 2d, 3b, 4a, 5c.</p><p>D) 1b, 2c, 3a, 4d, 5e.</p><p>E) 1e, 2b, 3d, 4a, 5c.</p><p>Na prática</p><p>Cada vez mais, as pessoas fazem uso de comércio via internet, porém, quando sua residência está</p><p>no interior, tudo o que diz respeito a frete fica mais complicado e mais caro. Caso o produto tenha</p><p>que ser trocado, os problemas aumentam ainda mais. Quando se trata de rotas, os grafos são</p><p>importantes instrumentos que podem evidenciar problemas de logística. Eles podem ajudar a</p><p>escolher o menor trajeto, o mais barato, o mais rápido. Existe uma série de análises que é possível</p><p>fazer com o auxílio dos grafos. Eles são de vários tipos e têm um papel fundamental para traçar</p><p>estratégias.</p><p>Veja, em Na Prática, a história de um grupo de amigas do interior de Boa Vista/RR, que, por meio</p><p>de um grafo, conseguiu entender o atraso na entrega de suas mercadorias.</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/f026d7b1-fa2d-4569-ae08-d5e156b3f5c6/9b591ae3-8147-46ad-bfaa-dee62f4ec066.jpg</p><p>Saiba +</p><p>Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor:</p><p>Análise da evasão de alunos da área de tecnologia da</p><p>informação por meio de um banco de dados orientado a grafos</p><p>Leia este artigo, que contém uma análise sobre a evasão de estudantes de um curso superior na</p><p>área de TI. O objetivo é ter o contato com um banco de dados orientados a grafos, utilizando-se a</p><p>linguagem Cypher em comparação à linguagem SQL.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>Grafos – Conceitos básicos</p><p>Assista a este vídeo, que contém uma explicação sobre os grafos, os principais tipos e aplicações, e</p><p>saiba como partir de um problema e criar um grafo para representá-lo.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>Verificação de vulnerabilidades em redes de transporte: uma</p><p>abordagem pela teoria dos grafos</p><p>Leia este artigo, que aborda a teoria dos grafos auxiliando no mapeamento de possíveis</p><p>vulnerabilidades no sistema de transportes com o objetivo de evitar futuras crises.</p><p>https://revistas.setrem.com.br/index.php/reabtic/article/view/278/126?v=1956145534</p><p>https://www.youtube.com/embed/MC0u4f334mI</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>http://www.anpet.org.br/anais/documentos/2019/Planejamento%20Territorial%20do%20Transporte/Resili%C3%AAncia%20em%20Transportes/4_517_AC.pdf?v=1706526805</p>