-
Regular
-
Completo
Laboratorio de teoría de grafos
Un grafo es un conjunto de puntos, llamados vértices, unidos por líneas, llamadas aristas. Dibuja uno aquí con unos pocos clics y el laboratorio te dirá qué tipo de grafo es: cuántas partes tiene, si es un árbol, cuántos colores necesita como mínimo, si se puede dibujar de un solo trazo y mucho más. Haz clic en una propiedad para verla en tu grafo, cambia una arista y observa cómo cambian las respuestas. Haz clic en un espacio vacío para añadir un vértice. Haz clic en un vértice y luego en otro para unirlos con una arista; repítelo para quitar la arista. Arrastra un vértice para moverlo. Cambia el clic a Borra y haz clic en un vértice o una arista para eliminarlo. Con un vértice seleccionado, Supr lo elimina y Esc lo suelta. Haz clic en una propiedad para verla en el grafo. Ejemplo carga un grafo conocido, Grafo aleatorio crea uno, Ordenar separa los vértices y Complemento une exactamente los pares que no estaban unidos. Ctrl+Z deshace un paso.
Cómo funciona
- Haz clic en un espacio vacío para añadir un vértice. Haz clic en un vértice y luego en otro para unirlos; repítelo para quitar la arista. Arrastra un vértice para moverlo.
- Lee las propiedades bajo el grafo y haz clic en una para mostrarla: una coloración, los dos lados, un recorrido euleriano, un árbol generador, el ciclo más corto o el diámetro.
- Carga un ejemplo como el grafo de Petersen, crea un grafo aleatorio, toma el complemento o cambia el clic a Borra para eliminar vértices y aristas.
Qué significan las propiedades
El grado de un vértice es el número de aristas que llegan a él. Un grafo es conexo cuando desde cada vértice se puede llegar a todos los demás siguiendo las aristas, y es un árbol cuando es conexo y no tiene ciclos. Es bipartito cuando sus vértices se dividen en dos lados y todas las aristas van de un lado al otro, lo que ocurre exactamente cuando no tiene ciclos de longitud impar. El número cromático es la menor cantidad de colores con la que los vecinos reciben colores distintos. La longitud del ciclo más corto se llama cintura, y el diámetro es la mayor distancia entre dos vértices, contada en aristas.
Dibujar de un solo trazo
Un recorrido euleriano usa cada arista exactamente una vez. En 1736, con los siete puentes de Königsberg, Leonhard Euler vio cuál es el obstáculo: cada vez que un recorrido pasa por un vértice, usa dos de sus aristas. Así que, o bien todos los grados son pares, y el recorrido puede terminar donde empezó, o bien exactamente dos grados son impares, y el recorrido tiene que ir de uno de esos vértices al otro. Más tarde Carl Hierholzer demostró que esto, junto con que todas las aristas estén en una sola parte, también es suficiente. Carga el ejemplo de la casa y descubre dónde tiene que empezar el trazo.
Preguntas frecuentes
¿Qué es un grafo en teoría de grafos?
Un conjunto de puntos, llamados vértices o nodos, y líneas entre algunos pares de ellos, llamadas aristas. No es la gráfica de una función: solo describe qué está unido con qué. Los mapas de carreteras, las redes sociales, las moléculas y las redes de ordenadores son grafos.
¿Cómo se calcula el número cromático?
El laboratorio intenta colorear el grafo con un color, luego con dos, luego con tres, y así sucesivamente, y para cada número explora todas las posibilidades que importan, coloreando siempre a continuación el vértice cuyos vecinos ya usan más colores. El primer número que funciona es el número cromático. Con los grafos que puedes dibujar aquí eso tarda como mucho un momento; en un grafo muy difícil la búsqueda se detiene antes y el valor se muestra como cota superior.
¿Cuándo tiene un grafo un camino euleriano?
Cuando todas sus aristas están en una sola parte y como mucho dos vértices tienen grado impar. Si no hay vértices impares, hay un circuito euleriano que termina donde empieza; si hay dos, todo camino euleriano empieza en uno de ellos y termina en el otro. El número de vértices impares siempre es par, así que nunca es exactamente uno.
¿Qué es el complemento de un grafo?
Es el grafo con los mismos vértices cuyas aristas son exactamente los pares que antes no estaban unidos. El complemento del complemento es el grafo del que partiste. El complemento del grafo de Petersen, por ejemplo, es 6-regular, porque cada vértice estaba unido a 3 de los otros 9.
¿Por qué es famoso el grafo de Petersen?
Es un grafo pequeño, con 10 vértices y 15 aristas, que sirve de contraejemplo a muchas conjeturas optimistas. Todos sus vértices tienen grado 3, su ciclo más corto tiene longitud 5, dos vértices cualesquiera están como mucho a 2 aristas de distancia y no se puede dibujar sin que se crucen aristas. El laboratorio empieza con él.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor