¿Hay alguna manera de agregar un nodo a un digrafo sin agregar un nuevo orden topológico?

Question

Tengo un digrafo con $n$ nodos. Quiero agregar un nuevo nodo al grafo, pero no necesariamente quiero agregar una nueva arista para conectar este nodo. En esencia, quiero que el grafo siga siendo acíclico.

¿Puedo agregar este nuevo nodo sin cambiar el número de ordenaciones topológicas en el grafo?

Supongamos que termino agregando nueva(s) arista(s) para conectar el nuevo nodo. ¿Puedo hacerlo y obtener un grafo que tenga $a(n + 1)$ ordenaciones topológicas, con $a$ representando el número de ordenaciones topológicas antes de la adición?

Answer 1

Si agregas un nuevo vértice $v$ a un grafo y agregas aristas $xv$ para cada vértice $x$ en el grafo, el vértice $v$ debe venir al final de cualquier ordenamiento topológico del nuevo grafo, por lo que habrá el mismo número de ordenamientos topológicos como si no se hubiera agregado $v$.

Sospecho que tu otra pregunta, preguntando si puedes agregar $v$ de tal manera para aumentar el número de ordenamientos topológicos por un factor de $n+1$ es mucho más difícil. Dudo que todos los grafos tengan esta propiedad, y no tengo idea de cómo clasificar los que lo tienen, pero puedo imaginar que hay un algoritmo ingenioso que puede buscar de manera metódica tal forma de agregar un nuevo vértice.