ORDEN DE INFORMACIÓN
RAZONAMIENTO
MATEMÁTICO
Profesor
Carlos Cabana
Aguilar
RUTAS Y TRAYECTORIAS
RUTAS Y TRAYECTORIAS
EN GRAFOS DIRIGIDOS EN GRAFOS NO DIRIGIDOS
RUTAS Y TRAYECTORIAS
CONCEPTOS IMPORTANTES
GRAFO CAMINO O RUTA
Diagrama que está compuesto por un conjunto de Es una sucesión de aristas que van de un vértice a otro
nodos o vértices conectados mediante arcos o vértice.
aristas.
Se observa el camino: ABCD
A
C
B IMPORTANTE
En un camino no se debe
D repetir ninguna arista o tramo.
TRAMO
NODOS O VÉRTICES Cada una de las partes en las que se divide una
extensión.
ARISTA, ARCO o LÍNEA Ejemplo: En el camino ABCD se observa el tramo CD.
RUTAS Y TRAYECTORIAS
CONTEO DE RUTAS
Los problemas en este tema consiste en conocer el número de caminos o rutas que existen desde un punto
inicial a otro punto final bajo determinadas condiciones.
CONTEO DE RUTAS EN GRAFOS DIRIGIDOS (RUTAS ESTABLECIDAS)
Se debe seguir una dirección determinada, nunca retrocediendo.
Utilizaremos por lo general las siguientes técnicas de conteo:
• PRINCIPIO DE ADICIÓN
• PRINCIPIO DE MULTIPLICACIÓN
Observación:
En algunos problemas será necesario el uso de ambos criterios.
RUTAS Y TRAYECTORIAS
PRINCIPIO DE ADICIÓN PRINCIPIO DE MULTIPLICACIÓN
Se suman cuando o bien se va por un camino o Se multiplican cuando para llegar a un camino se debe
bien se va por el otro; es decir no por ambos a la pasar por un tramo y necesariamente por el otro también.
vez.
Ejemplo:
Ejemplo: ¿De cuántas maneras se puede ir de A hacia B siempre
¿Cuántas rutas distintas existen para ir del punto A avanzando, pasando por C necesariamente?
hasta el punto B, siempre avanzando?
2 Si me voy por este tramo hay tres formas de llegar a B
A 1 B
A C B
3 AC y CB
Se puede ir de 2 + 1 + 3 = 6 maneras 2 3
Se puede ir de 2 x 3 = 6 maneras
RECUERDA: Principio de Adición ( o < > + ) Principio de Multiplicación ( y < > x )
RUTAS Y TRAYECTORIAS
Ejemplo 1: Resolución:
¿Cuántos caminos hay de A hacia B si solo se debe Nos piden: De cuántas maneras distintas se puede ir de
ir en la dirección que indican las flechas? A siguiendo solo las direcciones indicadas.
Aplicamos el principio de adición, siguiendo las flechas y
sumando donde concurren:
1 1 1
1 2
A) 6 B) 3 1 4
2
C) 4 D) 7
∴ El total de caminos para ir de A hacia B es 4.
RUTAS Y TRAYECTORIAS
Ejemplo 2: Resolución:
¿De cuántas maneras diferentes se Nos piden: De cuántas maneras diferentes se puede ir de A hasta B,
podrá ir de A hasta B, sin retroceder sin retroceder en ningún momento.
en ningún momento? Aplicando el principio de adición y multiplicación.
1
3 5
A) 15 B) 16 1
C) 17 D) 18
AB o AC y CB
RECUERDA: N° de maneras de
Principio de adición (o<>+) ir de A hasta B = (1 + 1) + 3 x 5 = 17
Principio de multiplicación (y<>x)
∴ El total de maneras para ir de A hacia B es 17.
RUTAS Y TRAYECTORIAS
CONTEO DE RUTAS EN GRAFOS NO DIRIGIDOS (RUTAS NO ESTABLECIDAS)
No es necesario seguir una dirección determinada, es posible retroceder.
Por lo tanto no se puede aplicar en forma directa algún principio.
Se presenta además ciertas condiciones como el de no repetir un vértice o el
no repetir algún tramo.
Ejemplo:
En la siguiente figura, ¿cuántos caminos diferentes hay desde A hasta B?
A B
I. No se puede repetir puntos en ningún momento. II. No se puede repetir tramos en ningún momento.
A B A B A B A B
De A hacia B hay un camino. De A hacia B hay tres caminos.
Ejemplo 3:
¿Cuántas rutas diferentes hay para ir de A
hasta B, sin pasar dos veces por un mismo M
punto? 2
B
2
A
N
A) 8 B) 7
C) 6 D) 5 Total de rutas: 2 + 2 + 1 = 5
PUNTOS CARDINALES
N𝛽ºE
O𝜙ºN N N45º0 ≡ ≡ N45ºE
𝛽º
𝜙º
O E
𝜃º
𝛼º S
S𝜃ºE S45º0 ≡ ≡ S45ºE
S𝛼ºO
PUNTOS CARDINALES
Ejemplo 4: Resolución:
Desde un puerto parten Luego de 3 horas
simultáneamente dos embarcaciones
con velocidades constantes de 36
km/h y 48 km/h con direcciones 3(36)
N65º0 y S25º0, respectivamente. 108 km
Después de 3 horas, ¿cuántos N Puerto
65o
kilómetros los separa a uno del otro?
5(36)
O E
A) 180 B) 190
180 km
C) 150 D) 210 25oS
144 km
4(36)
∴ La distancia de separación será de 180 km.