Matemáticas HL AI Evaluación interna:

Análisis gráfico de las opciones universitarias

Tema: Diagramas de Voronoi y teoría de grafos

Índice
Introducción:...............................................................................................................................2
Justificación:...............................................................................................................................2
Objetivo:......................................................................................................................................2
Exploración:................................................................................................................................3
Resolver el problema del viajante de comercio..........................................................................9
Conclusión y evaluación:..........................................................................................................19
Bibliografía...............................................................................................................................20
Introducción:

Justificación:

Como estudiante del último curso del diploma del BI, la emoción y el terror de solicitar plaza

en la universidad es una presión constante que se cierne sobre mi cabeza. Hay varios factores

que influyen, como el deseo de dar lo mejor de ti mismo en el IB para alcanzar ciertas notas

exigidas o la redacción de una declaración personal. Sin embargo, el primer obstáculo es

decidir dónde quiere presentar su solicitud. Por supuesto, esto depende de muchas variables,

como el nivel académico de cada uno y sus objetivos profesionales. Para mí, la ubicación es

un factor importante. Como mi familia seguirá viviendo en el extranjero cuando me traslade

al Reino Unido, será beneficioso tener muchos aeropuertos cerca para poder visitarlos con

frecuencia o viceversa. Además, antes de elegir dónde quiero estudiar, es importante que me

haga una idea de cada zona y campus, por lo que debo visitar todos los campus universitarios.

Como estudiante con un presupuesto limitado, deseo encontrar la forma más barata posible de

visitar cada uno de estos campus.

Objetivo:

El objetivo de esta investigación es determinar la universidad óptima en función del número

de aeropuertos más cercanos a cada una de las 9 universidades preseleccionadas utilizando un

diagrama de Voronoi. Además, para hacerme una idea de la cantidad de dinero que necesitaría

para visitar cada campus una vez en una visita guiada, esta investigación también aproxima la

solución al problema del viajante de comercio utilizando un gráfico ponderado que muestra el

precio de las rutas directas en tren a cada universidad. Aunque se puede determinar un rango

de valores encontrando un límite inferior y un límite inferior para el ciclo hamiltoniano de

menor peso, hay que establecer que debido a la naturaleza del problema del viajante de
comercio, al ser NP-duro (lo que significa que no tiene un algoritmo eficiente), cualquier

solución para el problema del viajante de comercio es sólo aproximada.

Exploración:

Construcción del diagrama de Voronoi:1

Para construir un diagrama de Voronoi, primero superpuse un mapa de Inglaterra sobre una
cuadrícula cuadriculada utilizando GeoGebra. La Figura 1 tiene una escala de 50 km por 2
unidades y muestra las 9 universidades preseleccionadas como diferentes emplazamientos {N,
D, Lo, M, L, 0, W, LS, E ] con sus coordenadas registradas en la Tabla 1.

Figura 1: Mapa de universidades potenciales

1
Los recuadros azul claro con ribete rojo se utilizan para ocultar información personal y no tienen
relevancia matemática.
Cuadro 1: Coordenadas de las Universidades
Nombre del emplazamiento Coordenadas del emplazamiento
N (12.0, 19.9)
D (12.1, 18.8)
L (12.2,14.5)
M (10.4,13.0)
Lo (13.0,9.9)
0 (12.1,8.2)
W (12.9,5.6)
LS (15.9,4.6)
E (6.9,1.3)

Como todos los puntos de una bisectriz perpendicular son equidistantes a los lugares que

bisecan, las bisectrices perpendiculares son útiles en la construcción de Diagramas de

Voronoi. Por lo tanto, se deben encontrar las bisectrices perpendiculares entre cada sitio, éstas

actuarán como los bordes para el Diagrama de Voronoi.

En primer lugar, se construyó el borde entre los sitios N(12,0,19,9) y D(12,1,18,8). Como el

