Conectividad de gráficos por eliminación de bordes y vértices

Digamos que un gráfico es comunicado con los si la eliminación de cualquier vértices y cualquier bordes de hojas siempre un gráfico conectado. Por ejemplo, un gráfico conectado a , según la definición estándar, está conectado , según la nueva definición. ¿Existe un algoritmo de tiempo polinómico para decidir si está conectado ? Aquí considero que la entrada es , y . $G$ $(a,b)$ $a$ $b$ $G$ $k$ $(k-1,0)$ $G$ $(a,b)$ $G$ $a$ $b$

ds.algorithms graph-theory graph-algorithms alguien
fuente

Problema de tarea?

Chandra Chekuri

Llegué a esta pregunta durante una charla de Janez Zerovnik sobre la conectividad de redes de aproximadamente 2/3 años. Para ser sincero, no recuerdo los detalles. Desde entonces, he preguntado acerca de 4 investigadores y nadie vio cómo reducirlo a la conectividad de vértice (o conectividad de borde), que sería el enfoque obvio. Además, nadie podría señalar un teorema de tipo Menger. Entonces sí, creo que esta es una pregunta de nivel de investigación, posiblemente con una respuesta simple o no.

alguien

No sé por qué la gente a veces asume que una pregunta es tarea sin pensarlo primero. Creo que no debes declarar algo de tarea a menos que al menos sepas cómo resolverlo.

domotorp

@domotorp: las personas generalmente preguntan si es una tarea, no reclaman. Es difícil juzgar si una pregunta está a nivel de tarea o no cuando la pregunta no contiene antecedentes / motivación.

Kaveh

Entiendo que mi pregunta podría malinterpretarse como tarea por varias razones, pero ahora deberíamos seguir adelante. En realidad, con el comentario de Chandra Chekuri, tengo la esperanza de que tal vez la pregunta tenga una respuesta simple ...

Alguien

Conectividad de gráficos por eliminación de bordes y vértices

Respuestas: