Tome cualquier gráfico G fuertemente conectado y elija cualquiera de los dos vértices aib [para n = 1 la tesis es trivial]. Hay un camino de a a b y de b a a, elíjalos y vea cuántos vértices visitan mientras tanto, llame a esto k (k = número de vértices visitados, incluidos ayb). Está bastante claro que este ciclo podría haber tenido como máximo 2k-2 bordes: ayb aparecen solo una vez en el ciclo y cualquier otro vértice aparece como máximo dos veces.
Entonces, para la conectividad de esta parte del gráfico, solo como máximo los bordes 2k-2 fueron de hecho cruciales, si hay otros bordes entre estos vértices, son innecesarios y podrían eliminarse. Intentaremos extender esta afirmación a todo el gráfico, si podemos demostrar para todo el gráfico que uno puede encontrar como máximo 2n-2 bordes que son cruciales, entonces la tesis se vuelve obvia. Entonces, tienes estos k vértices (llámalos visitados) conectados en algún ciclo. Si no hay vértices no visitados, la prueba ha finalizado. Si los hay, intentemos expandir nuestra “red de nodos visitados” tomando cualquier borde que vaya de un vértice visitado a uno no visitado. El gráfico está fuertemente conectado, por lo que debe existir la posibilidad de regresar de este vértice, es decir, debe haber una ruta desde este vértice no visitado hasta al menos uno de los visitados. Tome el camino más corto, obviamente, no aparecen nodos en él dos veces. Así que hemos fundado una ruta: | vértice visitado -> m vértices no visitados -> algún otro vértice visitado |, donde no aparece ningún nodo dos veces (aparte del punto inicial y final posiblemente podría ser el mismo). Esta ruta agregó m vértices a nuestra red visitada a expensas de agregar m + 1 bordes cruciales. Repita este procedimiento hasta que no se vean vértices.
En el primer paso, hemos agregado k vértices al introducir no más de 2k-2 bordes cruciales. En otros pasos, hemos estado agregando m vértices a la vez mediante la introducción de m + 1 aristas, así que no importa cuál sea m, m + 1 <= 2m, es decir, no hemos agregado más de 2m aristas en ese momento. Como al final no hay vértices no visitados, hemos agregado no más de 2n-2 bordes cruciales en todo el procedimiento.
- ¿Cuál es el significado de matriz redimensionable en arraylist?
- Algoritmos: ¿Qué sucede cuando un usuario crea una matriz de tamaño -100, qué sucede en la memoria?
- ¿Qué es el algoritmo Twofish?
- ¿Qué es una estructura de datos dinámicos de pila?
- ¿Cuál es el enfoque algorítmico para encontrar los intervalos de tiempo libre de ambas personas para que puedan organizar una reunión, dado el conjunto de intervalos de tiempo ocupado de dos personas, como en un calendario?
(¿Cuál es la razón por la que necesitabas esta propiedad por cierto ya que no es una tarea, es una subtarea de algún problema más interesante en el que estás pensando?)
