¿Se le ha dado una gráfica para detectar si es un árbol o no en gráficas dirigidas y no dirigidas?

Me gustaría saber de un algoritmo rápido para determinar si un gráfico dado es un árbol o no.Esta La publicación parece tratarlo, pero no muy clara. De acuerdo con esto, si la gráfica es acíclica, entonces es un árbol. Si considera los ejemplos de gráficos dirigidos y no dirigidos que se muestran, en mi opinión, solo 1 y 4 son árboles, pero 3 no es ni cíclico ni un árbol, supongo.

así que mi pregunta es: ¿qué se debe verificar para ver si un gráfico es un árbol o no, tanto para el gráfico dirigido como el no dirigido de manera eficiente?

Un paso adelante para ver si un árbol existe, ¿es un árbol binario o no?

Respuestas a la pregunta(1)

Su respuesta a la pregunta