Semana 15
Razonamiento Matemático
Polonio
Radio
, semana
Anual Virtual UNI Razonamiento Matemático
15
Conteo de rutas
En el presente capítulo se tendrá que averiguar cuántas rutas o caminos distintos existen desde un punto
inicial hasta un punto final. Se presentarán “problemas con rutas ya establecidas”, en donde la mayoría de
los casos aplicando el criterio de adición es suficiente para hallar el total de caminos existentes, y en otros
“problemas las rutas no estarán preestablecidas”, se tendrán que descubrir, bajo ciertas condiciones que
se brinden en el problema como el de “no repetir un vértice” o el de no “repetir algún tramo”, el total de
rutas existentes.
Debemos tener en cuenta lo siguiente: Camino hamiltoniano
• Un grafo es un conjunto de vértice o nodos
unidos por aristas o arcos.
6
vértice o nodo
4 5
arista o arcos 1
3 2
Un camino hamiltoniano recorre todos
Grafo etiquetado con 6 vértices y 7 aristas. los vértices exactamente una vez.
TIPOS DE PROBLEMAS
• Un camino o ruta es una sucesión de vértices
unidos por aristas. Grafos dirigidos
Se debe seguir la dirección determinada, nunca re
trocediendo. ¿Cuántos caminos hay de A hacia B si
Camino se debe ir en la dirección que indican las flechas?
a c A
b
d
B
• Camino euleriano y hamiltoniano
Para ir de A hacia B hay 4 caminos.
Camino euleriano
Grafos no dirigidos
Cuando no hay una dirección determinada y no es
posible aplicar Pascal. ¿Cuántos caminos hay de A
6 7
hacia B si no se debe pasar dos veces por el mismo
3
punto?
A
5 8
4 2
1
Un camino euleriano recorre todas
B
las aristas exactamente una vez
(puede repetir vértices). Para ir de A hacia B hay 7 caminos.
Razonamiento Matemático
Polonio
Radio
, semana
Anual Virtual UNI Razonamiento Matemático
15
Conteo de rutas
En el presente capítulo se tendrá que averiguar cuántas rutas o caminos distintos existen desde un punto
inicial hasta un punto final. Se presentarán “problemas con rutas ya establecidas”, en donde la mayoría de
los casos aplicando el criterio de adición es suficiente para hallar el total de caminos existentes, y en otros
“problemas las rutas no estarán preestablecidas”, se tendrán que descubrir, bajo ciertas condiciones que
se brinden en el problema como el de “no repetir un vértice” o el de no “repetir algún tramo”, el total de
rutas existentes.
Debemos tener en cuenta lo siguiente: Camino hamiltoniano
• Un grafo es un conjunto de vértice o nodos
unidos por aristas o arcos.
6
vértice o nodo
4 5
arista o arcos 1
3 2
Un camino hamiltoniano recorre todos
Grafo etiquetado con 6 vértices y 7 aristas. los vértices exactamente una vez.
TIPOS DE PROBLEMAS
• Un camino o ruta es una sucesión de vértices
unidos por aristas. Grafos dirigidos
Se debe seguir la dirección determinada, nunca re
trocediendo. ¿Cuántos caminos hay de A hacia B si
Camino se debe ir en la dirección que indican las flechas?
a c A
b
d
B
• Camino euleriano y hamiltoniano
Para ir de A hacia B hay 4 caminos.
Camino euleriano
Grafos no dirigidos
Cuando no hay una dirección determinada y no es
posible aplicar Pascal. ¿Cuántos caminos hay de A
6 7
hacia B si no se debe pasar dos veces por el mismo
3
punto?
A
5 8
4 2
1
Un camino euleriano recorre todas
B
las aristas exactamente una vez
(puede repetir vértices). Para ir de A hacia B hay 7 caminos.
