PUERTA | PUERTA CS 1999 | Pregunta 53

[Pregunta de 5 puntos]

Sea G un grafo conexo no dirigido. Un corte en G es un conjunto de aristas cuya eliminación da como resultado que 0 se rompa en dos o más componentes que no están conectados entre sí. El tamaño de un corte se llama su cardinalidad. Un corte masculino de G es un corte en G de cardinalidad mínima. Considere el siguiente gráfico.

una. ¿Cuál de los siguientes conjuntos de aristas es un corte?

(i) {(A,B), (E,F), (B,D), (A,E), (A,D)}

(ii) {(B,D), (C,F), (A,B)}

b. ¿Cuál es la cardinalidad de un corte mínimo en el gráfico?

C. Demuestre que si un grafo G no dirigido conexo con n vértices tiene un corte mínimo de cardinalidad K, entonces G tiene al menos (nk/2) aristas.

Respuesta:
Explicación:
Cuestionario de esta pregunta