En el subcampo matemático de la teoría de grafos, una estructura de nivel de un grafo no dirigido es una partición de los vértices en subconjuntos que tienen la misma distancia desde un vértice raíz dado. [1]
Definición y construcción
Dado un grafo conectado G = ( V , E ) con V el conjunto de vértices y E el conjunto de aristas , y con un vértice raíz r , la estructura de niveles es una partición de los vértices en subconjuntos L i llamados niveles, que consisten en el vértices a una distancia i de r . De manera equivalente, este conjunto puede definirse estableciendo L 0 = { r }, y luego, para i > 0, definiendo L i como el conjunto de vértices que son vecinos de los vértices en L i - 1 pero que no son ellos mismos en ninguna anterior. nivel. [1]
La estructura de niveles de un gráfico se puede calcular mediante una variante de búsqueda en amplitud : [2] : 176
nivel de algoritmo -BFS (G, r): Q ← {r} para ℓ de 0 a ∞: process (Q, ℓ) // el conjunto Q contiene todos los vértices en el nivel ℓ marcar todos los vértices en Q como descubiertos Q '← {} para u en Q: para cada borde (u, v): si v aún no está marcado: agregar v a Q ' si Q 'está vacío: volver Q ← Q '
Propiedades
En una estructura de nivel, cada borde de G tiene sus dos extremos dentro del mismo nivel o sus dos extremos están en niveles consecutivos. [1]
Aplicaciones
La partición de un gráfico en su estructura de niveles se puede utilizar como heurística para problemas de diseño de gráficos, como el ancho de banda del gráfico . [1] El algoritmo de Cuthill-McKee es un refinamiento de esta idea, basado en un paso de clasificación adicional dentro de cada nivel. [3]
Las estructuras de nivel también se utilizan en algoritmos para matrices dispersas , [4] y para construir separadores de gráficos planos . [5]
Referencias
- ↑ a b c d Díaz, Josep; Petit, Jordi; Serna, Maria (2002), "Una encuesta de problemas de diseño de gráficos" (PDF) , Encuestas de computación de ACM , 34 (3): 313–356, CiteSeerX 10.1.1.12.4358 , doi : 10.1145 / 568522.568523.
- ^ Mehlhorn, Kurt ; Sanders, Peter (2008). Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) . Saltador.
- ^ Cuthill, E .; McKee, J. (1969), "Reducing the bandwidth of sparse symmetric matrices", Actas de la 24ª conferencia nacional de 1969 (ACM '69) , ACM, págs. 157-172, doi : 10.1145 / 800195.805928.
- ^ George, J. Alan (1977), "Solución de sistemas lineales de ecuaciones: métodos directos para problemas de elementos finitos", Técnicas de matrices dispersas (Curso avanzado, Universidad Técnica de Dinamarca, Copenhague, 1976) , Berlín: Springer, págs. 52 –101. Lecture Notes in Math., Vol. 572, MR 0440883.
- ^ Lipton, Richard J .; Tarjan, Robert E. (1979), "Un teorema del separador para gráficas planas", SIAM Journal on Applied Mathematics , 36 (2): 177–189, CiteSeerX 10.1.1.214.417 , doi : 10.1137 / 0136016.