¿Qué significa "Gráfico Ordenado"?
Tabla de contenidos
Un grafo ordenado es un tipo de grafo donde los vértices están organizados en un orden específico. En este tipo de configuración, los vértices se colocan a lo largo de una línea recta, que se llama la columna vertebral. Cada arista conecta dos vértices y debe seguir este orden.
Dibujo de Grafos
Cuando dibujamos grafos ordenados, tratamos de minimizar cuántas aristas se cruzan entre sí. Esto es importante para la claridad y la comprensión visual. Podemos dibujar las aristas en varias páginas, y el número de páginas necesarias para mostrar el grafo sin que haya cruces se llama el número de páginas.
Reduciendo Cruces
Una forma de hacer el dibujo más claro es eliminar algunas aristas o vértices. Esto significa que podemos borrar ciertas partes del grafo para crear una versión que se vea más bonita.
Conjunto de Golpeo
Otro concepto es el conjunto de golpeo. Esto es una selección de puntos en la columna vertebral que toca todas las aristas. Si tenemos un punto, podemos averiguar fácilmente cuántas aristas necesitamos quitar para seguir dibujando el grafo de forma clara. Si tenemos más de un punto, el problema se complica un poco, pero aún podemos encontrar una solución.
Dibujo de Columna Vertebral + t-Ruta
En algunos casos, no todos los vértices están en la columna vertebral. Necesitamos colocar estos otros vértices en líneas separadas, llamadas rutas, mientras mantenemos el orden de los vértices en la columna vertebral intacto. Cada ruta es paralela a la columna vertebral y ayuda a mantener un diseño claro del grafo.