Prova 2 de Teoria dos Grafos

Prova 2 de Teoria dos Grafos Questão 1 2 pontos Exiba um digrafo ponderado com arcos com custo ne gativo mas sem ciclos de custo negativo que quando submetido ao algoritmo de Dijkstra a partir de uma certa origem não produz caminhos de custo mí nimo Exiba também a simulação do algoritmo de Dijkstra neste exemplo Tente produzir o menor exemplo possível Questão 2 2 pontos Nesta questão você deve escrever um algoritmo que encontra um caminho maximal em um grafo A representação de um grafo é dada pelo seu conjunto de vértices V pelo corte x de cada vértice x X e pela função de incidência ι que devolve as pontas de cada aresta do grafo Não é necessária uma descrição de baixo nível do algoritmo Assim você pode manipular objetos matemáticos como conjuntos sequências e funções desde que esteja evidente um mapeamento para estruturas de dados básicas Questão 3 5 pontos Seja D c 0 um digrafo ponderado Vamos definir uma nova noção de custo de um caminho Seja P um caminho de D O custo de P denotado cP é o número minca a AP Note que se AP então cP Sejam s t vértices de D Dizemos que um stcaminho P é cmáximo se cP cQ para cada stcaminho Q de D Para um vértice s de D dizemos que uma sarborescência T é cmáxima se Ts t é cmáximo para cada t VT i 3 pontos Mostre que se T é uma sarborescência cmáxima e V T então T a também é uma sarborescência cmáxima onde a V T é tal que mincTs a ca mincTs e ce para cada e V T A hipótese c 0 é relevante para a sua prova ii 2 pontos Sugira um algorito que dado um digrafo ponderado e um 1 vértice s determina uma sarborescência cmáxima cujo conjunto de vértices é o território de s Questão 4 5 pontos O Teorema de König estabelece que em um grafo bi partido o tamanho de uma cobertura mínima coincide com o tamanho de um emparelhamento máximo Uma árvore é um grafo bipartido e portanto em uma árvore o Teorema de König também é válido Nesta questão você vai produzir uma prova direta do Teorema de König para árvores i Mostre que se T é uma árvore nãotrivial então existe um vértice de T tal que todos os seus vizinhos exceto no máximo um são folhas de T ii Agora você vai provar o Teorema de König para árvores por indução no número de vértices Para o passo da indução suponha que T é uma árvore e T 3 Selecione um vértice r como no item i e divida a prova em dois casos dr 2 ou dr 3 Seja t uma folha de T que é vizinha de r No primeiro caso considere a árvore T r t no segundo considere a árvore T t 2