bisectriz perpendicular pasa por el punto medio, eso es lo que hay que calcular primero.

Punto medio de [ND] = 8!!"!", $ !"$"9

12.0 + 12.1 19.9 + 18.8
2,2
= (12.05, 19.35)

La pendiente de la mediatriz entre dos puntos es igual al recíproco negativo de la pendiente

(m) de la recta que une dichos puntos.

m de ND]
!"%!!
=YY

18.8 - 19.9
=
12.1 - 12.0
 mof [ND] = -11

AGradiente de la mediatriz de [ND] = 1

La forma de la ecuación lineal es y = mx + c por lo que sustituimos los valores de

x e y desde el punto medio, y m para hallar c y, por tanto, la ecuación de la mediatriz.

y = mx + c
19.35 -11(12.05) + c
c = 19.35 12.05
11

c = 18.254
A y = x + 18.254
W
11
W
W
W
Esta forma lineal representa el borde entre los sitios N y D.
Este proceso se repite para todos los demás bordes entre sitios. Para hacer el proceso

más eficiente, creé una hoja de cálculo en Excel para encontrar los puntos medios y los

gradientes de las otras bisectrices perpendiculares. Para estos valores he optado por no

redondearlos para garantizar la precisión en el resto de mis cálculos.

Sitios X yi X2 Y2 m i Punto Punto c
-m medio medio y
X
DL 12.1 18.8 12.2 14.5 -43 0.02325581 12.15 16.65 16.3674419
LM 12.2 14.5 10.4 13 0.83333333 -1.2 11.3 13.75 27.31
MLo 10.4 13 13 9.9 -1.1923077 0.83870968 11.7 11.45 1.63709677
LoO 13 9.9 12.1 8.2 1.88888889 -0.5294118 12.55 9.05 15.6941176
OW 12.1 8.2 12.9 5.6 -3.25 0.30769231 12.5 6.9 3.05384615
WLS 12.9 5.6 15.9 4.6 -0.3333333 3 14.4 5.1 -38.1
LSE 15.9 4.6 6.9 1.3 0.36666667 -2.7272727 11.4 2.95 34.0409091
NL 12 19.9 12.2 14.5 -27 0.03703704 12.1 17.2 16.7518519
NM 12 19.9 10.4 13 4.3125 -0.2318841 11.2 16.45 19.0471014
NLo 12 19.9 13 9.9 -10 0.1 12.5 14.9 13.65
NO 12 19.9 12.1 8.2 -117 0.00854701 12.05 14.05 13.9470085
NW 12 19.9 12.9 5.6 -15.888889 0.06293706 12.45 12.75 11.9664336
NLS 12 19.9 15.9 4.6 -3.9230769 0.25490196 13.95 12.25 8.69411765
NE 12 19.9 6.9 1.3 3.64705882 -0.2741935 9.45 10.6 13.191129
DM 12.1 18.8 10.4 13 3.41176471 -0.2931034 11.25 15.9 19.1974138
DLo 12.1 18.8 13 9.9 -9.8888889 0.1011236 12.55 14.35 13.0808989
DO 12.1 18.8 12.1 8.2 Sin definir Sin definir 12.1 13.5 Sin definir
DW 12.1 18.8 12.9 5.6 -16.5 0.06060606 12.5 12.2 11.4424242
DLS 12.1 18.8 15.9 4.6 -3.7368421 0.26760563 14 11.7 7.95352113
DE 12.1 18.8 6.9 1.3 3.36538462 -0.2971429 9.5 10.05 12.8728571
LLo 12.2 14.5 13 9.9 -5.75 0.17391304 12.6 12.2 10.0086957
LO 12.2 14.5 12.1 8.2 63 -0.015873 12.15 11.35 11.5428571
LW 12.2 14.5 12.9 5.6 -12.714286 0.07865169 12.55 10.05 9.06292135
LLS 12.2 14.5 15.9 4.6 -2.6756757 0.37373737 14.05 9.55 4.2989899
LE 12.2 14.5 6.9 1.3 2.49056604 -0.4015152 9.55 7.9 11.7344697
MO 10.4 13 12.1 8.2 -2.8235294 0.35416667 11.25 10.6 6.615625
MW 10.4 13 12.9 5.6 -2.96 0.33783784 11.65 9.3 5.36418919
MLS 10.4 13 15.9 4.6 -1.5272727 0.6547619 13.15 8.8 0.18988095
ME 10.4 13 6.9 1.3 3.34285714 -0.2991453 8.65 7.15 9.73760684

