← Volver a los ejercicios

El valor low de cada vértice

En el algoritmo de Tarjan cada vértice guarda d, el orden en que se descubre, y low, el menor d al que llega desde su subárbol con a lo sumo una flecha que no es de árbol. Un hijo de árbol aporta su low; cualquier otra flecha aporta el d del otro extremo, pero solo si ese vértice sigue en la pila. La búsqueda ya corrió: el árbol está dibujado y cada vértice trae su d. Falta el low de cada uno.

1. El grafo con la búsqueda hecha

Grafo:

Flechas azules gruesas: el árbol de la búsqueda. Flechas punteadas: las demás. La búsqueda arranca en el vértice 0 y recorre cada lista en el orden en que está escrita.

2. El low de cada vértice

Conviene empezar por las hojas del árbol y subir: el low de un vértice necesita el de sus hijos.

3. Para llevarse

Sin solución aquí. En el grafo de los módulos, agregue la flecha ir → lex y diga qué cambia en los low y en los componentes, y por qué. Después, en el grafo de mensajería, quite la flecha router → origen, recalcule los low y escriba qué componentes se cierran y en qué orden.