14.4: Ejemplos importantes

Ejemplo\(\PageIndex{1}\): A power set graph.

Podemos usar una gráfica para visualizar el conjunto de potencias de un conjunto finito\(A\text{:}\)\((\mathscr{P}(A),E)\) siendo la gráfica dirigida donde, para vértices\(B,C \in \mathscr{P}(A)\) (es decir, subconjuntos\(B,C \subseteq A\)), el par ordenado\((B,C)\) es un borde en\(E\) si se cumplen las dos condiciones siguientes:

\(B \subsetneqq C\text{;}\)y

no existe un subconjunto\(D \subseteq A\) tal que\(B \subsetneqq D \subsetneqq C\text{.}\)

Nota: La segunda condición es evitar abarrotar la gráfica con bordes adicionales que no agreguen ninguna información adicional.

Por ejemplo, considere\(A = \{a,b,c\}\) y

\ begin {ecuación*}\ mathscr {P} (A) =\ izquierda\ {\,\ emptyset,\,\ {a\},\,\ {b\},\,\ {c\},\,\ {a, b\},\,\ {a, c\},\,\ {b, c\},\,\ {a, b, c\}\,\ derecho\}. \ end {equation*}
Así podemos dibujar una gráfica para representar las relaciones de subconjunto de\(\mathscr{P}(A)\text{,}\) con flechas para apuntar de subconjunto a superconjunto.

Figura\(\PageIndex{1}\): Gráfica dirigida para representar las relaciones de subconjunto entre elementos de\(\mathscr{P}(A)\text{.}\)

Es algo natural dibujar la gráfica con los subconjuntos más grandes de\(A\) en la parte superior (o en la parte inferior). Si decidimos que las flechas siempre apuntarán hacia arriba, podemos desordenar nuestra gráfica simplemente dibujando líneas en lugar de flechas para bordes.

Podemos usar gráficas para visualizar otro tipo de relaciones matemáticas.

Ejemplo\(\PageIndex{2}\): A division graph.

Para enteros\(m,n\text{,}\) escribir\(m \mid n\) si\(m\) divide es\(n\text{;}\) decir, si\(n/m\) es también un entero. En este caso, decimos que\(m\) divide\(n\text{.}\)

Set

\ begin {ecuación*} V =\ {2,3,4,5,6,7,8,9,10,11,12,13,14\}\ texto {.} \ end {equation*}
Dejar\(G = (V,E)\) ser la gráfica dirigida donde, para enteros\(m,n \in V\) con\(m \lt n\text{,}\) el par ordenado\((m,n)\) es un borde en\(E\) si se cumplen las dos condiciones siguientes:

\(m \mid n\text{;}\)

no existe un entero\(\mathscr{P} \in V\) tal que\(m \mid \mathscr{P}\) y\(\mathscr{P} \mid n\text{,}\) pero\(\mathscr{P} \ne m,n\text{.}\)

Podemos utilizar esta gráfica dirigida para visualizar el conjunto\(V\) con respecto a la relación divide. Nuevamente, coincidimos en que las flechas siempre apuntarán hacia arriba, pero en realidad no las dibujan. Tenga en cuenta que todos los números primos aparecen en la parte inferior.

Figura\(\PageIndex{2}\): Gráfica dirigida para representar la relación de división entre elementos de\(V\text{.}\)

Ejemplo\(\PageIndex{3}\): Travelling salesman problem.

Obtienes un trabajo de verano en la Oficina de Estudiantes Prospectos en el Campus Augustana de la Universidad de Alberta en Camrose, Alberta. En mayo y junio, tu trabajo es visitar las escuelas secundarias de Alberta y reunirte con estudiantes que están pensando en postularse a Augustana. A continuación se muestra un mapa de las ciudades y pueblos que debes visitar, dado como una gráfica ponderada con distancias en kilómetros como pesos. Para ahorrar en gasolina, te gustaría visitar cada ciudad y pueblo exactamente una vez, y hacerlo mientras recorres la distancia más corta posible.

Figura\(\PageIndex{3}\): Mapa de ruta de los principales centros de Alberta como gráfica ponderada.

Este es un problema difícil, y se vuelve más difícil a medida que aumenta el número de ciudades y carreteras.