LoW 13 9.9 12.9 5.6 43 -0.0232558 12.95 7.75 8.05116279

LoLS 13 9.9 15.9 4.6 -1.8275862 0.54716981 14.45 7.25 -0.6566038

LoE 13 9.9 6.9 1.3 1.40983607 -0.7093023 9.95 5.6 12.6575581

OLS 12.1 8.2 15.9 4.6 -0.9473684 1.05555556 14 6.4 -8.3777778

OE 12.1 8.2 6.9 1.3 1.32692308 -0.7536232 9.5 4.75 11.9094203

NOSOTROS 12.9 5.6 6.9 1.3 0.71666667 -1.3953488 9.9 3.45 17.2639535

Tabla 2: Hoja de cálculo para hallar bisectrices perpendiculares

Para la mediatriz de los sitios D y O, utilizando la fórmula: $"%$!!, existe un !"%!!

denominador de 0, lo que debe significar que la recta tiene pendiente indefinida y por tanto la

mediatriz entre estos sitios es horizontal.

Figura 2: Diagrama de Voronoi

Utilizando estos valores para X, y, c, m; he creado la Figura 3. Sin embargo, hay que
señalar que sólo un
sección de las bisectrices perpendiculares se incluyen como aristas en este diagrama de
Voronoi. Las aristas representan el lugar de los puntos de equidistancia entre dos sitios, pero se
detienen cuando un nuevo sitio se acerca más a la arista que los puntos que biseca. Análisis
del diagrama de Voronoi para determinar qué celda contiene más incentivos:
Como he explicado en la introducción, la ubicación de los aeropuertos es sumamente

importante para mi elección de universidad. Para determinar qué universidad tiene más
aeropuertos cerca, basta con añadir la ubicación de los aeropuertos a la cuadrícula. Cualquiera

que sea la celda en la que se encuentre el aeropuerto, será la más cercana a la universidad

correspondiente.

Figura 3: Diagrama de Voronoi con aeropuertos

Así pues, he trazado la ubicación de los principales aeropuertos de Inglaterra en el diagrama de

Voronoi ilustrado por los puntos rojos. La celda en la que se encuentra el punto representa la

universidad a la que debe estar más cerca el aeropuerto. Anoté cuántos puntos había en cada

celda, mediante inspección, y registré mis resultados en la tabla 3.

En el caso de cualquier aeropuerto situado en el borde entre dos celdas, los conté como en

ambas celdas debido a la equidistancia desde cualquier punto de un borde a cualquiera de los
dos sitios. Este era el caso del aeropuerto situado en el límite entre los emplazamientos E y W

Cuadro 3: Número de aeropuertos en cada casilla

Celda Número de aeropuertos
N 1
D 1
L 0
M 2
Lo 2
0 0
W 2
LS 4
E 3

A partir de estos resultados, podemos determinar que la celda LS contiene el mayor número de

aeropuertos y, por tanto, el emplazamiento LS es el más cercano al mayor número de

aeropuertos. Sin embargo, esta conclusión puede ser errónea, ya que el diagrama sólo tiene en

cuenta la distancia desde las coordenadas y no considera el tamaño de los aeropuertos, la

disponibilidad de transporte a los mismos y si el aeropuerto acoge vuelos internacionales.

Resolver el problema del viajante de comercio

