Clasificación topológica

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.

Ejemplo

para contar $G={\Bigl (}{\bigl \{}2,3,5,7,8,9,10,11{\bigr \)),{\bigl \{}(3,8),(3, 10),(5,11),(7,11),(7,8),(8,9),(11,2),(11,9),(11,10){\mayor \}} {\Gran R )}$

hay varias secuencias consistentes de sus vértices, que se pueden obtener utilizando una ordenación topológica, por ejemplo:

$7,5,11,3,8,2,9,10$
$3,7,5,8,11,10,9,2$

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 . $mi$

Algoritmo de Kahn (1962)

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. $G=(V,E)$ $A(v),v\en V$ ${\ estilo de visualización u \ en V}$ $\existe ~(u,v)\en E$ $AV)$ $v$ $PAGS$

por ahora , elija cualquier vértice tal que y elimínelo de todos

|P|<|V|

v

A(v)=\varnada

v\notin P

P\obtiene P,v

v

A(u),u\neqv

La 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 . $v$

Un ejemplo de cómo funciona el algoritmo

Sea dada una gráfica . En este caso, el algoritmo se ejecutará de la siguiente manera: $G={\Bigl (}{\bigl \{}a,b,c,d,e{\bigr \)),{\bigl \{}(a,b),(a,c),(a, d),(a,e),(b,d),(c,d),(c,e),(d,e){\bigr \}}{\Bigr )}$

paso	$v$	$Automóvil club británico)$	$un (b)$	$C.A)$	$Anuncio)$	$un(e)$	$PAGS$
0	$-$	$\varnada$	$a$	$a$	$a B C$	$a, c, d$	$\varnada$
una	$a$	$\varnada$	$\varnada$	$\varnada$	$antes de Cristo$	$discos compactos$	$a$
2	$C$	$\varnada$	$\varnada$	$\varnada$	$b$	$d$	$C.A$
3	$b$	$\varnada$	$\varnada$	$\varnada$	$\varnada$	$d$	$a, c, b$
cuatro	$d$	$\varnada$	$\varnada$	$\varnada$	$\varnada$	$\varnada$	$a, c, b, d$
5	$mi$	$\varnada$	$\varnada$	$\varnada$	$\varnada$	$\varnada$	$a, c, b, d, e$

En el segundo paso , se puede elegir el vértice en lugar de , ya que no se especifica el orden entre y . $C$ $b$ $b$ $C$

Algoritmo de Tarjan ( 1976)

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:

Inicialmente, todos los vértices son blancos.
Para cada vértice hacemos un paso del algoritmo.

Paso del algoritmo:

Si el vértice es negro, no es necesario hacer nada.
Si el vértice es gris, se encuentra un ciclo, la clasificación topológica no es posible.
Si la parte de arriba es blanca
- pintarlo de gris
- Aplicamos el paso del algoritmo a todos los vértices que se pueden alcanzar desde el actual
- Colorea el vértice de negro y colócalo en la parte superior de la lista final.

Ejemplo

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

Aplicación

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).

Véase también

Algoritmo de Demucron

Enlaces

Literatura

Levitin A. V. Capítulo 5. Método de reducción del tamaño del problema: Clasificación topológica // Algoritmos. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 220-224. — 576 pág. — ISBN 978-5-8459-0987-9
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Capítulo 22.4. Clasificación topológica // Algoritmos: construcción y análisis = Introducción a los Algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - S. 632-635. — ISBN 5-8459-0857-4 .

Algoritmos de clasificación
Teoría	Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo
Intercambio	burbuja Emocionante enanos Rápido Peine Clasificación par-impar bit a bit
Elección	Elección Piramidal Suave
inserciones	inserciones cáscara árbol
fusión	fusión
sin comparaciones	Contando bloquear
híbrido	introsorteo Timsort
Otro	topológico redes bitón
poco práctico	Bogosort Tipo de títere tortita lento