Caminhos mínimos

Dado o contexto de árvores geradoras mínimas e caminhos mínimos, assinale a alternativa não necessariamente correta. Assuma que os grafos citados são ponderados.

a) Seja (S, V-S) um corte em um grafo G, e seja e uma aresta que cruza esse corte (com um terminal em S e outro em V-S). Uma aresta é dita leve se tiver o menor peso entre todas as arestas que cruzam o corte.

b) Toda aresta leve faz parte de alguma árvore geradora mínima.

c) Se T é uma árvore geradora mínima do grafo G, então o caminho P_uv em T é o caminho mínimo de u para v em G.

d) Para todo grafo simples com |E| >= 1, existe pelo menos um par uv tal que o caminho mínimo de u para v contém apenas uma aresta

e) N.D.A.

Comentários

  1. Joao Meidanis12 de abril de 2024 às 15:33

    Complicado. A alternatiova (a) é só definição, e usada nas outras. Não é uma questão bem formulada.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Jogo de boca

Considere um jogo com as seguintes regras: Cada partida é entre 2 jogadores. A cada rodada o jogador da vez deve falar o próximo número para ser o da mesa Suponha que n seja o número atual da mesa, o jogador da vez pode escolher ou n + 1 ou n + 2 para ser o próximo número da mesa. O valor inicial n_0 da mesa é 0 . O jogador que falar 21 vence a partida. Dada a descrição do jogo, assinale a alternativa que contém apenas afirmações corretas. Você pode assumir que os jogadores sempre jogam de maneira ótima: I - Apesar do jogador que começa ter uma vantagem, o jogo não possui uma estratégia ótima. II - O segundo jogador sempre vence. III - Numa variação onde vence quem fala o número 31, o primeiro jogador pode sempre ganhar desde que seu primeiro lance seja "n = 1". IV - Numa variação onde vence quem fala o número 31, o primeiro jogador pode sempre ganhar desde que seu primeiro lance seja "n = 2". V - O jogo pode terminar em empate. a) II, IV, V b) I e V c) I, III ...
Leia mais

Caminhos, trilhas e passeios

 Seja G um grafo conexo. Sabendo que cada aresta de G é uma aresta de corte, assinale a afirmativa incorreta. a) G é bipartido b) Todo vértice v de grau d_v  > 1 em G é um vértice de corte c) G é euleriano. d) Sejam u e v dois vértices não adjacentes em G e C a quantidade de ciclos em G. Ao inserir a aresta uv em G, o grafo passará a ter C + 1 ciclos. e) N.D.A Ideia original de: Luiz Gustavo Aguiar
Leia mais