Para seguir determinando qué universidad me conviene más, es necesario visitar el campus de

cada una de ellas. Sin embargo, como tendré un presupuesto de estudiante ajustado, encontrar

el ciclo hamiltoniano de menor peso que empiece y termine en LS (el lugar con el mayor

número de aeropuertos más cercanos) es importante. Para ello, se aproximará una solución al

problema práctico del viajante de comercio (TSP). Para descubrir la mejor ruta para viajar, he

creado un gráfico ponderado que muestra los costes (en £) de los trenes directos desde las

estaciones de tren más cercanas a las universidades. En este caso, el coste de los trenes

representa el peso de las aristas, y las distintas estaciones de tren representan los vértices. Hay

que señalar que los vértices de este gráfico no representan la ubicación geográfica de las

estaciones de tren.
Figura 4: Gráfico ponderado de trenes directos

Para simplificarlo, he utilizado el peso de las aristas entre cada vértice para construir una tabla

de adyacencia ponderada.

Tabla 4: Tabla de adyacencia ponderada

Vértice E B O LS W LO M L D N
E 0 16.50 - 40.30 - - - 166.50 205.20 206.80
B 16.50 0 - 33.20 - - - - - -
O - - 0 10.40 - - 74.50 - - -
LS 40.30 33.20 10.40 0 16.00 66.50 49.20 46.00 50.50 59.00
W - - - 16.00 0 - - - - -
LO - - - 66.50 - 0 - - - -
M - - 74.50 49.20 - - 0 17.70 39.40 39.40
L 166.5 - - 46.00 - - 17.70 0 20.90 25.00
D 205.2 - - 50.50 - - 39.40 20.90 0 3.50
N 206.80 - - 59.00 - - 39.40 25.00 3.50 0

El símbolo "-" indica que no hay rutas ferroviarias directas entre estas estaciones. Para resolver

el TSP clásico, debemos encontrar un ciclo hamiltoniano (un circuito que visita cada vértice
exactamente una vez antes de volver al vértice inicial) de menor peso para un grafo completo

ponderado dado. Un grafo completo es un grafo simple no dirigido en el que cada vértice está

conectado por una arista a cualquier otro vértice. Como indica la Tabla 3, varios vértices no

están conectados por una sola arista con todos los demás vértices (por ejemplo, el vértice W

sólo está conectado directamente con el vértice LS) y, por tanto, la figura 4 no es un grafo

completo. Por lo tanto, el TSP clásico no puede resolverse y, en su lugar, debe resolverse el

TSP práctico.

Para resolver el TSP práctico para un grafo ponderado dado, se debe encontrar la ruta de menor

peso que empiece y termine en el mismo vértice y visite cada vértice al menos una vez. Para

conseguirlo, podemos convertir el TSP práctico en un TSP clásico añadiendo o sustituyendo

aristas para mostrar el camino de menor peso entre los vértices que no estaban conectados a

todos los demás vértices. Por ejemplo, la ruta de menor peso entre el vértice E y el vértice O

pasa por el vértice LS.

E → LS → O = 40,30 + 10,40. Por lo tanto, el peso de la arista añadida entre el vértice E y el

vértice O es 50,70. Este proceso de añadir una nueva arista que conecte cada vértice con todos

los demás permitió crear el grafo ponderado completo que se muestra en la figura 5, y su

correspondiente tabla de adyacencia

Figura 5: Gráfico ponderado completo

Tabla 5: Tabla de adyacencia ponderada para el grafo completo

