La respuesta es una si P y Q están originalmente conectados.
Aquí hay una prueba por contradicción. Asumimos que cualquier otro vértice que se elimine, P y Q todavía están conectados. Probaré que debería haber más de 2 * N vértices. La idea está relacionada con el teorema de corte mínimo de flujo máximo.
Podemos dividir todos los vértices en dos grupos con P en el primer grupo y Q en el segundo grupo. Dada nuestra suposición, si Q no tiene un vecino en el primer grupo, debería haber al menos dos vértices en el segundo grupo que tengan un vecino en el primer grupo, sin importar cómo dividimos los vértices. De lo contrario, P y Q no están conectados originalmente, o solo hay un vértice que tiene un vecino en el primer grupo para que podamos destruirlo para desconectar P y Q. Ambos contradicen nuestra suposición.
- ¿Qué algoritmos pueden detectar si dos imágenes / objetos son similares o no?
- ¿Cuál es la estrategia de divide y vencerás? Escribe un algoritmo para encontrar x a la enésima potencia usando el método de dividir y conquistar.
- Cómo escribir un programa para encontrar la frecuencia de la presencia de un elemento en una matriz en C ++
- ¿Cómo funcionan los algoritmos y la estructura de datos cuando procesamos cualquier solicitud en un sitio web?
- ¿Existe un algoritmo de tiempo O (N) para esta pregunta?
Ahora hacemos un BFS comenzando con P. Definimos dos grupos: el grupo A tiene los vértices visitados; el grupo B tiene los vértices restantes. Inicialmente, el grupo A tiene un solo vértice P, mientras que el grupo B tiene los vértices restantes 2 * N – 1. Como probé antes, habrá al menos dos vértices que tengan vecinos en el grupo A. Por lo tanto, se agregarán al menos dos vértices al grupo A después de la primera iteración del BFS. Y en las siguientes iteraciones, siempre que Q no tenga un vecino en el grupo A, podemos encontrar al menos otros dos vértices en el grupo B y agregarlos al grupo A.
Como la ruta más corta de P a Q no es más corta que N + 1, el BFS no terminará después de las primeras N iteraciones. Pero después de N iteraciones, hay al menos 1 + 2 * N vértices en el grupo A que es más de 2 * N.
