2024-151

Lembrando que \( \kappa(x,y) \) é o mínimo tamanho de um corte que separa \(x\) de \(y\), considere as seguintes alternativas e selecione a correta, considerando que \( x, y \) são dois vértices que não tenham uma aresta direta entre si nos grafos em questão.

a) \( \kappa(x,y) = 2\) em um \( C_6 \), \( \kappa(x,y) = 2\) em um \( P_6 \) e \( \kappa(x,y) = 3\) em um \( K_{3,3} \). 

b) \( \kappa(x,y) = 1\) em um \( C_6 \), \( \kappa(x,y) = 1\) em um \( P_6 \) e \( \kappa(x,y) = 3\) em um \( K_{3,3} \). 

c) \( \kappa(x,y) = 1\) em um \( C_6 \), \( \kappa(x,y) = 1\) em um \( P_6 \) e \( \kappa(x,y) = 1\) em um \( K_{3,3} \). 

d) \( \kappa(x,y) = 2\) em um \( C_6 \), \( \kappa(x,y) = 1\) em um \( P_6 \) e \( \kappa(x,y) = 3\) em um \( K_{3,3} \). 

e) N.D.A.

Ideia original de: Guilherme Michel Carvalho

2024-148

Considere as seguintes afirmações: 

1-) O grafo de Petersen possui 1-fator, 2-fator e 3-fator.

2-) O grafo abaixo possui emparelhamento perfeito.

3-) Para o grafo abaixo, temos que sua conectividade é κ = 3.

4-) Para o grafo abaixo, temos  κ < κ'.

Assinale a alternativa CORRETA:

a-) Somente as afirmativas 1 e 3 estão corretas

b-) Somente as afirmativas 2 e 4 estão corretas

c-) Somente as afirmativas 1, 2 e 4 estão corretas

d-) Somente as afirmativas 3 e 4 estão corretas

e-) N.D.A.

Ideia original de: Guilherme A. Terrell

2024-147

Considere o seguinte grafo não dirigido com 14 nós e 25 arestas. Cada nó possui um peso associado, conforme mostrado na ilustração. Qual é a soma máxima dos pesos de um corte mínimo no grafo? 

a) 9

b) 15

c) 7

d) 16

e) NDA

Ideia original de: Juan David Nieto

2024-146

Considere o grafo G abaixo com \(|V(G)| = 11\) e as afirmações a seguir:

1 - \(G\) tem exatamente 8 blocos.

2 - \(\kappa(G)= \kappa'(G) = 1\).

4 - O maior bloco de \(G\) tem tamanho 4.

A soma das afirmações corretas é:

A) 6

B) 5

C) 3

D) 2

E) NDA

Ideia Original de: Gabriel Cruz Vitale Torkomian