Vértice E B O LS W LO M L D N
E 0 16.50 50.70 40.30 57.30 106.80 89.50 166.50 205.20 206.80
B 16.50 0 43.60 33.20 49.20 99.70 82.40 79.20 83.70 92.20
O 50.70 43.60 0 10.40 26.40 76.90 74.50 56.40 60.90 69.40
LS 40.30 33.20 10.40 0 16.00 66.50 49.20 46.00 50.50 59.00
W 57.30 49.20 26.40 16.00 0 82.50 65.20 62.00 66.50 75.00
LO 106.80 99.70 76.90 66.50 82.50 0 115.70 112.50 117.00 125.00
M 89.50 82.40 74.50 49.20 65.20 115.70 0 17.70 39.40 39.40
L 166.5 79.20 56.40 46.00 62.00 112.50 17.70 0 20.90 25.00
D 205.2 83.70 60.90 50.50 66.50 117.00 39.40 20.90 0 3.50
N 206.80 92.20 69.40 59.00 75.00 125.00 39.40 25.00 3.50 0

Ahora que hemos convertido el grafo en un grafo completo, podemos encontrar una

aproximación para el TSP clásico. Para un grafo más pequeño con un menor número de

vértices, puede ser práctico encontrar todos los posibles ciclos hamiltonianos por inspección
del grafo y determinar el ciclo de menor peso, sin embargo como este grafo tiene muchos

vértices de alto orden, este método es poco práctico y por lo tanto se encontrará una estimación

del peso mínimo del ciclo hamiltoniano. Para ello, debemos encontrar un límite superior y un

límite inferior para el peso del ciclo hamiltoniano. Para encontrar un límite superior, se puede

utilizar el algoritmo del vecino más próximo. Este algoritmo consta de 4 pasos:

• Paso 1: Elegir un vértice inicial (a efectos de nuestro gráfico, el vértice inicial será LS).

• Paso 2: Seguir la arista de menor peso hasta un vértice no visitado.

• Paso 3: Repetir el paso 2 hasta que se hayan visitado todos los vértices.

• Paso 4: Volver al vértice inicial añadiendo la arista correspondiente.

Utilizando la tabla 5, podemos seguir este algoritmo creando otra tabla (tabla 6) que muestre

las aristas de menor peso, su peso y si se ha formado un ciclo. Si se ha formado un ciclo, como

en el caso de la arista OLS, el peso de esta arista se ignora y en su lugar se encuentra la arista

de segundo menor peso. Para el resto de la tabla, las aristas de menor peso que daban lugar a un

ciclo se ignoraban hasta que cada vértice había sido visitado una vez.

Tabla 6: Algoritmo del vecino más próximo

Arista de menor Peso Vértice ¿Existe un ciclo?
peso
N/A N/A LS N/A
LSO 10.40 O No
OLS 10.40 LS Sí, así que ignora
y encuentra la
arista de segundo
menor peso.2
OW 26.40 W No
OB 49.20 B No
BE 16.50 E No
2
Esta misma suposición se hizo para todas las demás aristas que formarían un ciclo, pero no se muestran.
EM 89.50 M No
ML 17.70 L No
LD 20.90 D No
DN 3.50 N No
NLO 125.00 LO No
NLS 59.00 LS Sí (ciclo
completo)

Este ciclo hamiltoniano puede escribirse así:

LS → O → W→ B → E → M → L → D → N → LO → LS

Sin embargo, como algunos de estos bordes no son directos, ésta no es la solución real. En

cambio, tenemos que incluir todas las rutas de tren que pasan por el vértice LS.

LS → O → LS →W → LS → B → E → LS → M → L → D → N → LS → LO → LS.
Sea m el peso mínimo (¿del grafo? Marque una nota) (reescriba)

m < 10.40 + 26.40 + 49.20 + 16.50 + 89.50 + 17.70 + 20.90 + 3.50 + 125.00 + 59.00

m < £418.10
Ahora que tenemos nuestro límite superior para m, debemos utilizar el algoritmo de vértices

eliminados para encontrar un límite inferior para m.

• Paso 1: Eliminar un vértice, y las aristas conectadas a él, del grafo original.

• Paso 2: Encontrar el árbol de mínima expansión (MST) para el grafo restante.

• Paso 3: Añadir la longitud de las dos aristas más cortas eliminadas al peso del árbol de
expansión mínimo.

