Grafolândia e Teoria dos Grafos - Detecção de Regiões Altamente Conectadas em C

Painel Meus cursos 2023Q3TG Entrega 3 22novembro Desvendando a Magia das Conexões na Grafolândia 2023 Q3 MCTA02717 Teoria dos Grafos Descrição Enviar Editar Visualizar envios Desvendando a Magia das Conexões na Grafolândia Data de entrega quinta 23 Nov 2023 0100 Número máximo de arquivos 1 Tipo de trabalho Trabalho individual À medida que Grafolândia emergiu dos sombrios tempos de guerra e as conexões mínimas entre os povoados voltaram a ser restabelecidas as estradas voltaram a ter suas propriedades mágicas os caminhos só permitem avançar mas nunca retroceder Agora mais do que nunca os habitantes anseiam por construir vários caminhos de deslocamento entre os povoados e certamente caminhos que os permitam voltar ao seu povoado de origem Como várias estradas já estão construídas é preciso primeiro detectar quais povoados já estão em regiões altamente conectadas isto é regiões em que quaisquer dois povoados têm uma estrada que os conectam em ambas as direções Sua missão agora é detectar onde no mapa atual essas regiões já existem Instruções Independente dos resultados dos testes o não cumprimento dos critérios abaixo implicará em nota zero para esta atividade Qualquer dúvida entre em contato Você deve resolver esse problema em linguagem C usando grafosdigrafos que devem ser representados por listas de adjacências Você deve incluir no início do seu programa uma breve cabeçalho contendo no mínimo o seu nome e RA Se você precisar implementar uma busca em largura você precisa implementar uma estrutura de dados Fila Se você precisar implementar o algoritmo de Kruskal você precisa implementar uma estrutura de dados UnionFind Use o algoritmo de ordenação disponível no material de aula Se você precisar implementar o algoritmo de Prim você precisa implementar uma estrutura de dados Heap Se você precisar implementar o algoritmo de Tarjan você precisa implementar uma estrutura de dados Pilha Indente corretamente o seu código e inclua comentários necessários no decorrer do seu programa Entrada A primeira linha da entrada consiste de dois inteiros V e E separados por espaço onde 1 V 1000 e 0 E VV 1 representando o número de povoados e o número de estradas que já foram construídas na Grafolândia respectivamente Cada povoado é representado por um código numérico entre 0 e V 1 Cada uma das próximas E linhas consiste de um par de números inteiros separados por espaços x y onde 0 x y V 1 que indicam que há uma estrada mágica do povoado x para o povoado y Saída A primeira linha da saída deve ser a frase Ha X regioes altamente conectadas onde X deve ser corretamente substituído pela quantidade de regiões altamente conectadas encontradas Se X 1 então escreva a frase Ha 1 regiao altamente conectada Não use acentos Cada uma das X linhas seguintes deve contar todos os povoados de uma região altamente conectada da Grafolândia em ordem crescente do código numérico e separados por espaço conforme os exemplos abaixo As regiões em si não têm uma ordem específica Exemplos Teste 1 Entrada 7 15 0 2 0 6 2 3 3 5 4 0 4 1 4 3 4 5 4 6 5 1 5 4 6 0 6 1 6 3 6 4 Possível saída Ha 2 regioes altamente conectadas 1 0 2 3 4 5 6 Teste 2 Entrada 14 32 1 3 1 5 2 4 2 5 3 1 3 2 3 4 4 0 4 5 5 0 5 1 5 2 5 7 6 7 7 8 7 13 9 8 9 12 9 13 10 8 10 11 10 12 11 12 11 13 12 8 12 10 12 11 13 6 13 7 13 9 13 10 13 11 Possível saída Ha 4 regioes altamente conectadas 0 8 6 7 9 10 11 12 13 1 2 3 4 5 Teste 3 Entrada Universidade Federal do ABC Moodle 2023 Português Brasil ptbr VPL 5 16 0 1 0 2 0 3 0 4 1 0 1 2 1 4 2 0 2 1 2 4 3 1 3 2 4 0 4 1 4 2 4 3 Única saída possível Ha 1 regiao altamente conectada 0 1 2 3 4 Conectando Povoados Distantes na Grafolândia Seguir para Lista 4 Este é o Ambiente Virtual de Aprendizagem da UFABC para apoio ao ensino presencial e semipresencial Esta plataforma permite que os usuários educadoresalunos possam criar cursos gerenciálos e participar de maneira colaborativa Informação Conheça a UFABC Conheça o NTI Conheça o Netel Contato Av dos Estados 5001 Bairro Bangu Santo André SP Brasil CEP 09210580 Siganos English en Português Brasil ptbr Obter o aplicativo para dispositivos móveis MCTA02817 Teoria dos Grafos Centro de Matemática Computação e Cognição Universidade Federal do ABC Profa Carla Negri Lintzmayer Lista 4 Conceitos básicos em digrafos 1 Vimos o seguinte resultado para grafos Se G é um grafo com δG 2 então G contém um caminho de comprimento pelo menos δG e um ciclo de comprimento pelo menos δG 1 Se for possível reescrevao e proveo adequadamente para digrafos Se não for apresente um contraexemplo 2 Vimos o seguinte resultado para grafos Todo grafo que não contém ciclos tem pelo menos dois vértices de grau 1 Se for possível reescrevao e proveo adequadamente para digrafos Se não for apresente um contraexemplo 3 Prove ou exiba um contraexemplo todo digrafo com ao menos dois vértices possui ao menos dois vértices com o mesmo grau de entrada ou ao menos dois vértices com o mesmo grau de saída 4 Quantas orientações um grafo simples possui 5 Vimos em sala que Se D é um um digrafo então D admite uma ordenação topo lógica se e somente se D é acíclico É possível extrair da prova desse teorema um algoritmo que devolve uma ordenação topológica para um dado digrafo de entrada Apresente um pseudocódigo para esse algoritmo 6 Prove que todo DAG tem um sorvedouroralo 7 Qual a relação entre as componentes fortemente conexas de um digrafo D e seu reverso D 8 Seja D um digrafo qualquer e seja x y V D tal que xy ED e yx ED Qual a relação entre as componentes fortemente conexas de D e D xy 9 Descreva um algoritmo que determine se um dado digrafo D é um DAG O seu algoritmo deve executar em tempo OV E 10 Prove que se D é um digrafo então vV G dv ED por indução no número de vértices 11 O que acontece quando nosso algoritmo de ordenação topológica executar a DFS e devolver os vértices em ordem decrescente de posordem é executado em um grafo dirigido que possui um ciclo 12 Prove que todo torneio possui um caminho gerador 1 13 Seja D um digrafo Seja CD o digrafo das componentes fortemente conexas de D também chamado digrafo condensação definido de forma que para cada componente fortemente conexa Ci de D há um vértice vi em V CD e existe um arco vivj ECD se e somente se existir um arco ab ED tal que a V Ci e b Cj a Desenhe CD1 e CD2 para os digrafos D1 e D2 das Figuras 1 e 2 b Prove que CD para qualquer D é um DAG 14 Prove que um digrafo D é um DAG se e somente se não são encontradas arestas de retorno em nenhuma chamada da DFS sobre D 15 O algoritmo de Kosajaru continuaria funcionando se uma ou ambas as passadas usassem busca em largura Justifique 16 Execute o algoritmo de ordenação topológica para o digrafo D3 17 Execute o algoritmo de Kosajaru sobre o digrafo D1 18 Execute o algoritmo de Tarjan sobre o digrafo D1 0 1 2 4 5 6 7 8 9 10 11 12 13 14 Figura 1 Digrafo D1 0 1 2 3 4 5 6 Figura 2 Digrafo D2 0 1 2 4 5 6 7 8 9 Figura 3 Digrafo D3 2 Guru 1 Questao 1 Grafos nao direcionados Seja P v0 v1 vk um caminho simples maximal em G Suponha que exista um vizinho vn de vk que nao esta em P Observe que P pode ser estendido anexando vn em seu final o que e uma contradicao pois P e maximal Logo todo vizinho de vk esta em P o que implica que P possui pelo menos dvk 1 vertices Como dvk δG entao P e um caminho de comprimento pelo menos δG Alem disso seja i o menor ındice tal que vi e vizinho de vk ou seja tal que vkvi EG Note que o subcaminho vi vk de P possui vk e todos os seus vizinhos possuindo portanto dvk 1 vertices Como ha uma aresta de vk para vi temos que vi vk vi e um ciclo com comprimento dvk 1 δG 1 assim como querıamos demonstrar Grafos direcionados Podemos provar propriedades analogas usando o grau de saıda mınimo δG e grau de entrada mınimo δG Seja P v0 v1 vk um caminho direcionado simples maximal em G Note que nao pode haver vn P tal que vkvn EG pois caso contrario podemos estender P anexando vn em seu final Da mesma forma nao pode haver vn P tal que vnv0 EG pois poderıamos estender P anexando vn em seu comeco Disso concluımos que todo vertice na vizinhanca de saıda de vk esta em P e portanto P tem tamanho pelo menos dvk δG Alem disso o menor ındice i tal que vkvi EG forma um ciclo de comprimento dvk 1 δG 1 Note tambem que todo vertice na vizinhanca de entrada de v0 esta em P e portanto P tem tamanho 1 pelo menos dvk δG Adicionalmente o maior ındice i tal que viv0 EG forma um ciclo de comprimento dv0 1 δG 1 2 Questao 5 Remova as linhas 2 e 3 ou declare que GrauEntradav como recebendo dv De resto o algoritmo esta certo para construir a ordenacao topologica contudo ele nao detecta ciclos corretamente Para tal vocˆe precisa ver se GrauEntradav e zero para todo vertices v no final do algoritmo pois isso simboliza que todos os vertices foram processados Seu algoritmo esta errado neste aspecto pois e possıvel que um grafo possua ciclo e ao mesmo tempo possua uma fonte E dado que seu algoritmo so coloca um vertice na fila quando todas as suas arestas de entrada forem removidas um vertice pertencente a um ciclo nunca sera colocado na fila e tera grau de entrada maior que 0 no final 3 Questao 8 Por simplicidade denotaremos que um vertice u alcanca um vertice v se ha um caminho direcionado de u para v Alem disso dois vertices u e v estao na mesma componente fortemente conexa se u alcanca v e v alcanca u Visto isso vamos dividir a analise em quatro casos 31 x nao alcanca y e y nao alcanca x Neste caso D e D xy sao iguais Pois y nao alcanca x em D xy e portanto x e y nao estao na mesma componente fortemente conexa no mesmo Como as componentes fortemente conexas de x e y nao mudaram de D para D xy as componentes dos demais vertices tambem se mantem as mesmas 32 x alcanca y e y nao alcanca x Neste caso D e D xy sao iguais Pois como x ja alcanca y em D temos que a aresta xy nao agrega em nada Note que neste caso x e y estao em componentes fortemente conexas distintas em ambos 2 os grafos 33 x nao alcanca y e y alcanca x Neste caso D e D xy sao diferentes Em D xy x e y se alcancam reciprocamente e portanto estao na mesma componente fortemente conexas Todos os vertices alcancaveis por y e que ao mesmo alcancam x em D serao unidos em uma unica componente fortemente conexa em D xy Os demais vertices nao terao suas componentes fortemente conexas alteradas 34 x alcanca y e y alcanca x Neste caso D e D xy sao iguais pois como x ja alcanca y em D a aresta xy nao agrega em nada Note que neste caso x e y estao na mesma componente fortemente conexas em ambos os grafos 4 Questao 11 Corrigindo a questao 5 sua explicacao nesta esta correta 5 Questao 12 Nao entendi sua prova segue a minha abaixo Claramente o resultado vale para um torneio G tal que V G 0 Vamos considerar entao um torneio G tal que V G 0 Seja vi V G entao crie G1 e G2 tal que G1 seja o grafo induzido de G por todos os vertices vn onde vivn EG e G2 seja o grafo induzido de G por todos os vertices vn onde vnvi EG Claramente V G1 V G e V G2 V G pois ambos os grafos nao contem vi Alem disso note que G1 e G2 tambem sao torneios Por hipotese de inducao seja PG1 e PG2 o caminho gerador de G1 e G2 respectivamente Note que PG1viPG2 e um caminho gerador de G pois se V G1 entao ha um aresta do ultimo vertice de PG1 para vi por construcao e se V G2 entao ha um aresta de vi para o primeiro vertice de PG2 por construcao 3 6 Questao 13 61 a No grafo D1 temos as componentes fortemente conexas C0 9 11 10 12 13 14 C1 3 C2 2 C3 0 1 4 C4 5 6 C5 7 C6 8 Na figura abaixo mostramos CD1 No grafo D2 temos uma unica componente fortemente conexa C0 0 1 2 3 4 5 6 logo CD2 e um unico vertice isolado 62 b Suponha que CD nao seja acıclico seja W C1 C2 Cn C1 um ciclo de CD Note que para todo par de vertices u Ci e v Cj com Ci Cj W temos que u e v se alcancam reciprocamente em D Logo C1C2 Cn e uma componente fortemente conexa de D o que e uma contradicao dado que C1 C2 Cn deveriam ser maximais Logo CD e acıclico 4