La clasificación topológica es la ordenación de los vértices de un gráfico dirigido sin contorno de acuerdo con el orden parcial dado por las aristas del dígrafo en el conjunto de sus vértices.
para contar
hay varias secuencias consistentes de sus vértices, que se pueden obtener utilizando una ordenación topológica, por ejemplo:
Puede verse que dos vértices adyacentes cualesquiera que no estén incluidos en la relación de orden parcial pueden permutarse en la secuencia .
Uno de los primeros algoritmos, y el más adecuado para la ejecución manual.
Sea un grafo simple orientado sin contorno . Denote por el conjunto de vértices tal que . Es decir , el conjunto de todos los vértices de los cuales hay un arco al vértice . Sea la secuencia deseada de vértices.
por ahora , elija cualquier vértice tal que y elimínelo de todosLa presencia de al menos un contorno en el gráfico hará que en una determinada iteración del ciclo no sea posible seleccionar un nuevo vértice .
Sea dada una gráfica . En este caso, el algoritmo se ejecutará de la siguiente manera:
paso | |||||||
---|---|---|---|---|---|---|---|
0 | |||||||
una | |||||||
2 | |||||||
3 | |||||||
cuatro | |||||||
5 |
En el segundo paso , se puede elegir el vértice en lugar de , ya que no se especifica el orden entre y .
En una computadora, se puede realizar una ordenación topológica en tiempo y memoria O( n ) recorriendo todos los vértices mediante la búsqueda en profundidad y generando los vértices en el punto de salida.
En otras palabras, el algoritmo es el siguiente:
Paso del algoritmo:
El ejemplo estará en el mismo gráfico, pero el orden en el que seleccionamos los vértices para omitir es c, d, e, a, b.
Paso | Actual | Blanco | Pila (gris) | Salir (negro) |
---|---|---|---|---|
0 | — | a B C D e | — | — |
una | C | un, b, d, e | C | — |
2 | d | un, b, mi | discos compactos | — |
3 | mi | un, b | c, d, e | — |
cuatro | d | un, b | discos compactos | mi |
5 | C | un, b | C | re, mi |
6 | — | un, b | — | c, d, e |
7 | d | un, b | — | c, d, e |
ocho | mi | un, b | — | c, d, e |
9 | a | b | a | c, d, e |
diez | b | — | un, b | c, d, e |
once | a | — | a | b, c, d, e |
12 | — | — | — | a B C D e |
13 | b | — | — | a B C D e |
Con la ayuda de la clasificación topológica, se construye una secuencia correcta de acciones, cada una de las cuales puede depender de la otra: la secuencia de pasar cursos de capacitación por parte de los estudiantes, instalar programas usando el administrador de paquetes , construir códigos fuente de programas usando Makefiles .
Es posible construir una lista de visualización de objetos en una proyección isométrica conociendo las relaciones ordinales emparejadas entre los objetos (cuál de los dos objetos debe dibujarse primero).
Algoritmos de clasificación | |
---|---|
Teoría | Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo |
Intercambio | |
Elección | |
inserciones | |
fusión | |
sin comparaciones | |
híbrido | |
Otro | |
poco práctico |