La siguiente tabla es el aspecto de la tabla 5 una vez eliminado el vértice L de la tabla.

Tabla 7: Tabla de adyacencia ponderada con el vértice L eliminado

Vértice E B O LS W LO M D N
E 0 16.50 50.70 40.30 57.30 106.80 89.50 205.20 206.80
B 16.50 0 43.60 33.20 49.20 99.70 82.40 83.70 92.20
O 50.70 43.60 0 10.40 26.40 76.90 74.50 60.90 69.40
LS 40.30 33.20 10.40 0 16.00 66.50 49.20 50.50 59.00
W 57.30 49.20 26.40 16.00 0 82.50 65.20 66.50 75.00
LO 106.80 99.70 76.90 66.50 82.50 0 115.70 117.00 125.00
M 89.50 82.40 74.50 49.20 65.20 115.70 0 39.40 39.40
D 205.2 83.70 60.90 50.50 66.50 117.00 39.40 0 3.50
N 206.80 92.20 69.40 59.00 75.00 125.00 39.40 3.50 0

Las aristas más cortas desde el vértice L eliminado eran LM y LD, con pesos de 17,70 y 20,90

libras respectivamente. Estos son los pesos que se añadirán al peso del árbol de expansión

mínimo.

Con el vértice L eliminado, ahora podemos encontrar el árbol de expansión mínimo utilizando

el algoritmo de Prim. El algoritmo de Prim puede utilizarse mediante dos métodos diferentes.

En el primer método, las aristas más cercanas a cada vértice se eligen mediante inspección del

grafo. Sin embargo, debido a que los vértices en el gráfico (ilustrado incluyendo el Vértice L en

la figura 4), todos tienen un orden de 9, creo que era demasiado complejo utilizar la inspección

y por lo tanto se debe utilizar un método diferente. En este método, el algoritmo de Prim se

aplica a una tabla de adyacencia ponderada siguiendo estos pasos:

• Paso 1: Seleccionar cualquier vértice al azar.

• Paso 2: Borrar la fila del vértice elegido

• Paso 3: Numerar la columna del vértice elegido

• Paso 4: Rodee con un círculo la entrada no eliminada más baja de cualquiera de las
columnas numeradas. Si hay más de una opción posible, elige una al azar. La fila de la
entrada marcada con un círculo decide el nuevo vértice elegido.

• Paso 5: Repite los pasos 2-4 hasta eliminar todas las filas. Las entradas marcadas con
un círculo darán las aristas del árbol de expansión mínimo.

Trabajando:

Vértice E B O LS W LO M D N
4 .50
A 16 uno sobre
en en
206,80
•______ 2 SO 70 Un 70 57 70 1 4 en o0SO
B 16.50 0 43.60 33.20 49.20 99.70 82.40 83.70 92.20
O 50.70 43.60 0 10 40 26.40 76.90 74.50 60.90 69.40
9a en CQ f|f|
T C____ Un sobre 33.20 1 0 40 0 1 A 00 AA SO 40 en SO so 59.00
09 54
82.50
W 57 en 4920 2640 1600 0 6520 6650 7500
LO 106.80 99.70 76.90 66.50 82.50 0 115.70 117.00 125.00
89.50
_____ en es en An 74 SO
82.40 49.20 AS en 1 1 S 70 n el 40 7Q j n
65.20 115.70 0
D 205.2 83.70 60.90 50.50 66.50 117.00 39.40 0 3.50
NT n om Un nm ZM Am Em An me An i ne An om Am fl Ah en
N 206.80 92.20 69.40 59.00 75.00 125.00 39.40 3.50 0
5 4 2 1 3 9 6 7 8
El árbol de expansión mínimo tiene peso = 10,40 + 16,00 + 33,20 + 16,50 + 49,20 +
39.40 + 3.50 + 66.50 = £234.70
Ahora que se ha encontrado el MST, la longitud de dos aristas eliminadas más cortas debe
sumarse a £234,70 para completar el algoritmo de vértices eliminados. Estos bordes eran los
ya mencionados LM y LD, que tienen un peso combinado de 38,50 libras. Esta respuesta al
algoritmo de vértices eliminados es igual al límite inferior del peso mínimo para resolver el
TSP.

