Imagen sacada de la red
Teoría de Grafos
En matemáticas y en ciencias de la computación, la Teoría de Grafos (también llamada Teoría de Gráficas) estudia las propiedades de los grafos. Un grafo está formado por un conjunto no vacío, de objetos llamados vértices, y una selección de pares no orientados de vértices llamados aristas. También se puede considerar pares de vértices orientados, formando así los grafos dirigidos. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas). [b]NOTA: Las respuestas de las preguntas de cada una de las actividades podrán ser consultadas en https://ggbm.at/wevejqtz[/b]
Table of Contents
- Partes de un grafo
- Grafos
- Grafos Duales
- Grafo Dual
- Grafos Completos
- Grafos Completos de n vértices
- Grafos Eulerianos
- Problema del puente de Königsberg
- Grafos Hamiltonianos
- Ajedrez
- Teorema de los cuatro colores
- El teorema de los cuatro colores
Grafos
Partes de un grafo.
Un grafo G=(V,E) consiste en un conjunto V de objetos llamados vértices, puntos o nodos, y un conjunto E de líneas o aristas, que se relacionan entre si de tal manera que a cada línea se le asocia un par de vértices.
Ejemplos de grafos.
Selecciona la respuesta correcta.
¿Cuántas aristas tiene el grafo 1?
¿Cuántos vértices tiene el grafo 3?
La cantidad de vértices que tiene el grafo 2 es:
Grafo Dual
Un grafo dual G* se obtiene de un grafo plano G, es decir, un grafo dibujado en el plano sin que ninguna de sus aristas se crucen.[br]El grafo dual tiene un vértice por cada región de G y una arista por cada arista en el grafo plano, con lo que se unen dos regiones.[br]Una región conexa es el espacio delimitado por un conjunto de aristas.
Grafo planar y grafo dual.
Con ayuda de las herramientas, obtén los grafos duales.
Responde las siguientes preguntas, en las preguntas abiertas ingresa solo el número correspondiente.
¿Qué grafos tienen asociado un grafo dual? (Ingresa los números correspondientes, juntos separados por comas).
¿Todos los grafos tienen grafo dual?
¿Cuántos vértices tiene G* de la figura 1?
¿Cuántos vértices debe tener G* de la figura 5?
¿Cuántas aristas debe tener G* de la figura 4?
¿Qué grafos no son planos? (Ingresa los números correspondientes, juntos separados por comas).
Grafos Completos de n vértices
Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices debe tener una arista que los une.[br]El grafo completo de [math]n[/math] vértices se denota [img]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABoAAAAOCAYAAAAxDQxDAAABYElEQVQ4T8XUzStEURzG8Rli4a1IKSmFslJiYSGKvdfYKi8LaxtiYcpSEZbISxL/gIWNbCQhoUgiKVFWNqzwfep3dZrO7Y7SuPXp3Hvur/OclzsTj6XpiqcpJ+YLyiJ8DBO4xBoWbEJNtLvYxzhOU51o2IryGOANpXh2BuuwwR9TDQjqwoLaKZhBlRUW03ZiAx+/DVF9WJBCCjCEFlRiyROQSV837qBtbkAhDvHi1ocFae/nkY0ERrDlCeqhbwdXmLLJlNNuojEqKDifSQpnLUSzrvUE1dN3jwuU4cvqNMnmqCCdzzSqrbCI9gmtOPCEddHXhgF7p9WXYDQqSOeTg2GncJX7XPR6guboO8G6vTui7cMnboJ63xmd81JbtuIMqm3YQwUeksLOeNZnr/586EOowSAWfUFabh305VzjGLfIgLZFZ/COZbw6YQnuJbj6udFqtvHzU/jXv6Cknfmbx2+KjD8PE7zZqgAAAABJRU5ErkJggg==[/img].[br]Un [img]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABoAAAAOCAYAAAAxDQxDAAABYElEQVQ4T8XUzStEURzG8Rli4a1IKSmFslJiYSGKvdfYKi8LaxtiYcpSEZbISxL/gIWNbCQhoUgiKVFWNqzwfep3dZrO7Y7SuPXp3Hvur/OclzsTj6XpiqcpJ+YLyiJ8DBO4xBoWbEJNtLvYxzhOU51o2IryGOANpXh2BuuwwR9TDQjqwoLaKZhBlRUW03ZiAx+/DVF9WJBCCjCEFlRiyROQSV837qBtbkAhDvHi1ocFae/nkY0ERrDlCeqhbwdXmLLJlNNuojEqKDifSQpnLUSzrvUE1dN3jwuU4cvqNMnmqCCdzzSqrbCI9gmtOPCEddHXhgF7p9WXYDQqSOeTg2GncJX7XPR6guboO8G6vTui7cMnboJ63xmd81JbtuIMqm3YQwUeksLOeNZnr/586EOowSAWfUFabh305VzjGLfIgLZFZ/COZbw6YQnuJbj6udFqtvHzU/jXv6Cknfmbx2+KjD8PE7zZqgAAAABJRU5ErkJggg==[/img] , es decir, grafo completo de [math]n[/math] vértices tiene exactamente [math]\frac{n\left(n-1\right)}{2}[/math] aristas..[br][br]INSTRUCCIONES:[br]Introduce el # de vértices que desees (del 1 al 30) y observa cómo son los grafos completos.
El grafo completo de 12 vértices contiene las escalas musicales. Los vértices corresponden a notas.
Problema del puente de Königsberg
En la ciudad de Königsberg, Prussia (1736), hoy Kaliningrado Rusia, el Río Pregel fluía a través de la ciudad dividiéndola en 4 regiones de tierra: 7 puentes atravesaban el río en diferentes ubicaciones. El siguiente mapa muestra el mapa de Königsberg donde las 4 regiones de tierra son A, B, C, D y los puentes son a, b, c, d, e, f y g.
Instrucciones
Dibuja en la siguiente imagen cómo resolverías el problema de los puentes de Königsberg.
Responde la siguiente pregunta:
¿Es posible caminar por Königsberg cruzando cada uno de sus siete puentes exactamente solo una vez?
El matemático suizo, Euler, determinó que los puntos intermedios de un recorrido posible necesariamente han de estar conectados a un número par de líneas. En efecto, si llegamos a un punto desde alguna línea, entonces el único modo de salir de ese punto es por una línea diferente. Esto significa que tanto el punto inicial como el final serían los únicos que podrían estar conectados con un número impar de líneas. Sin embargo, el requisito adicional del problema dice que el punto inicial debe ser igual al final, por lo que no podría existir ningún punto conectado con un número impar de líneas.[br]En particular, como en este diagrama los cuatro puntos poseen un número impar de líneas incidentes (tres de ellos inciden en tres líneas, y el restante incide en cinco), entonces se concluye que es imposible definir un camino con las características buscadas que son los 7 puentes de Königsberg.
Grafo asociado al problema de los puentes de Königsberg.
Ajedrez
[center][size=200]EL CABALLO[/size][/center]
[justify][size=100][size=150][/size][/size][/justify][size=150][justify]El juego de ajedrez es considerado un juego matemático. Por ejemplo, se le pueden asociar problemas relacionados con la Teoría de Grafos.[br]Uno de los primeros problemas de este tipo, se originó en el año de 840 aún antes de desarrollarse la Teoría de Grafos. El problema consiste en colocar a la pieza "caballo" en todo el tablero, haciendo los movimientos correspondientes.[br][br]Un caballo puede moverse dos casillas hacia adelante o hacia atrás (o bien hacia la izquierda o hacia la derecha), seguido de una casilla más hacia la izquierda o hacia la derecha (o bien hacia arriba o hacia abajo) en un movimiento de "L".[/justify][/size]
Movimiento del caballo.
[size=200][center]¿De qué forma podría moverse el caballo sobre todo el tablero?[br]Esto se resuelve con Teoría de Grafos.[/center][/size]
Se enumera el tablero, con cada uno de los movimientos del caballo por todo el tablero.
[center][/center][size=150][size=200][center]Representación de los movimientos del caballo por todo el tablero.[/center][/size][/size]
Ciclo "HAMILTONIANO" del movimiento de la pieza "caballo" por todo el tablero.
El teorema de los cuatro colores
El teorema de los cuatro colores consiste básicamente, en que cualquier mapa puede ser coloreado solamente con cuatro colores distintos de tal manera que dos regiones adyacentes (es decir, que tienen una frontera en común y no sólo un punto) no tengan el mismo color.
Instrucciones:
Colorea este mapa, de modo que no haya dos regiones adyacentes con el mismo color. Sólo puedes utilizar cuatro colores: [color=#1e84cc]azul[/color], [color=#38761d]verde[/color], [color=#ff0000]rojo[/color] y [color=#9900ff]púrpura.[/color][br][br]Haz clic en las regiones (cuadrilateros) para colorearlas. Para cambiar el color, haz clic de nuevo en la misma región.
Actividad realizada por [u]Juan Carlos Ponce Campuzano.[/u][br]Diseñado con ayuda de [url=https://www.geogebra.org/m/pGCXX3wW]Coloreando el mapa[/url], hecho por [url=https://www.geogebra.org/ilarrosa]Ignacio Larrosa Cañestro[/url].