Estoy buscando un método/algoritmo rápido para encontrar qué nodos en un gráfico es crítico.¿Qué es un algoritmo rápido para encontrar nodos críticos?
Por ejemplo, en este gráfico: 
número de nodo 2 y 5 son críticos.
Mi método actual es intentar eliminar un nodo no terminal del gráfico a la vez y luego verificar si se puede llegar a toda la red desde todos los otros nodos. Este método es obvio no muy eficiente.
¿Qué es una manera mejor?
Ver biconnected components. Llamarlos puntos de articulación en lugar de nodos críticos parece producir mejores resultados de búsqueda.
En cualquier caso, el algoritmo consiste en un simple depth first search donde se guarda cierta información para cada nodo.
Muchas gracias, los puntos de articulación realmente dieron mejores resultados y encontré algunos muy enlaces útiles a la primera búsqueda en profundidad. – monoceres
hay varias formas mejores. research is always helpful
pero ya que esta es la tarea, el objetivo del ejercicio es probable que sea a la figura hacia fuera usted mismo
pista: ¿cómo puedes decorar el gráfico que le diga qué nodos dependen de qué otros nodos, y me esta información quizás sea útil para detectar los nodos críticos?
Ver: http://portal.acm.org/citation.cfm?id=1480409. Demuestran que la detección de nodos críticos es NP completa, por lo que no esperaría mejoras drásticas. –
¿Le preocupan los nodos, no los enlaces? Por ejemplo, si tengo un enlace entre 3 y 6, entonces, para encontrar nodos críticos, primero necesito encontrar enlaces que puedan eliminarse. –
@Jerry Coffin - Recuerdo algo sobre esto en una clase de análisis de red eléctrica, pero tendría que volver a buscarlo, pero, dependiendo de las simplificaciones, esto puede ser fácil o muy difícil de resolver, ya que el caso general es demasiado difícil, como usted señaló. –