Esta página muestra algunos ejercicios corregidos de modelado de gráficos y árboles. El propósito de estos ejercicios es aprender a modelar un problema usando los conceptos y conceptos básicos de Teoría de grafos.
Ejercicio 1
Dos jugadores tienen 2 o más conjuntos de partidos. Cada turno, el siguiente jugador puede eliminar un cierto número de coincidencias de un lote (dependiendo de la regla elegida). El jugador que quita el último partido pierde.
Modele este juego con un gráfico en el caso de que haya dos pilas, cada una de las cuales contiene tres fósforos, y donde un jugador puede quitar uno o dos fósforos cada uno.
¿Qué movimiento debe hacer el primer jugador para ganar el juego?
Solución
Los bordes están orientados de izquierda a derecha. Si estamos en posición o ganamos. Así, la posición comprobará que, sea cual sea la jugada de tu adversario, puedes alcanzar o
Ejercicio 2
El siguiente gráfico muestra los pasillos de un museo. Un vigilante situado en un pasillo puede vigilar dos cruces situados en sus extremos. ¿Cuántos guardias se necesitan (y cómo deben colocarse) para que todas las intersecciones estén vigiladas?
Si ahora colocamos guardias en las intersecciones, suponiendo que un guardia pueda monitorear todos los pasillos que conducen a esa intersección, ¿cuántos guardias se necesitan?
Solución
Cada guardia se colocará en un borde y podrá monitorear dos intersecciones (vértices). El gráfico tiene 11 vértices; Se necesitarán al menos seis guardias. Por lo tanto, es necesario encontrar un conjunto (mínimo) de al menos seis aristas, tal que cada vértice incida en al menos una de estas aristas. El siguiente gráfico proporciona una solución (bordes más gruesos).
Esta vez, los guardias están en las cimas y observan las crestas. Debe haber un conjunto de vértices tal que cada arista incida en al menos uno de estos vértices. El siguiente gráfico proporciona una solución utilizando 6 vértices (vértices blancos).
Ejercicio 3
Skynet es una red de 15 vértices. Puede pasar de cada vértice a al menos otros siete vértices por enlace. ¿Podemos ir por enlace desde un vértice X a cada uno de los otros?
Solución
Sea A cualquier vértice. X está vinculado a al menos 7 ciudades diferentes. Entonces tenemos una red de 8 vértices conectados por enlaces. Dentro de un vértice, también puede conectarse con al menos otros siete vértices; entonces hay una nueva red de 8 vértices. Debe haber un vértice compartido en estas redes, de lo contrario la red tendría al menos 16 vértices. X está conectado a A en dos planos como máximo, por este vértice común; está conectado con todas las demás ciudades.
Ejercicio 4
Una red está formada por siete fábricas. Una ciudad está vinculada a exactamente dos plantas. Dos fábricas comparten exactamente una ciudad. ¿Cuántas ciudades son servidas por la red? Demostrar que un grafo completo con vértices tiene n(n-1)/2 enlaces.
Solución
Las fábricas son los vértices y las ciudades están representadas por una arista que conecta dos vértices. La regla 2 implica que no hay aristas múltiples y que cualquier par de vértices son adyacentes; es decir, el gráfico está completo; es K7, o 21 enlaces.
Ejercicio 5
Considerando el siguiente sistema matemático:
Donde X es 0 o 1. Determinar, con un problema gráfico, una solución que maximice la función objetivo (suma de las X).
Solución
Un vértice representa una variable. Dos vértices están conectados si están en la misma desigualdad. El problema es encontrar un conjunto máximo de vértices donde ningún par de vértices tenga un enlace directo.
Modelado con árbol
Ejercicio 6
Considere un gráfico no dirigido con vértices. Demostrar que todas las siguientes propiedades son equivalentes:
- es un árbol
- es conexo y si quitamos una arista, el grafo ya no es conexo
- está conectado con n-1 aristas
- no tiene ciclo hasta que agregamos un borde
- no tiene ciclo con borde n-1
- un solo camino entre cualquier par de vértices
Ejercicio 7
Queremos agregar una granja en una red. El siguiente gráfico muestra el costo de enviar energía entre dos subestaciones de la red y la cantidad de energía enviada por una subestación. Debe colocar la batería en una subestación mientras minimiza el costo total.
Solución
Calcule la suma de todos los costos en cada subestación, es decir, el costo de cada ruta entre cualquier subestación y la subestación elegida (borde * vértice).
ES 
FR 
EN 
RU