234,70£ + 38,50£ = 273,20£ m > 273,20£

A £273,20 <m< £418,10
Sin embargo...

(MÁS COSAS QUE HACER:

EVALUACIÓN DE LA MISMA: Implicaciones de los órdenes de las vértices tal vez;

implicaciones de lo que estoy descubriendo (un par de frases)

Reflejo: no representa necesariamente lo fácil que es llegar a los lugares, ya que sólo

muestra los trenes directos. Además, los precios fluctúan y ese no será siempre el precio

mínimo.

Los aeropuertos no se construyen igual: los aeropuertos de Exeter pueden no volar igual

que un aeropuerto de

Londres (sin embargo no afecta a la conclusión)

ALGORITMO DE PRIM
En el algoritmo de Prim, elegimos las aristas de una en una, conectando en cada etapa un vértice adicional al árbol
hasta que todos los vértices estén conectados.

Paso 1: Empieza con un vértice cualquiera.

Paso 2: Une este vértice al vértice más cercano. Si dos o más vértices forman un arco a la misma distancia, elige
uno al azar.
Paso 3: Unir el vértice más cercano a cualquiera de los ya conectados.
Paso 4: Continúa uniendo los vértices conectados con el vértice no conectado más cercano hasta que todos los
vértices estén conectados.

Ejemplo 4 mnemummemammmmeu - Auto Tutor

 Paso I: Seleccionar cualquier vértice al azar, digamos
el vértice E.
Paso 2: Borrar la fila del vértice elegido.
Paso 3: Numerar la columna del vértice elegido.
Paso 4: Rodee con un círculo la entrada no eliminada
más baja de cualquiera de las columnas
numeradas. Si hay más de una opción
posible, elige una al azar.
La fila de la entrada encerrada en un círculo
nos da el nuevo vértice elegido.
Paso 5: Repita los pasos 2 a 4 hasta eliminar todas las filas.
Los círculos indican las aristas del árbol
mínimo.

¿Por qué estoy usando el TSP, qué método. (por inspección podemos decir que este camino

no es

Hamiltoniano)

Nuestro grafo no es completo y no es euclediano (explique por qué con un ejemplo) por lo

que debe utilizar TSPxs prácticos

Debemos convertir lo práctico en clásico

Convertir en tabla y luego en matriz de adyacencia

Pasar de la práctica a la TSP clásica.
A continuación, utilice el método clásico TSP para encontrar los límites superior e inferior

Gráfico:

http://graphonline.ru/en/?graph=NzBEdFqPOhtzPBGn

Conclusión y evaluación:

En conclusión

Esta investigación fue beneficiosa para mí fuera de las matemáticas. Mientras investigaba las

ubicaciones de las universidades, acabé descubriendo ciertas características dentro de las

celdas de las universidades que no sabía que existían.

Sin embargo, esta investigación tenía algunas limitaciones. En primer lugar, debido a la gran

escala del mapa, era casi imposible que la ubicación de los lugares fuera exacta al 100%, por

lo que habrá un error con cálculos como el radio. Por lo tanto, he optado por redondear el

radio al kilómetro más próximo, ya que me resultaba imposible conocer la respuesta con un

mayor nivel de precisión.

Bibliografía

www.geogebra.com. Fecha de consulta: 5 de septiembre de 2021.

https://mpra.ub.uni-muenchen.de/53026/1/MPRA_paper_53026.pdf. Fecha de consulta: 6

de septiembre de 2021.

http://graphonline.ru/en/?graph=gwVmUZRnolTiamri
21