Ejercicios corregidos: modelado en grafos y árboles

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.

modelado de grafos y árboles

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

Ejercicios corregidos sobre árboles y modelado de teoría de grafos.

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?

Ejercicios corregidos sobre árboles y modelado de teoría de grafos.

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).

Ejercicios corregidos sobre árboles y modelado de teoría de grafos.

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:

Ejercicios corregidos sobre árboles y modelado de teoría de grafos.

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.

Ejercicios corregidos sobre árboles y modelado de teoría de grafos.

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.

Ejercicios corregidos sobre árboles y modelado de teoría de grafos.

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).

Ejercicios corregidos sobre árboles y modelado de teoría de grafos.

Compartir, repartir
es_ESES