Grafos y matrices de adyacencia
Enviado por pepe_1989 • 4 de Julio de 2024 • Trabajo • 374 Palabras (2 Páginas) • 61 Visitas
Para resolver este problema, vamos a representar los vuelos entre los aeropuertos en forma de matrices de adyacencia. Las matrices de adyacencia indicarán las conexiones directas entre los aeropuertos de una ciudad a otra.
Definición de las matrices de adyacencia:
Matriz
𝑀
𝐴
𝐵
M
AB
: Representa los vuelos de A a B.
Filas: Aeropuertos en A (
𝐴
1
,
𝐴
2
,
𝐴
3
A1,A2,A3)
Columnas: Aeropuertos en B (
𝐵
1
,
𝐵
2
,
𝐵
3
,
𝐵
4
B1,B2,B3,B4)
Matriz
𝑀
𝐵
𝐶
M
BC
: Representa los vuelos de B a C.
Filas: Aeropuertos en B (
𝐵
1
,
𝐵
2
,
𝐵
3
,
𝐵
4
B1,B2,B3,B4)
Columnas: Aeropuertos en C (
𝐶
1
,
𝐶
2
C1,C2)
Llenado de las matrices de adyacencia:
Supongamos que las matrices de adyacencia
𝑀
𝐴
𝐵
M
AB
y
𝑀
𝐵
𝐶
M
BC
están definidas de la siguiente manera:
𝑀
𝐴
𝐵
(
𝑖
,
𝑗
)
=
1
M
AB
(i,j)=1 si hay un vuelo directo desde
𝐴
𝑖
A
i
a
𝐵
𝑗
B
j
, de lo contrario
0
0.
𝑀
𝐵
𝐶
(
𝑗
,
𝑘
)
=
1
M
BC
(j,k)=1 si hay un vuelo directo desde
𝐵
𝑗
B
j
a
𝐶
𝑘
C
k
, de lo contrario
0
0.
Ejemplo:
𝑀
𝐴
𝐵
=
(
1
0
1
1
0
1
0
1
1
1
1
0
)
M
AB
=
1
0
1
0
1
1
1
0
1
1
1
0
𝑀
𝐵
𝐶
=
(
1
0
0
1
1
0
0
1
)
M
BC
=
1
0
1
0
0
1
0
1
Operación para obtener las formas distintas de ir de A a C:
Para
...