algorithm - tabla - Algoritmo: para G=(V, E), cómo determinar si el conjunto de bordes(e pertenece a E) es un conjunto de corte válido de un gráfico

informe de laboratorio de fisica analisis grafico

Question

Dado un subconjunto de bordes de un gráfico G = (V, E), ¿cómo podemos verificar si es un corte válido del gráfico o no? Nota: Un corte es una partición de los vértices de un gráfico en dos subconjuntos disjuntos. Por lo tanto, el corte del corte es el conjunto de bordes cuyos puntos finales se encuentran en subconjuntos diferentes de la partición. Estoy interesado en encontrar un algoritmo para este problema

Answer 1

Es un conjunto de corte válido si, con ese subconjunto de borde eliminado, deja de ser un gráfico conectado.

Si está solicitando algoritmos, debería poder comenzar en cualquier nodo y ver si puede llegar a todos los demás nodos mediante la primera búsqueda en profundidad. Si es así, no es un conjunto de corte válido, si no puede, es un conjunto de corte válido.

Answer 2

Un algoritmo simple sería eliminar los bordes de corte sospechosos del gráfico, y ver si todavía puede obtener desde un nodo de un borde eliminado a su contraparte. Si todavía puedes, no fue un corte completo. Entonces, si eliminas E2 que tenía nodos A y D, puedes usar la primera búsqueda de amplitud desde A y ver si alguna vez llegas a D. Debería ser lineal en cuanto a requisitos de espacio y complejidad ya que almacenamos todos los nodos que hemos visitado, así que no retroceda y visite ningún nodo dos veces. Esta página wiki tiene algunas buenas imágenes que pueden ayudar: http://en.wikipedia.org/wiki/Cut_%28graph_theory%29