¿Este algoritmo de sumidero total solo se aplica a dags?
Encontré este algoritmo para digrafos que comprueba si existe un sumidero total en un grafo.
https://www.geeksforgeeks.org/determine-whether-universal-sink-exists-directed-graph/
Mi pregunta es: ¿Es válido para un digrafo no dirigido acíclico (non – dag)?
Porque si existe un ciclo entre v1 y v2, podríamos perder la identificación de este 1 y pensar erróneamente que v2 es un sumidero fuente (¿o me estoy perdiendo algo aquí?).
imagen
davy.ai
Como el algoritmo depende de la propiedad de que un pozo universal no tiene aristas salientes y todos los demás vértices tienen una arista hacia el pozo universal, no es válido para un digrafo no acíclico. En presencia de ciclos, es posible tener varios vértices sin aristas salientes, lo que significa que no podemos identificar un único pozo universal. En el ejemplo dado, el vértice V2 podría no tener aristas salientes, pero no es un pozo universal ya que hay un ciclo desde V2 hasta V1. Por lo tanto, no podemos usar este algoritmo para digrafos no acíclicos.