Aplicacion-del-algoritmo-de-Dijkstra-al-problema-de-la-ruta-mas-corta-y-su-distancia--caso-practico-del-ferrocarril-en-Mexico

Vista previa del material en texto

UNIVERSIDAD NACIONAL 
AUTÓNOMA DE MÉXICO 
 
FACULTAD DE ESTUDIOS SUPERIORES 
ACATLÁN 
 
APLICACIÓN DEL ALGORITMO DE DIJKSTRA AL PROBLEMA DE LA RUTA MÁS CORTA Y SU 
DISTANCIA (CASO PRÁCTICO DEL FERROCARRIL EN MÉXICO) 
 
T E S I S 
QUE PARA OBTENER EL TÍTULO DE 
A C T U A R I O 
 
P R E S E N T A: 
RODRIGO ISRAEL SANTIAGO GONZÁLEZ 
 
 
Asesor: DRA. MARICARMEN GONZÁLEZ VIDEGARAY 
Mayo, 2012 
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
 
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
 
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
A mis padres por su apoyo durante mis estudios. 
A mi esposa por su gran dedicación a mi persona. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
No es tarea de la Universidad ofrecer lo que la sociedad le pide, sino lo que la sociedad necesita. EDW. 
 
Índice General 
Introducción ........................................................................... i 
Actualidad del ferrocarril en México .................................................... i 
Ferrocarriles participantes en México ................................................. iii 
Delimitación del problema ................................................................... v 
Hipótesis ............................................................................................ vii 
Justificación ....................................................................................... vii 
Capítulo 1 .............................................................................. 1 
Fundamentos de la Teoría de Grafos ................................. 1 
Introducción ......................................................................................... 1 
Definiciones ......................................................................................... 1 
Subgrafos ............................................................................................. 5 
Diagramas ............................................................................................ 5 
Isomorfismo en grafos ......................................................................... 7 
Matriz de incidencia y matriz de adyacencia ....................................... 8 
Caminos y Conexiones ...................................................................... 10 
Digrafo etiquetado y ponderado ........................................................ 20 
Capítulo 2 ............................................................................ 23 
Introducción al Análisis de Algoritmos ............................ 23 
Conceptos Básicos ............................................................................. 23 
Correctez de un algoritmo .................................................................. 24 
Notación para expresar complejidad en tiempo (complejidad 
asintótica) ........................................................................................... 25 
Funciones de Complejidad en tiempos más usuales .......................... 28 
Tipos de Algoritmos .......................................................................... 30 
Complejidad de los problemas ........................................................... 30 
Comparación de Algoritmos .............................................................. 32 
Algoritmos de exploración en grafos ................................................. 35 
Clasificación de Algoritmos para rutas cortas ................................... 36 
Capítulo 3 ............................................................................ 37 
El problema de la ruta más corta ..................................... 37 
Algoritmo de Dijkstra ........................................................................ 38 
Algoritmo Glotón ............................................................................... 38 
Análisis del Algoritmo de Dijkstra .................................................... 39 
Correctez del algoritmo de Dijkstra ................................................ 43 
Diagrama de flujo del Algoritmo de Dijkstra ................................. 47 
Ejemplo del Algoritmo de Dijkstra................................................. 48 
Pseudocódigo del Algoritmo de Dijkstra ........................................ 50 
Desarrollo ............................................................................ 51 
Análisis del Grafo del Ferrocarril en México .................................... 51 
Vértices ...................................................................... 52 
Aristas ........................................................................ 52 
Estructura ........................................................................................... 53 
Conclusiones ....................................................................... 54 
Anexos .................................................................................. 56 
Código de la Clase Dijkstra ............................................................... 56 
Ejecución del Programa ..................................................................... 62 
Diagrama de .................................................................... 65 
Bibliografía.......................................................................... 66 
 
Introducción 
Actualidad del ferrocarril en México 
El ferrocarril es un medio de transporte que tiene sus comienzos en México en el año de 1837. En 
la actualidad, existen tres rubros donde se desempeñan los ferrocarriles como son: transporte turístico, 
transporte de pasajeros y transporte de carga esta última es la actividad principal del ferrocarril en el país, 
la cual se complementa con intercambios comerciales a nivel ferroviario únicamente con los países del 
Norte de América y con las navieras de todo el mundo en los principales puertos del país. 
Tomando en cuenta lo anterior y para ubicar el porcentaje de participación de México a nivel de 
América del Norte y tomando como base el total de toneladas movidas por ferrocarril durante 2010, en 
esta área, la participación de Estados Unidos fue del 88% con 2,705.6 millones de toneladas-kilómetroa 
(Asociación Americana de Ferrocarriles, 2011), la de Canadá del 10% con 299.2 millones de toneladas-
kilómetro (Transport Canada, 2010), mientras que México solamente participa con el 3% con 78.8 
millones de toneladas-kilómetro (Dirección General de Transporte Ferroviario y Multimodal, 2010) 
(Figura 1). 
 
 
a
 Total de toneladas movidas por kilómetro recorrido. 
3%
88%
10%
Figura 1. Toneladas kilómetro en FFCC - Norte América 2010
México
Estados Unidos
Canada
ii | Introducción 
Comparando al transporte ferroviario nacional con los otros medios de transporte de carga, léanse 
aéreo, marítimo y carretero, en 2010 el ferrocarril se encontraba con una participación del 12% 
(Dirección General de Planeación, 2011) (Figura 2). 
 
El transporte ferroviario nacional es un medio que desde su privatización no ha dejado de crecer, 
con excepción de la recesión mundial del 2009, en cuanto los datos de carga transportada (Dirección 
General de Transporte Ferroviario y Multimodal, 2010) y participación en el mercado. 
 
0.6
470
105
272
0 100 200 300 400 500Áereo
Carretero
Ferroviari
o
Marítimo
(Cifras en miles de toneladas)
Figura 2. Miles de toneladas transportadas en México 2010
0
20,000
40,000
60,000
80,000
100,000
120,000
1990 1995 2000 2005 2010 2015
Figura 3. Evolución del ferrocarril en México 1995 - 2010
Toneladas 
(miles)
Toneladas-Km 
(millones)
iii | Introducción 
Ferrocarriles participantes en México 
En México existen actualmente siete ferrocarriles (FFCC), los cuales aparecieron a partir de que el 
12 de Mayo de 1995, el gobierno Mexicano promulga la Ley Reglamentaria del Servicio Ferroviario de 
la cual se desprende que la empresa paraestatal, Ferrocarriles Nacionales de México por sus siglas (FNM) 
sería concesionada a particulares para construir, operar y explotar vías férreas así como prestar el servicio 
público de transporte ferroviario. 
Para impedir que existiera un monopolio, la empresa se concesiono por partes, de las cuales 
surgieron dos ferrocarriles clase I de acuerdo a la clasificación de la AARb. 
1. Nombre: Kansas City Southern México (KCSM) 
Inicio de operaciones: Enero de 1997 
Kilometraje de vías: 4054.2 km 
Concesión que opera: 
 Ferrocarril del Noreste (Líneas A, B, BB, BC, BD, BF, F, L, LA, LB, LJ, N, NB, NC, ND, 
NE, NF, O, OA, V, XX) 
Fronteras: Nuevo Laredo y Matamoros 
Puertos: Tampico y Lázaro Cárdenas y Veracruz 
2. Nombre: Ferrocarril Mexicano (FXE) 
Inicio de operaciones: Febrero de 1998 
Kilometraje de vías: 8251.8 km 
Concesiones que opera: 
 Ferrocarril del Pacifico Norte (Líneas A, AE, AK, B, BC, I, IB, IC, IN, M, MA, P, R, RA, 
T, TC, TE, TF, TG, TH, TL, TM, U, UA, TI) 
 Línea Corta Ojinaga – Topolobampo (Línea Q) 
 Línea Corta Nacozari (TA y TB) 
Fronteras: Mexicali, Nogales, Ojinaga, Ciudad Juárez y Piedras Negras 
Puertos: Manzanillo, Topolobampo y Tampico 
3. Nombre: Ferrosur (FSRR) 
Inicio de operaciones: Junio de 1998 
Kilometraje de vías: 1638.7 km 
 
b
 Association of American Railroads (Asociación Americana de Ferrocarriles, Incluye a los ferrocarriles más 
importantes de Norte América, se especializa en mejorar la seguridad y productividad del transporte ferroviario) 
iv | Introducción 
Concesiones que opera: 
 Ferrocarril del Sureste (Líneas A, E, EA, FA, G, GA, GF, HB, HC, S, SA, SC, V, VB, Z, 
ZA) 
 Línea Corta del Sur y Oaxaca (Líneas VK y VC) 
 Línea Corta de Hidalgo (H, HA) 
 Línea Corta Tres Valles – San Cristóbal (GB) 
Fronteras: N/A Puertos: Veracruz 
4. Nombre: Ferrocarril Coahuila Durango (LFCD) 
Inicio de operaciones: Abril de 1998 
Kilometraje de vías: 952.5 km 
Concesiones que opera: 
 Ferrocarril Coahuila Durango (Líneas DA, DC, DF, RB, RC, RD, RK, RL) 
Fronteras y Puertos: N/A 
5. Nombre: Ferrocarril del Istmo de Tehuantepec (FIT) 
Inicio de operaciones: Octubre de 1999 
Kilometraje de vías: 1790.1 km 
Concesiones que opera: 
 Línea Corta del Istmo de Tehuantepec (Z) 
 Línea Corta Chiapas-Mayab (FA, FD, FN, FX, K) 
Fronteras y Puertos: N/A 
6. Nombre: Ferrocarril y Terminal Ferroviaria del Valle de México(TFVM) 
Inicio de operaciones: Mayo de 1998 
Kilometraje de vías: 176.5 km 
Concesiones que opera: 
 Terminal Ferroviaria del Valle de México (Líneas A, B, C, H, N, NA, S, SH, VK) 
Fronteras y Puertos: N/A 
7. Nombre: Administradora de la Vía Corta Tijuana – Tecate (ADMICARGA) 
Inicio de operaciones: Septiembre de 2000 
Kilometraje de vías: 71.4 km 
Concesiones que opera: 
 Línea Corta Ferrocarril Tijuana - Tecate (Línea UB) 
Fronteras y Puertos: Tijuana y Tecate 
v | Introducción 
El porcentaje de participación de los Ferrocarriles en 2010 por empresa Ferroviaria tomando en 
cuenta las Toneladas – Kilómetro transportadas se divide como se muestra en la Figura 4. 
 
Delimitación del problema 
El objetivo del presente trabajo es desarrollar un programa que determine la ruta más corta entre 
dos estaciones dentro de la red del Ferrocarril en México y su respectiva distancia, el algoritmo principal 
del programa deberá cumplir las siguientes características: 
 Rápido (El usuario deberá obtener el resultado en un tiempo corto) 
 Confiable (El usuario deberá obtener el resultado correcto y sin variaciones cada vez que 
realice una consulta) 
 Flexible (El usuario deberá poder modificar de forma sencilla los parámetros de entrada y 
salida de información también debe tener la capacidad de calcular rutas alternas válidas 
dentro del negocio del Ferrocarril, contemplando una serie de reglas y factores ya sean 
determinadas por el usuario o por la naturaleza misma del Ferrocarril. 
A continuación se enlistan las diferentes limitaciones que tenemos para que las rutas sean válidas 
en el ámbito del Ferrocarril. 
 Factores legales y de concesión: Se deben seguir las reglas dadas de alta ante la SCT 
(Secretaría de Comunicaciones y Transportes). Cada Ferrocarril tiene concesión sobre las 
líneas por donde puede dar servicio, sin embargo existen registrados ante la SCT factores y 
32%
58%
9%
0%
1% 1%
0%
Figura 4. Participación de los FFC en Toneladas-Km (millones)
KCSM
FXE
FSRR
TFVM
LFCD
FCCM
ADMI
vi | Introducción 
vías por derecho de paso que se pagan al Ferrocarril propietario si se desea dar servicio 
utilizando dichos tramos. 
 Factores de infraestructura: La infraestructura de una estación nos puede ocasionar que el 
intercambio no se efectué en la estación más cercana dada la capacidad del patio de 
intercambio, por lo que se tiene que realizar el intercambio en una estación más alejada pero 
con una mayor capacidad. Otra restricción se puede presentar en la capacidad de carga de la 
vía, ya que si el tren rebasa esta restricción se debe encontrar una vía altera. 
 Factores orográficos: Se puede restringir a que se utilice una vía cuando la pendiente esta es 
muy grande y si el material que se transporte es peligroso existen dos casos. 
a. Materiales No Peligrosos 
Se tienen que usar locomotoras ayudadoras cuando se transita en el sentido positivo 
de la inclinación por lo cual se necesita conocer si la ruta pasa por determinadas estaciones y 
en el sentido en que lo hacen. Para este caso existen tramos registrados ante la SCT quien 
autoriza la sobretasa que cada Ferrocarril cobra por cruzar por dichos tramos. 
b. Materiales Peligrosos 
Si se transportan materiales peligrosos no se puede pasar por dichos tramos y se debe 
buscar una ruta alterna. 
 Factores climatológicos: Si se presentan inundaciones o deslaves que pueden afectar el paso 
por una vía por lo que se necesita obtener rutas alternas. 
 Factores comerciales: La concesión permite derechos de paso a los diferentes ferrocarriles y 
cuando existe algún acuerdo comercial entre los mismos, un ferrocarril puede recorrer las 
líneas de otro. Lo anterior implica que los ferrocarriles buscan obtener la mayor participación 
de las rutas creando rutas alternas, por lo que se necesita conocer las rutas que maximicen el 
recorrido de un ferrocarril determinado para un origen y destino. 
 
vii | Introducción 
Hipótesis 
Se pretende demostrar que convirtiendo la red del ferrocarril en México en un modelo y aplicando 
el algoritmo de Dijkstra en un programa para el cálculo de rutas cortas y su distancia, podremos satisfacer 
las características anteriormente mencionadas. 
Para lograr lo anterior en el primer capítulo se expondrán las definiciones, conceptos, propiedades y 
teoremas básicos de la teoría de grafos que nos permitan incluir todas las características del problema real 
en la teoría y así poder modelar de forma correcta el problema. 
En el segundo capítulo se revisarán los conceptos generales de la complejidad de los algoritmos 
para verificar que nuestro algoritmo seleccionado cumpla con los requisitos necesarios para poder 
alcanzar el objetivo del presente trabajo y que se adapte a las características que se definan en el primer 
capítulo de la teoría de grafos. 
En eltercer capítulo se analizará el problema de la ruta más corta y los diferentes algoritmos que se 
pueden aplicar a dicho problema, se analizará porque se eligió el algoritmo así como un análisis profundo 
de este y sus características. 
En el cuarto capítulo se desarrolla la adaptación del modelo del grafo del ferrocarril en México y 
sus características, así como la estructura elegida para la incorporación del algoritmo en el programa, la 
justificación del lenguaje de programación que se utilizó para el desarrollo así como los pasos que se 
llevaron acabo para la implementación del algoritmo y una ilustración de los resultados finales del 
programa en ejecución. 
En los anexos se agrega el código del algoritmo utilizado y una ilustración del grafo de la red del 
ferrocarril en México. 
Justificación 
Las áreas Comercial, de Finanzas y de Logística de un ferrocarril requieren de las rutas y sus 
distancias para diferentes usos, de entre los que se encuentran los siguientes: 
viii | Introducción 
1. Cálculo de Tarifas (TUCEc): Existen dos principales variables para realizar el cálculo de la 
TUCE, el primero es el producto que se transporta y el segundo es la distancia recorrida por cada 
Ferrocarril participante del flete. Cada Ferrocarril registra ante la SCT Factores Fijos y Factores 
Variables dependiendo del producto donde el factor variable se multiplica por la distancia recorrida. Este 
cálculo existía desde FNM (Ferrocarriles Nacionales de México) y a partir de la privatización se ha 
modificado para quedar de la siguiente manera: 
 
 
 
 
Como puede verse en el cálculo de la TUCE, va implícita la distancia recorrida por cada uno de los 
FFCC, por lo tanto es necesario conocer la ruta que tendrá el movimiento. 
Antes de continuar daremos unas definiciones relativas a los conceptos de la TUCE. 
 Ferrocarriles participantes: Son tanto Nacionales como Internacionales y se identifican 
con un máximo de 4 caracteres, existe actualmente cerca de 740 registrados ante la AAR tomando en 
cuenta las líneas cortas. 
 Estación: Lugar donde se inicia, termina, pasa o se intercambian carros con o sin carga, 
existen alrededor de 50,000 estaciones registradas vigentes. Existen dos formas de identificar una 
estación de Ferrocarril 
Internacionalmente: Nacionalmente: 
Standard Carrier Alpha Code (SCAC): 
FC propietario de la estación 
Freight Station Accounting Code (FSAC): 
Número de hasta 5 dígitos identificador de la estación 
Standard Point Location Code(SPLC): 
Localización geográfica de la estación 
Línea: Existen 106 diferentes líneas en México 
Poste Kilométrico: Número que indica el 
kilómetro en que se encuentra la estación con 
respecto al comienzo de la línea. La unión de las 
anteriores nos da la estación operativa o CIRC7 
 
c
 Tarifa Única de Carga Express (TUCE): Serie de reglas dadas de alta ante la SCT la cuales especifican el cobro 
máximo que un ferrocarril está autorizado para cobrar a sus clientes por el servicio de flete de mercancía así como de 
regreso de vacío de carros de Ferrocarril. 
ix | Introducción 
Estación: GUADALAJARA, JA MÉXICO 
SCAC: FXE 
FSAC: 09678 
SPLC: 944300000 
Estación: GUADALAJARA, JA MÉXICO 
Línea: I (Esta línea corre de Irapuato a 
 Manzanillo) 
Poste Kilométrico: 0260 
 Puntos de Intercambio: Puntos de interconexión o conocidos como regla 260, son las 
estaciones donde un ferrocarril recibe o entrega carros de o a otro ferrocarril. Existen alrededor de 
8,300 puntos de intercambio registrados. Se identifican con un máximo de 5 caracteres y están 
asociados a alguna estación. 
Ejemplo: 
 Estación: Celaya 
 Intercambio: CELAY (Punto de intercambio entre FXE y KCSM) 
 Ruta: Formada por el origen y el destino de la ruta así como los participantes y los puntos 
de intercambio entre ellos. 
Ejemplos: 
1. Guadalajara JA a Veracruz VL: FXE_09678 – FSRR06055 
 
 
Figura 5. Ruta Guadalajara JA – Veracruz VL (FXE – FSRR) 
Guadalajara, JA 
Lechería, EM 
Veracruz, VL 
x | Introducción 
2. Guadalajara JA a Veracruz VL: FXE_09678 – KCSM06055 
 
3. Puebla PU a Durango DG: FSRR09056 – LFCD01418 
 
Figura 7. Ruta Puebla PU – Durango DG 
Puebla, PU 
Lechería, EM 
Escalón, CI 
Durango, DG 
Figura 6. Ruta Guadalajara JA – Veracruz VL (FXE – KCSM) 
Veracruz, VL 
Guadalajara, JA 
Lechería, EM 
Celaya, GJ 
xi | Introducción 
En los ejemplos anteriores podemos ver las variantes de las rutas, ya que aunque es el mismo 
origen y destino en las rutas uno y dos, en la primera ruta el Ferrocarril FXE entrega en el punto de 
intercambio de Lechería para que el Ferrocarril Ferrosur lo lleve al destino Veracruz. En la segunda el 
encargado de llevar la mercancía de Lechería a Veracruz es el Ferrocarril KCSM, cada uno por sus vías 
correspondientes. Podemos realizar una clasificación de rutas como se muestra a continuación: 
 
En el presente trabajo nos enfocaremos a trabajar con rutas Nacionales. 
 Distancia: Se dividen en los dos tipos siguientes. 
a) Horaria: Distancia física que recorre el Ferrocarril, la unidad es en kilómetros y se 
calcula hasta décimas, estas se encuentran definidas en los horarios dados de alta ante la 
Dirección General de Transporte Ferroviario y Multimodal. Dirección de Regulación Técnica 
Operativa de Transporte Ferroviario de la SCT. 
b) Comercial: Distancia que se calcula en base a la TABLA DE DISTANCIAS NUM. 8 
aprobada por la SCT, según Oficio Núm. 23031-EPS-2142, Folio 120994, Exp.- 302/1, de 
noviembre 3 de 1977. La cual está dada en base a la logística del movimiento de trenes y 
contempla 81 tablas, está dada en kilómetros enteros. Estas son las distancias que se utilizan 
para el cálculo de la TUCE y las reglas para su cálculo son las siguientes. 
o Regla No. 1 Sección III.- 
Las distancias que servirán de base para la aplicación de las cuotas serán las que figuran 
en la o las Tablas de Distancias aprobadas para cada empresa porteadora por la Secretaría 
de Comunicaciones y Transportes, Dirección General de Ferrocarriles en Operación. Se 
obtiene la distancia comercial de un origen a un destino tomando el valor más grande que 
se recorra en una línea. Es decir, no se pueden sumar las distancias de tramos recorridos 
en una misma línea. 
o Regla No. 1 Sección IV.- 
a) Si el solicitante de un servicio de transporte no expresa la ruta o línea por la cual se 
hará el transporte, ésta será fijada por la empresa porteadora en donde se origine el 
xii | Introducción 
embarque; pero el importe que se cobre, será el correspondiente a la ruta más corta, a 
menos que ésta estuviera interrumpida por causa de fuerza mayor, pues en este caso se 
cobrará el servicio por la ruta o línea que se haya usado. 
b) En aquellas estaciones en donde existan vías anchas y angostas, el carro que se cargue 
determinará la ruta. Cuotas a distancias no publicadas 
o Regla No. 1 Sección V.- 
 Las cuotas por distancias que figuran en las Tablas de cuotas se aplican por Secciones de 
10 en 10 kilómetros hasta 250 kilómetros, de 25 en 25 desde 250 kilómetros hasta 1,000 y 
de 50 en 50 de 1,000 kilómetros en adelante. Para encontrar cuotas a distancias 
intermedias, se aplicarán las correspondientes a la distancia publicada inmediata anterior 
o posterior, en la forma siguiente: 
Secciones de 10 en 10 Las Fracciones menores de 5 kilómetros se desprecian y las de 
5 a 9 se elevan a 10 kilómetros. 
Secciones de 25 en 25 Las Fracciones menores de 13 kilómetros se desprecian y las 
de 13 a 24 se elevan a 25 kilómetros. 
Secciones de 50 en 50 Las Fracciones menores de 25 kilómetros se desprecian y las 
de 25 a 49 se elevan a 50 kilómetros. 
2. Alquiler de carros (CAR HIRE): De acuerdo a lo establecido en las reglas del CAR 
HIRE publicadas por la AAR, el CAR HIRE se entiende como la contraprestación que paga un 
ferrocarril signatario de los acuerdos deintercambio de la AAR por el uso de equipo ferroviario (y 
sus accesorios, en los casos que así aplica) propiedad de otro ferrocarril o entidad signatarios. El 
cómputo de dicha contraprestación se efectúa por el tiempo que permaneció el equipo en territorio del 
ferrocarril usuario y por el kilometraje recorrido, de acuerdo a tarifas negociadas o por omisión 
aplicables entre ambas partes. El CAR HIRE opera de manera automática, sin necesidad de contrato 
específico entre el propietario del equipo y el FC usuario, bajo los criterios de la AAR (Circular OT-
10). Por lo tanto, se necesita conocer la distancia de los tramos recorridos del carro en territorio del 
ferrocarril usuario. 
3. Estadística: El principal indicador estadístico para comparar los servicios de carga de un 
medio de transporte es el de Toneladas –Kilómetro el cual equivale al desplazamiento de una 
tonelada de carga la distancia de un kilómetro. Por ejemplo si un tren generó 200 Toneladas-
Kilómetro por recorrer diez kilómetros con veinte toneladas, este es comparable a uno que recorra 
cuarenta kilómetros con cinco toneladas. Su uso implica conocer la distancia recorrida. 
xiii | Introducción 
4. Documentación de fletes: Para que la carga sea transportada se debe llenar un 
documento donde el embarcador especifica de manera explícita las características específicas del 
servicio a realizar por el porteador de la carga, en el caso del ferrocarril, uno de eso datos es la ruta a 
seguir, tomando en cuenta origen, destino, FFCC participantes e intercambios entre los mismos. Si el 
cliente proporciona la ruta, se utilizará la misma, de lo contrario se debe identificar la ruta óptima 
para el servicio. 
5. Asignación de carros vacíos: El área de logística de un ferrocarril necesita maximizar la 
asignación de carros vacíos de su flota a los clientes que los solicitan, por lo que se necesita una 
matriz de distancias de toda la red propiedad del ferrocarril con la distancia mínima entre todas las 
estaciones. 
6. Costos y Rentabilidad: También es necesaria la distancia recorrida para obtener los 
costos variables como gasto de diesel, horas de trabajo etc., así como el cálculo de la rentabilidad 
 
 
Capítulo 1 
Fundamentos de la Teoría de 
Grafos 
Introducción 
Muchas situaciones del mundo real pueden ser descritas convenientemente por medio de un 
diagrama, los cuales consisten en un conjunto de puntos y líneas que unen ciertos pares de estos. Por 
ejemplo, los puntos pueden representar personas, con líneas uniendo pares de amigos; o los puntos 
pueden ser centros de comunicación con líneas representando ligas de comunicación. Notemos que en 
estos diagramas las personas están principalmente interesadas en conocer si dos puntos están unidos por 
una línea; y la forma en la que están unidas es abstracta e inmaterial. Una abstracción matemática de 
situaciones de este tipo da lugar al concepto de grafo. 
Definiciones 
En primer lugar se darán las definiciones fundamentales de la Teoría de Grafos para ubicar el 
contexto del problema que vamos a resolver. 
Definición. Un grafo es una pareja G = (V, E) de conjuntos tales que ; es decir que cada 
elemento de E es a su vez un subconjunto de 2 elementos de V y donde V es finito y no 
vacío. Los elementos de V son los vértices (o nodos, o puntos) de la grafo G, los elementos de E son sus 
aristas o lados. Un grafo con un conjunto de vértices V se dice que es un grafo en V. El conjunto de 
vértices en un grafo G es referido como V (G) y su conjunto de aristas como E (G). 
Definición. Un grafo G consta de una tripleta ordenada (V (G), E (G), f (G)) la cual consiste en un 
conjunto no vacío V (G) de vértices, un conjunto E (G), independiente de V (G), de aristas, y una función 
de incidencia f (G) que asocia con cada arista de G un par no ordenado (no necesariamente distinto) de 
2 | Fundamentos de la Teoría de Grafos 
vértices de G. Si e es una arista y u y v son vértices tales que, entonces se dice que e une a u y 
v. Los vértices u y v son llamados los extremos de e. 
Definición. El número de vértices de un grafo G es su orden, escrito como ; su número de 
aristas es denotado por a lo que llamamos el tamaño del grafo. 
Definición. Dos vértices u, v de un grafo G = (V, E) se dicen adyacentes si {u, v} ∈ E (G), 
asimismo dos aristas son adyacentes si tienen un mismo vértice como extremo. 
Definición. Análogamente si e = {u, v} decimos que el lado e es incidente a los vértices u y v. 
Definición. Una arista con extremos idénticos es llamada bucle, una arista con extremos distintos 
una liga. 
Definición. Un grafo que contiene bucles es llamado pseudografo. 
Definición. Un grafo que contiene dos o más ligas para el mismo par de vértices es llamado 
multígrafo. El conjunto de los grafos está contenido en el de los multígrafos pero no a la inversa. 
Definición. Un grafo es finito si tanto su conjunto de vértices como su conjunto de aristas son 
finitos. 
Definición. Un grafo es simple si no es pseudografo ni multígrafo. 
Definición. El grado de un vértice v en G es el número de aristas incidentes a él. 
 
Denotaremos a como el mínimo grado de G y a 
como el máximo grado de G. 
Definición. Los vecinos de un vértice v se definen como: 
 
De aquí se puede ver que si un grafo es simple entonces , también si el orden de 
una grafo G es p, entonces es claro que 
Definición. Un vértice de grado cero es llamado vértice aislado. 
Definición. Un vértice de grado uno es llamado vértice terminal. 
3 | Fundamentos de la Teoría de Grafos 
Teorema. Sea G un grafo de orden p y tamaño q con Entonces 
 
Demostración. Al sumar el grado de cada vértice de G, cada arista es contada dos veces, una vez 
por cada vértice en el que incide. 
Corolario. En cualquier grafo el número vértices de grado impar es par. 
Demostración. Si definimos a y como el conjunto de vértices de grado par e impar 
respectivamente, es claro que , además de ser independientes, por lo tanto. 
 
De aquí que 
 
Donde los dos elementos de la derecha de la ecuación son pares, por lo tanto la suma de la 
izquierda debe contener un número par de sumandos, pues cada elemento de ésta es impar. 
Definición. Un grafo G es r-regular o regular de grado r si 
 
De esto se observa que: . 
Definición. El complemento de un grafo denotado por se define como el grafo 
 tal que 
Definición. Un grafo simple G = (V, E) se dice completo si cada vértice está conectado a cualquier 
otro vértice en G. 
Definición. Un grafo G = (V, E) se dice vacío si , es decir, si no tiene aristas. 
Definición. Un grafo simple bipartita G = (V, E), es en el que V (G) puede ser particionado en dos 
subconjuntos X y Y, tales que cada arista tiene un extremo en X y un extremo en Y 
, de tal manera que toda arista e ∈ E conecta un vértice de X con un vértice de Y, a tal partición 
se le llama bipartición del grafo. 
4 | Fundamentos de la Teoría de Grafos 
 
Definición. Un grafo completo, denotado por , se llama a un grafo de orden p en donde a todo 
par de vértices estos son adyacentes. 
 
 
Figura 1.2 Ejemplos de grafos completos 
 
u v 
w x 
v u u 
 
 
u 
v 
w 
x y 
Figura 1.1 Ejemplo de un grafo bipartita 
5 | Fundamentos de la Teoría de Grafos 
Subgrafos 
Definición. Sea G = (V, E) un grafo. Si H = (W, F) es un grafo tal que W ⊆ V y F ⊆ E decimos 
que H es un subgrafo de G. Si F contiene todas las aristas de E que unen a los puntos de W en G se dice 
que H es un subgrafo completo de G generado por W. Si W = V decimos que H es un subgrafo 
extendido de G. 
Definición. Dado S ⊆ V (G) el grafo inducido por S es el ⊆-máximo subgrafo de G con S como 
su conjunto de vértices, este grafo es denotada como G [S]. 
Denotamos a G – S como el grafo inducido obtenido a partir de V (G) – S. Si S = {v} denotaremos a 
G – S como G – v en vez de G – {v} 
Dado X ⊆ E (G) el grafo inducido por X es el ⊆-mínimo subgrafo de G con S comosu conjunto de 
aristas, este grafo la denotaremos igualmente como G [X]. 
Un subgrafo H de G es llamada generador si V (H) = V (G). De aquí podemos observar que G – X 
es un grafo generador 
Si son pares de vértices no adyacentes en G, , entonces 
se define como el grafo formado a partir de G, denotamos G + { uv } como G + uv 
únicamente. 
Diagramas 
La forma usual de representar una grafo es dibujando un punto por cada vértice y uniendo dos de 
estos puntos por una línea si los correspondientes dos vértices forman una arista. La forma (diagrama) en 
la que estos puntos y líneas son dibujados es considerada irrelevante, todo lo que importa es la 
información de cuales pares de vértices forman una arista y cuáles no. Y es esta representación la que nos 
ayuda a comprender muchas de sus propiedades. 
La mayoría de las definiciones y conceptos en la teoría de grafos provienen de la representación del 
mismo grafo. 
Daremos dos ejemplos de diagramas de grafos 
1. G = (V (G), E (G), f (G)) 
V (G) = { } 
E (G) = 
 f (G) está definida por: 
6 | Fundamentos de la Teoría de Grafos 
 
 
2. H = (V (H), E (H), f (H)) 
V (H) = {u, v, w, x, y} 
E (G) = {a, b, c, d, e, f, g, h} 
 f (H) está definida por: 
 
 
 
Se puede observar en las figuras que dos aristas en un grafo se pueden interceptar en un punto que 
no sea un vértice (por ejemplo y del grafo G en la figura 1.3). 
Definición. Los grafos en los que su diagrama es interceptado solamente en sus extremos son 
llamados planos, ya que estos pueden ser representados en un plano de una manera sencilla. 
Definición. Un grafo dirigido o digrafo G = (V, E) consta de un conjunto V de vértices y conjunto 
E de aristas, que son pares ordenados de elementos de V. La relación entre V y E es irreflexiva. Los 
elementos de V también son llamados vértices, más los elementos de E son llamados aristas dirigidas, 
arcos o flechas, por lo tanto si (u, v) es un arco de G, entonces (v, u) no lo es necesariamente. 
 
 
 
 
 
 
 
 
 
 
 
 
f 
f 
f 
 
 
 
 
 
 
 
 
 
 
 
 
 
f 
Figura 1.3 Diagramas de los grafos G y H 
7 | Fundamentos de la Teoría de Grafos 
Isomorfismo en grafos 
Definición. Dos grafos y G2 son idénticos (denotado G = H) si: 
V (G1) = V (G2), E (G1) = E (G2) y f (G1) = f (G2). 
 Si dos grafos son idénticos pueden ser representados por diagramas idénticos. Si el diagrama de 
dos grafos es el mismo, pero esta etiquetado de distinta forma, ya no son idénticos pero se les llama 
Isomórficos. 
Definición. Los grafos y son isomorfos si existe una función biyectiva 
f de en con la propiedad de que, para cada par de vértices u, v ∈ , u, v son adyacentes en si y 
sólo si f (u), f (v) son adyacentes en . Es decir {u, v} ∈ ⇔ {f (u), f (v)} ∈ . Si y son 
isomorfos lo denotamos . 
Si dos grafos G1 y G2 son isomorfos, tienen el mismo número de vértices, el mismo número de 
aristas y el mismo número de vértices de cualquier grado. 
Para mostrar que dos grafos son isomórficos, se debe indicar un isomorfismo entre los mismos. El 
par de mapeos definidos por 
 
 
 
Es un isomorfismo entre los grafos G y H de la figura 1.1; G y H evidentemente tienen la misma 
estructura, y difieren solamente en el nombre de los vértices y aristas. 
Definición. Un grafo G es denso cuando en número de aristas es cercano al cuadrado de su orden o 
 
Definición. Un grafo G es disperso cuando en número de aristas es mucho menor al cuadrado de su 
orden o 
 
8 | Fundamentos de la Teoría de Grafos 
Matriz de incidencia y matriz de adyacencia 
Definición. Sea G = (V, E) un grafo con n vértices y p aristas, entonces le corresponde una matriz n 
× p denominada la matriz de incidencia de G. Si denotamos los vértices de G por y las 
aristas por . Entonces la matriz de incidencia de G es la matriz donde es 
el número de veces (0, 1 ó 2) en que el vértice y son incidentes. 
 
Definición. Otra matriz asociada a G es la matriz de adyacencia; esta es una matriz n × n 
 en donde es el número de aristas que van de hasta . Es claro que A es una matriz simétrica 
en donde si no hay bucles la diagonal está compuesta de ceros. Si el grafo es denso, nos conviene 
representarlo de esta forma o también si lo que se desea es conocer de manera rápida si existe una arista 
conectando dos vértices dados. Como A es una matriz de n × n requiere de n2 entradas si G es una grafo 
con un número grande de aristas estaríamos ingresando a la base de datos un gran número de ceros que 
no aportan información pero ocupan espacio. Es por eso, que se usan otros métodos de almacenamiento 
como lo es la lista de adyacencia descrita a continuación. 
Definición. Sea G grafo con , la lista de adyacencia asocia a cada 
 es una lista de vértices adyacentes a ordenados de manera numérica o alfabética. Podemos notar 
que esta forma de almacenamiento utiliza a lo más n × q entradas, lo que en el caso de un grafo disperso 
nos reduce la cantidad de memoria usada en la base de datos. 
9 | Fundamentos de la Teoría de Grafos 
 
Figura 1.4: (a) Matriz de Incidencia, (b) Matriz de Adyacencia y (c) Lista de Adyacencia 
 
 
 
 
 
 
 
 
 
 
 
 
(b) 
 
 
(a) 
 
 
 
 
 
 
 
 
 
 
 
 
v2 
v2 
v1 
v1 
v1 
v1 
 
 
 
 
 
 
v3 
v3 
v3 
v3 
v2 
v3 
 
 
 
 
 
 
 
 
v4 
v4 
 v4 
v4 
(c) 
10 | Fundamentos de la Teoría de Grafos 
Caminos y Conexiones 
Definición. Un camino en G es una secuencia finita no nula , en donde 
los términos son alternativamente vértices y aristas, tales que para 1 ≤ i ≤ k, los extremos de son 
y . Decimos que W es un camino desde hasta o un . Los vértices y son 
llamados el origen y término de W, respectivamente y sus vértices internos. En un grafo 
simple, un camino está determinado por la secuencia de sus 
vértices. Para referirnos al mismo camino recorrido inversamente usaremos la notación 
 
Definición. Un sub-camino de un camino es una sub-secuencia contigua de sus 
vértices. Esto es, para cualquier , la sub-secuencia de vértices es un sub-
camino de W. 
Definición. El entero k es la longitud de W denotado como . 
Definición. Denotemos con a un camino de u a v. Entonces definimos la distancia δ de un 
vértice s a un vértice v: 
 
Definición. Un camino más corto es aquel donde . 
 
Demostración. Denotemos la arista del vértice uv como u → v. Tomemos un camino más corto de s 
a v, s⇝v, y un camino más corto de s a u, s⇝u. Si un camino más corto de s a v pasa por u (s ⇝ u → v), 
el último vértice que se incluyó en el camino es, precisamente, u → v y entonces se da la igualdad 
. 
Si ningún camino más corto de s a v pasa por u, entonces un camino más corto debe tener menos 
arcos que el que pasa por u. El camino que pasa por u primero llega a u por un camino más corto de s a u 
( ; una vez en el vértice u, la forma más directa de llegar a v es utilizando el vértice u → v, por lo 
que tenemos que la longitud de s ⇝ u → v es Pero como existe un camino más corto de s a v 
que no pasa por u, tenemos 
11 | Fundamentos de la Teoría de Grafos 
Esto se ilustra en la gráfica de la siguiente figura. 
 
Definición. Un camino es cerrado si tiene longitud positiva y si el vértice origen y término son el 
mismo. 
Definición. Un camino cerrado es un ciclo si todos los vértices (excepto los extremos) son 
distintos. 
Definición. Un paseo en G se define como un camino en el cual ninguna arista es repetida. 
Definición. Una trayectoria se define como un camino en el cual ningún vértice se repite. Toda 
trayectoria es un paseo pero no a la inversa. 
Definición. Un ciclo se define como un camino cerrado en el cual no hay vértices que se repitan 
salvo el primero y el último, llamaremos la longitud de un ciclo al número de vértices distintos que en 
éste haya. 
Definición. Dado un vértice o una arista de G diremos que son acíclicos si no son parte de ningún 
ciclo enG. 
Figura1.5 Propiedad de la distancia 
s 
u 
v 
 
 
 
 
δ(s, u) = 2 ( = =>) 
δ(s, v) = 2 sin pasar por u ( ⇒ ) ≤ δ(s, u) + 1 = 3 (= =>) 
12 | Fundamentos de la Teoría de Grafos 
 
Teorema. Todo u-v-camino contiene una u-v-trayectoria 
Demostración. Sea W un u-v-camino en G. Si u = v, entonces la trayectoria u-u resuelve el 
problema, por lo tanto podemos suponer que . Digamos que . Si ningún 
vértice se repite en W, entonces ya es una trayectoria. De lo contrario tal que 
con j < k. 
De aquí que podemos afirmar que es un nuevo u-v-
camino contenido en W, si en no hay vértices que se repitan, entonces es una u-v-trayectoria 
contenida en W, de lo contrario podemos repetir el proceso anterior hasta obtener la trayectoria deseada 
dado que el número de vértices que aparecen más de una vez en W es finito. 
Definición. Dos vértices u y v de G están conectados si existe una (u,v) - trayectoria en G. 
Definición. Un grafo G es conexo si y sólo si para todo u está conectado a v. Un grafo 
que no cumple lo anterior es llamado inconexo. La conexión es una relación de equivalencia en V(G). Si 
existe una partición de V(G) en subconjuntos no vacios tal que dos vértices u, v están 
conectados si y solo si ambos u, v pertenecen al mismo conjunto . 
Los subgrafos son llamados los componentes de G. Si G tiene 
exactamente un solo componente entonces G es conexo, de lo contrario G es inconexo. Se denota al 
número de componentes de G por c(G). 
La noción de conexidad es importante para la aplicación de la teoría de grafos a las ciencias 
sociales; constituye la versión matemática de uno de los aspectos de la noción psicológica de cohesividad 
de grupo; intuitivamente se refiere a la densidad de relaciones. 
2 1 
4 5 
3 
Figura 1.6 (a) Ejemplo de un paseo. (b) Ejemplo de un ciclo. (c) Ejemplo de una trayectoria. 
 
 
5 
4 
1 2 
3 
 (a) 
 
 (b) 
 
 (c) 
 
2 1 
6 
4 5 
3 
13 | Fundamentos de la Teoría de Grafos 
 
Definición. Un grafo G = (V, E) es regular de grado k, si cada vértice tiene grado k; es decir, un 
grafo es regular si todos los vértices tienen el mismo grado. A un grafo que sea por si mismo una 
trayectoria de orden n lo denotaremos por , de igual forma un ciclo de longitud n es llamado un n-ciclo 
y se denota por . Un 3-ciclo es llamado un triangulo. Diremos también que un ciclo es par o impar 
dependiendo de la paridad de su orden. 
Teorema. Un grafo G no trivial es bipartita si y sólo si G no contiene ciclos impares. 
 Demostración. Sea G un grafo no trivial. Supongamos que G es bipartita, por lo tanto 
 particiones tales que se cumple que e es una x-y-arista. Sea un 
ciclo de grado n en G, de no existir el resultado se cumple por vacuidad. 
Supongamos sin pérdida de generalidad que , en consecuencia y así para toda 1 ≤ i 
≤ n, si y sólo si i es impar y si y sólo si i es par. Ahora como y 
entonces , por consiguiente n es par. De aquí concluimos que todo ciclo de G tiene longitud par. 
Para el reciproco supongamos que G no contiene ciclos impares y asumamos de momento que G es 
conexa. Sea , por lo tanto existe una u-v-trayectoria en G, por lo que podemos 
definir a como una de longitud mínima. 
Definamos ahora como el conjunto que contiene a u y a todo vértice tal que 
la longitud de sea par; y a como el conjunto que contiene a todo vértice tal que 
la longitud de sea impar. Por construcción es claro que X y Y son una partición de V (G). Sea 
, veamos ahora que x y y pertenecen a distintos elementos de la partición. Podemos 
suponer sin pérdida de generalidad que , si suponemos que entonces existen , u-x-
trayectoria mínima y , u-y-trayectoria mínima, ambas de longitud par, por lo tanto 
es un ciclo impar en G, lo cual es una contradicción que viene de suponer que 
. De aquí que y como consecuencia toda arista de G es una X-Y-arista. Si G no hubiera sido 
conexa, podemos suponer que las componentes conexas de G, de tal forma que si G no 
(a) (b) 
1 2 
3 4 5 
6 7 
1 
2 3 
4 
5 
6 
7 
Figura 1.7 (a) Grafo conexo y (b) Grafo inconexo 
14 | Fundamentos de la Teoría de Grafos 
contiene ciclos impares, entonces ninguna contiene ciclos impares, por lo que aplicado el proceso 
anterior obtenemos que cada es bipartita. Digamos que las particiones bipartitas de cada 
. Por lo que es claro que son una bipartición de G. 
Definición. Un camino hamiltoniano es una trayectoria que pasa por todos los puntos del grafo. 
Definición. Un circuito hamiltoniano es un camino hamiltoniano que vuelve a su punto de partida. 
Definición. Una arista que une dos vértices de un ciclo, pero no es esta misma una arista del ciclo 
es una cuerda. 
Definición. El diámetro de un grafo es el máximo de las distancias entre cualesquiera par de 
vértices, equivalentemente el contorno de un grafo es el mínimo de las distancias entre cualesquiera par 
de vértices. (si G no tiene un ciclo el valor del su diámetro es ∞ y el de su contorno cero). 
Definición. Dado un grafo G y decimos que v es un vértice de corte si el número de 
componentes de G cumple con , con lo que podemos afirmar que si G es conexa, v es 
vértice de corte si y sólo si es inconexa.Un grafo con vértices de corte se llama separable. 
Definición. Existe una definición análoga para aristas, dada e es un puente si 
> ( ). 
Teorema. Sea G conexo y sea , entonces son equivalentes: 
i) v es un vértice de corte 
ii) partición de V(G – v) tales que T X-Y-trayectoria se cumple que . 
iii) tales que T x-y-trayectoria se cumple que . 
Demostración. Sea G conexa y . 
 Sea v vértice de corte en G. Sabemos por definición que , digamos 
entonces que son las componentes conexas de . Definimos a y 
. 
Sea T una X-Y-trayectoria en G tal que con y , sin 
pérdida de generalidad supongamos que y . Supongamos ahora que , por lo 
tanto T es una X-Y-trayectoria en , más aún T sería una C1 – Ck – trayectoria, de aquí que 
15 | Fundamentos de la Teoría de Grafos 
es conexa, lo cual es una contradicción que viene de suponer que , por consiguiente 
. 
 Sea X, Y una partición de V (G) tal que T X-Y-trayectoria se cumple que . 
Sea y , ahora como toda x-y-trayectoria es una X-Y-trayectoria, entonces toda x-y-
trayectoria contiene a v. 
 Sean tales que T x-y-trayectoria se cumple que . 
Supongamos que es conexa, entonces existe una x-y-trayectoria en , lo cual es una 
contradicción pues todas las x-y-trayectorias pasaban por v y no lo hace. Contradicción que viene de 
suponer que es conexa, de aquí que es inconexa y por lo tanto como G es conexa 
 
Teorema. Sea G conexo con y entonces son equivalentes: 
i) e es un puente. 
ii) V(G) partición de V(G) tales que T X-Y-trayectoria, T pasa por e. 
iii) tales que toda u-v-trayectoria pasa por e. 
iv) e es acíclica. 
Demostración. Sea G conexa con y . 
 Sea e puente y sean las componentes conexas de , definimos X , 
 una partición de V (G). Sea una X- Y- trayectoria en G con 
y por lo tanto si suponemos que T no pasa por e, entonces en tenemos que u estaría 
conectado a v por T y por definición estarían en la misma componente conexa de , lo cual es una 
contradicción. De aquí que T pasa por e. 
 Sea una partición de los vértices de G, tal que T X-Y-trayectoria, T para 
por e. 
Sea y , como toda u-v-trayectoria es una X-Y-trayectoria, entonces toda u-v-
trayectoria pasa por e. 
i Sea tales que toda u-v-trayectoria pasa por e = (x, y) y supongamos que 
ciclo en G tal que . Tomamos a T una u-v-trayectoria tal que 
 una u-v-trayectoria que dependiendo del sentido en el que se recorra a pasa o 
16 | Fundamentos de la Teoría de Grafos 
no por e, si tomamos el caso en el que no lo hace tenemos una u-v-trayectoria que no pasa por e, lo cual 
es una contradicción que viene de suponer que e estaba en algún ciclo. Por lo que e es acíclico. 
i Por contrapuesto si e = (x, y) no es un puente, entonces en hayuna x-y-trayectoria 
digamos T. Por lo tanto es un ciclo en G que contiene a e. 
Definición. Dado un grafo G con definimos la conexidad puntual de G, denotada por , 
como el mínimo número de vértices necesarios para que, al quitarlos de G, ésta se desconecte o 
lleguemos al grafo trivial con un solo vértice. Decimos entonces que es un bloque si y B 
es un subgrafo máximo por contención con esta propiedad. Es claro que dos bloques pueden 
intersectarse a lo más en un vértice de corte, ya que si lo hicieran en dos o más, la unión , tendría 
también conexidad puntual mayor o igual a 2, contradiciendo la maximidad de y . Llamaremos 
bloque terminal a un bloque que tenga un solo vértice de corte. 
Definición. Un árbol es un grafo conexo sin ciclos, esto es que cada arista de un árbol represente 
un puente. Diremos que un grafo (conexo o inconexo) es un bosque si es un grafo acíclico. De modo que 
toda componente conexa de un bosque es un árbol. Llamaremos también árbol (bosque) generador de un 
grafo G a un subgrafo generador que sea un árbol (bosque). Veremos ahora una propiedad importante que 
tienen estos grafos: 
 
Teorema. Un árbol de orden p tiene tamaño p – 1 
Demostración. Por inducción sobre p. Como es el único árbol con p = 1 se cumple la base de 
inducción. 
Sea T árbol con y supongamos que el resultado se cumple para toda k < p. Sea , 
por lo que sabemos que e es un puente, de aquí que T – e tiene exactamente dos componentes conexas, 
Figura 1.8 (a) Ejemplo de un árbol. (b) Vértices terminales del mismo árbol. 
(b) (a) 
17 | Fundamentos de la Teoría de Grafos 
digamos árboles con y como su órdenes y tamaños. Como por hipótesis de 
inducción tenemos que con . 
Sabemos también que y por lo tanto: 
 
Por inducción tenemos que el tamaño de un árbol es su orden menos uno. 
Teorema. Todo árbol no trivial contiene al menos dos vértices terminales. 
Demostración. Sea T árbol con orden p, tamaño q y ordenados de tal 
forma que si . 
Ahora si suponemos que no existen 2 vértices con grado uno entonces se cumple que 
 y , por lo tanto: 
 
Sin embargo por el teorema anterior y como la suma de los grados de un grafo G es igual a dos 
veces su tamaño tenemos que: 
 
Por lo tanto: 
 
Lo cual es una contradicción con la primera desigualdad que viene de suponer que T no contenía al 
menos 2 vértices terminales. 
Sabemos que en un grafo conexo dados dos vértices existe una trayectoria que los une, sin embargo 
en árboles podemos decir un poco más: 
Teorema. Dado T árbol, si , entonces T contiene una única u-v-trayectoria. 
18 | Fundamentos de la Teoría de Grafos 
Demostración. Sea T árbol y sean . Supongamos que existen P y Q dos u-v-trayectorias 
distintas, por lo tanto existe un vértice tal que el vértice que sigue después de x en P 
sea distinto del que le sigue en Q, y sea y el primer vértice en P, después de x, que también esté en Q. 
 
De aquí que podamos construir el siguiente ciclo lo cual es una 
contradicción que viene de suponer que existían dos u-v-trayectorias distintas en T. 
Definición. Un árbol de expansión de un digrafo de n vértices es un grupo de n-1 aristas que 
conecta todos los vértices. Todo vértice es alcanzable desde cualquier otro vértice. En digrafos, los 
vértices no tienen una dirección asociada. Un grafo puede tener varios árboles de expansión 
 
Propiedades de los árboles de expansión: 
 No contienen ciclos – un ciclo necesita n aristas en un grafo de n-vértices. 
 Existe exactamente un camino entre dos vértices cualquiera – existe por lo menos un camino 
entre cualesquiera dos vértices ya que todos los vértices están conectados. Más aún, no hay más de un 
camino entre un par de vértices. 
 Añadir una arista que no pertenece al árbol crea un ciclo – Supongamos una arista que no 
pertenece al árbol (x, y), la arista añadida y el camino en el árbol. De aquí que exista un ciclo. Por 
ejemplo, si añadimos una arista (A, D) al árbol de expansión mostrado en la parte final de la figura 
anterior, entonces tendremos un ciclo (A, B, D, A). 
C D 
B A 
C D 
B A 
C D 
B A 
C D 
B A 
C D 
B A 
Figura1.10 Dígrafo y cuatro de los árboles de expansión del grafo. 
y x v u 
. . . 
. . . 
. . . 
. . . 
P 
Q 
Figura 1.9 Se observan las 2 u-v-trayectorias y el ciclo que se forma al suponer que son distintas. 
19 | Fundamentos de la Teoría de Grafos 
 
 Remover una arista de un ciclo como el anterior crea un árbol de expansión. Después de 
remover la arista existirán (n – 1) aristas. Todos los vértices del grafo estarán conectados: supongamos 
que la arista (x, y) que pertenece al grafo original es removida. Los vértices x y y estarán aún conectados 
porque x y y estuvieron en un ciclo. Para otro par de vértices, en el camino del grafo original remplaza la 
arista (x, y) por el camino entre x y y. 
 Al remover la arista (B, D) del ciclo (A, B, D, A) se crea un árbol de expansión. 
Los árboles de expansión tienen aplicaciones en el diseño de redes de comunicación. Si los vértices 
representan ciudades y las aristas distancias y necesitáramos colocar líneas eléctricas entre cada ciudad 
estos serían un buen modelo, los árboles de expansión también son útiles en problemas de rutas (rutas del 
correo, camiones escolares, vendedores viajeros, etc.). 
 
Figura1.11 Añadir una arista que no pertenece al árbol crea un ciclo. 
Al añadir la 
arista (A, D) 
C D 
B A 
C D 
B A 
Al remover la 
arista (B, D) 
C D 
B A 
C D 
B A 
Figura1.12 Remover una arista del grafo crea un árbol de expansión 
a) No es un árbol de expansión b) Árbol de expansión 
20 | Fundamentos de la Teoría de Grafos 
Digrafo etiquetado y ponderado 
Cuando estamos trabajando con digrafos con pesos heterogéneos en las aristas, debemos precisar de 
mejor manera algunas de las definiciones. 
Definición. Un grafo G es etiquetado si sus aristas y/o vértices tienen asignado alguna 
identificación. 
Definición. Un grafo G es ponderado si a cada arista e de G se le asigna un número real w(e) 
denominado peso o longitud de e. 
 
La matriz de pesos del Digrafo etiquetado y ponderado quedaría de la siguiente forma, donde si 
 y tendremos que 
 
Definición. Sea un digrafo con una función de pesos en las aristas . Esta 
función asigna a cada arista un peso que, en general, puede ser un número real y puede ser negativo 
 
 
4 
3 
4 
2 
1 
5 
6 
3 
8 
2 
10 
6 
3 
9 
1 
3 
1 
2 
4 
Figura 1.13 Digrafo etiquetado y ponderado 
21 | Fundamentos de la Teoría de Grafos 
Definición. El peso de un camino , está dado por: 
 
Definición. El peso de un camino más corto o distancia es: 
 
 
Propiedad: Sea un camino de a que pasa por . Entonces 
. 
Lema. Sub-caminos de caminos más cortos, son caminos más cortos. Dado un digrafo ponderado 
 con función de pesos , sea el camino más corto del vértice al 
vértice y para cualquier i y j tal que , sea del sub-camino de W del 
vértice al vértice . Entonces, es un camino más corto de a . 
Demostración. Si descomponemos el camino W en , entonces tendremos 
que . Ahora, asumamos que existe un camino desde hacia 
con peso . Entonces, es un camino desde hacia cuyo 
peso es menor que , lo que contradice la asunción de que p es un 
camino más corto desde hacia . 
6 
 
1 
1 
1 
2 
2 
3 
4 
4 
7 
9 
9 
1 
1 
2 
2 
3 5 6 
8 
9 7 
Figura1.14 Camino de peso mínimo o distancia entre y . 
22 | Fundamentos de la Teoría de Grafos 
Definición. es un árbol de caminos más cortos si cumple con: 
i. son los vértices para los cuales 
ii. es un árbol dirigido con raíz en s. 
iii. es tal que 
 
 
Capítulo 2 
Introducción al Análisis de 
Algoritmos 
Conceptos Básicos 
 
Un algoritmo, llamado así por el erudito del siglo XIX Abu Jafar Muhammad Ibn Musu Al-
Khowarizmi, es definido en forma general como sigue: 
Un conjunto de reglas e instrucciones bien definidas finitaspara obtener un resultado a partir de un 
conjunto específico de argumentos en un tiempo finito. El uso de algoritmos se ha incrementado 
ampliamente con la evolución de los sistemas de cómputo, pero tiene las siguientes características: 
Entrada: El algoritmo trabaja a partir de una entrada (o datos). Excepcionalmente, el algoritmo 
trabajará a partir de 0 entradas. 
Salida: El algoritmo produce una salida (resultado), que corresponde a la solución del problema 
planteado. 
Secuencia finita de pasos: El algoritmo define una secuencia de pasos cuya ejecución transforma a 
la entrada en la salida. 
Definición precisa: Cada uno de estos pasos debe estar bien definido y tener un nivel adecuado de 
detalle. 
Terminación: El algoritmo debe siempre terminar su ejecución proporcionando una solución 
correcta. 
El algoritmo más famoso en la historia, data de tiempos de antes de los antiguos Griegos, este es el 
algoritmo de Euclides para calcular el máximo común divisor de dos enteros. 
Para trabajar con un algoritmo debemos cubrir dos aspectos. El primero de ellos consiste en 
demostrar la correctez del algoritmo, esto es, que el algoritmo termina y produce la solución correcta 
frente a cualquier ejemplar del problema. La segunda consiste en hacer el análisis del algoritmo. 
24 | Introducción al Análisis de Algoritmos 
Correctez de un algoritmo 
Las demostraciones de correctez de un algoritmo generalmente se hacen por inducción en el 
número de veces que se repiten los enunciados del algoritmo, o si el algoritmo trabaja de manera 
recursiva, por una fórmula que contempla el costo de cada invocación. Debemos encontrar una 
invariante, que se refiere a predicados que deben ser verdaderos antes de que se inicie la ejecución (la 
base de inducción) y al terminar la ejecución. Generalmente se demuestra que si en el ciclo k el predicado 
se evalúa a verdadero, con las operaciones que se ejecutan en el ciclo, el predicado seguirá siendo 
verdadero en el ciclo k + 1 (paso inductivo). No es tan difícil encontrar esa invariante, pues tiene que ver 
con la manera en que describimos la salida del algoritmo. 
Todos los algoritmos que resuelven un determinado problema pueden no resultar iguales, porque 
alguno de ellos puede resultar más rápido que otros. Por lo tanto, se está en la necesidad de encontrar 
patrones que indiquen cuando un algoritmo es mejor que otro y porque. Para esto se introduce el 
concepto de complejidad computacional. 
La complejidad de un algoritmo mide la cantidad de esfuerzo computacional que se requiere para 
resolver un problema utilizando un algoritmo. 
El diseño de buenos algoritmos requiere creatividad e ingenio y no existen, en general, reglas para 
diseñar algoritmos. Es decir, no existe un algoritmo para diseñar algoritmos. 
Existen varios algoritmos para resolver un mismo problema, la pregunta es ¿cuál es el “mejor”?. El 
mejor es aquel que utilice los mínimos recursos informáticos para llevar a cabo la tarea determinada. 
Tiempo: Utilizando el tiempo empleado por el algoritmo como medida de eficiencia del mismo, 
aunque en general deben tenerse en cuenta los recursos que emplea para obtener la solución. 
Se define como un instante al caso particular de un problema con datos específicos para todos los 
parámetros del problema. Teniendo en cuenta que un algoritmo podrá resolver rápidamente determinados 
casos particulares de un problema y tardar demasiado en la resolución de otros. 
Las diferentes instrucciones típicas de un algoritmo son instrucciones de asignación, aritmética y 
lógicas. El número total de las mismas resulta de la suma de todas las instrucciones definidas 
anteriormente y determina el tiempo requerido en la ejecución del algoritmo. Es importante hacer notar 
que estamos suponiendo que cada una de estas instrucciones toma una cantidad constante de tiempo, 
independientemente del tamaño de la entrada y que es el mismo para todas las operaciones. Esto en 
general no va a ser cierto. 
25 | Introducción al Análisis de Algoritmos 
Si el tiempo de ejecución es demasiado grande, puede suceder que el algoritmo sea en la práctica 
inútil, pues el tiempo necesario para su ejecución puede sobrepasar el tiempo disponible del ordenador. 
Espacio: La complejidad de espacio de un algoritmo (para una entrada dada) es el número de 
objetos elementales que este algoritmo necesita almacenar durante su proceso de ejecución. El espacio 
ocupado por un algoritmo es determinado por el número y tamaño de las variables y estructuras de datos 
usadas por el algoritmo. En ocasiones se tendrá que hacer un balance entre tiempo y espacio, ya que para 
reducir el tiempo se requerirá de más espacio y viceversa. Esta situación es referida como negociación 
tiempo-espacio. 
La característica de los problemas de optimización combinatoria de tener un conjunto numerable de 
soluciones, hace que la obtención de la mejor solución sea un problema que podría tener poco interés 
matemático. Sin embargo es frecuente que este tipo de problemas tengan n! soluciones factibles. 
Si un ordenador puede examinar soluciones por segundo podría terminar su tarea para: 
n = 20 en unos 800 años 
n = 21 en cerca de 16,800 años 
Un algoritmo se considera eficiente si y solo si es polinomial. 
Definición. Un algoritmo es polinomial si el número de operaciones elementales necesarias para 
resolver un ejemplo de tamaño n está acotado por una función polinomial en n. 
Notación para expresar complejidad en tiempo 
(complejidad asintótica) 
El análisis asintótico es un medio de comparar el rendimiento relativo. La complejidad en tiempo 
de un algoritmo se ocupa de determinar una expresión del número de operaciones primitivas necesitadas 
como una función del tamaño del problema. Ya que la medida de contar el número de iteraciones es algo 
difícil, el propósito no es obtener una cuenta exacta del número de iteraciones, más bien, lo que se busca 
es encontrar cotas asintóticas de la cuenta de iteraciones. 
El análisis asintótico hace uso de la notación de Landau: O(O mayúscula) y o(o – minúscula). 
Otras notaciones también son usadas en el análisis de algoritmos como son: 
 y . 
26 | Introducción al Análisis de Algoritmos 
La tasa u orden de crecimiento del tiempo que toma un algoritmo , se considera que es un 
algoritmo más eficiente que otro, si el tiempo que toma su peor caso tiene menor orden de crecimiento. 
La notación representa que está acotando a la función por arriba, es decir que la está 
acotando en el peor de los casos. 
Definición. Se dice que una función es de orden si y solo si se cumple que existen 
unas constantes positivas c y , ambas independientes de n, tales que: 
 
Decidir que es de orden supone que cg(n) es una cota superior del algoritmo. Es 
decir que f no crece más rápido que g. Diremos también que f y g tienen el mismo orden si 
 y . Para estimar la bondad de los distintos algoritmos, se utilizará el análisis 
del peor caso, un estudio experimental de los algoritmos suministra información importante para su 
utilización práctica, dependiendo del instante del problema que se ha de resolver. 
El tiempo de ejecución de un algoritmo depende de la naturaleza y tamaño de la entrada. Una 
función temporal de la complejidad de un algoritmo es una función del tamaño del problema y especifica 
el tiempo máximo que se necesita para resolver un instante de un tamaño dado. Es decir, la función 
temporal de complejidad da una medida de la proporción en que se incrementa el tiempo de resolución 
con respecto a un incremento en el tamaño del problema. Se refiere a la función temporal de complejidad 
del peor caso de un algoritmo como su cota del peor caso (una cota superior del tiempo invertido). 
La notación O mayúscula tiene unas cuantas implicaciones. La complejidad de un algoritmo es una 
cota superior de tiempo de ejecución del algoritmo para valores de n lo suficientemente grandes. Más 
aún,esta notación indica solo los términos más dominantes en el tiempo de ejecución y representa el 
hecho de que para una n grande, los términos con un crecimiento menor tienden a ser insignificantes si se 
compara con el término de mayor crecimiento. 
Por ejemplo, si el tiempo de ejecución de un algoritmo es , entonces para 
todo el segundo término domina al primer término y para todo el tercer término 
domina al segundo término. Así, la complejidad del algoritmo es . Otra importante implicación de 
ignorar las constantes en el análisis de la complejidad es que se asume que las operaciones elementales, 
tales como la suma, multiplicación, asignación y operaciones lógicas, requieren una misma cantidad de 
tiempo. Se dice que un algoritmo es bueno si la complejidad del peor caso está acotada por una función 
polinomio de los parámetros del problema. 
27 | Introducción al Análisis de Algoritmos 
El siguiente ejemplo ilustra que es , para cuando 
Sea y 
Para y 
Verificamos lo anterior al sustituir , entonces tendríamos 
 
 
Para una n suficientemente grande, tiene una cota superior de 
Se escribe 
 
Un algoritmo que cumpla esto es llamado algoritmo polinomio y un algoritmo polinomio se dice 
que es fuertemente polinomio si su complejidad está acotada por una función polinomial en n y m y no 
aparecen las expresiones log(C) o log(U). En caso contrario se dice que el algoritmo es débilmente 
polinomial. 
La notación de representa que se está acotando asintóticamente a la función por 
abajo, lo que significa que está acotando a en el mejor de los casos. 
Definición. Se dice que una función es de orden si y solo si existen unas 
constantes positivas c y tales que: 
 
Decir que es supone que cg(n) es una cota inferior del algoritmo. 
Ejemplo: El mejor caso en tiempo de ejecución del ordenamiento por inserción (cuando el arreglo 
de entrada se encuentra ordenado previamente) es . El peor caso del ordenamiento por inserción 
(cuando el arreglo se encuentra en orden inverso) es . Por lo que el tiempo de ejecución del 
ordenamiento por inserción cae entre y , ya que cae entre una función lineal de n y una 
función cuadrática de n. 
La notación de representa que esta acotando a la función por los extremos, lo que 
significa que está acotando a tomando en cuenta el mejor caso y el peor caso en ese rango. 
Se dice que una función es si y solo si se cumple que existen unas constantes 
positivas y , tales que: 
 
28 | Introducción al Análisis de Algoritmos 
La notación es más precisa que las notaciones y , ya que es si y 
solo si es a la vez una cota inferior y superior de . 
Definición. Sean y funciones reales definidas para toda (donde n0 es un 
número positivo real fijo). Se dice que si y solo si 
El Valor de n0 no dependerá de n, pero podría depender de c. Por ejemplo, pero 
. La notación o-minúscula es como O-mayúscula, pero nos da una cota superior que no es 
asintóticamente justa. 
Definición. Sean y funciones reales definidas para toda (donde n0 es un 
número positivo real fijo). Se dice que si y solo si 
Lo anterior quiere decir que si , entonces la razón de crecimiento de es 
mayor que la razón de crecimiento de . 
Funciones de Complejidad en tiempos más 
usuales 
Las funciones de complejidad algorítmica más usuales, ordenadas de mayor a menor eficiencia 
(tiempo de ejecución) son: 
: Complejidad constante. El tiempo de ejecución del algoritmo es constante. 
Ejemplo: Obtener un elemento de un arreglo, dado su índice. Ya que el índice provee acceso 
directo al arreglo, el tiempo que toma en completar la tarea es independiente del tamaño n del 
arreglo. 
: Complejidad logarítmica. Esta complejidad suele aparecer en determinados algoritmos 
con iteración o recursión no estructural, es lograda al dividir el problema en segmentos más 
pequeños y solo analizar un elemento de entrada en cada segmento. 
Ejemplo: Algoritmo de búsqueda binaria (Binary search). 
: Complejidad lineal. Es en general, una complejidad buena y bastante usual. Suele aparecer 
en la evaluación de un bucle simple cuando la complejidad de las operaciones interiores es constante o en 
algoritmos con recursión estructural. 
29 | Introducción al Análisis de Algoritmos 
Ejemplo: Encontrar el elemento mínimo en un arreglo. 
: Complejidad lineal – logarítmica: Típicamente alcanzada al dividir el problema en sub-
problemas, resolviendo estos de forma independiente y después combinando los resultados. A diferencia 
de los algoritmos de complejidad logarítmica, cada elemento en los sub-problemas debe ser examinado. 
Ejemplo: Algoritmo de ordenamiento por intercalación o mezcla (Merge sort). 
: Complejidad cuadrática. Aparece en bucles o recursiones doblemente anidados. Aparece 
cuando tenemos que examinar todos los pares de elementos de datos. 
Ejemplo: Algoritmo de ordenamiento por selección (Selection sort). 
: Complejidad cúbica. Aparece en bucles o recursiones triples. Para un valor grande de n 
empieza a crecer en exceso. 
Ejemplo: Multiplicación de matrices - Cada elemento de la matriz resultante es obtenido al 
multiplicar dos vectores de tamaño n. Esto requiere un tiempo n. Ya que existen n2 elementos en la matriz 
resultante, toma un tiempo de n3 computar la matriz resultante completa. 
: Complejidad polinómica. Si k crece, la complejidad del programa es mala. 
: Complejidad exponencial. Debe evitarse en la medida de lo posible. Puede aparecer en un 
subprograma recursivo que contenga dos o más llamadas internas. En problemas donde aparece esta 
complejidad suele hablarse de explosión combinatoria. Cualquier función exponencial con una base 
mayor a uno crece más rápidamente que cualquier función polinomio. Los números Fibonacci crecen 
exponencialmente. 
Ejemplo: Resolver el problema de la sub-secuencia más larga mediante el enfoque de fuerza-bruta. 
Algunos ejemplos de cotas polinomiales son y algunos débilmente 
polinomiales como . 
Se dice que un algoritmo es exponencial en tiempo, si su ejecución no puede ser acotada 
polinomialmente por la longitud de la entrada. 
Algunos ejemplos son 
Se dice que un algoritmo es pseudopolinomial si su tiempo de ejecución es polinomicamente 
acotado en n, m, C y U. 
Algunos ejemplos son y 
30 | Introducción al Análisis de Algoritmos 
Tipos de Algoritmos 
La Teoría de la Complejidad estudia la manera de clasificar algoritmos como buenos o malos y de 
clasificar problemas de acuerdo a la dificultad inherente de resolverlos. 
Algoritmos Determinísticos: Tiene la propiedad de que el resultado de cada operación, se define en 
forma única. En otras palabras nos garantizan en cada paso la solución. 
Algoritmos No Determinísticos: Tiene la propiedad de que el resultado de una o varias operaciones, 
se determina dentro de un conjunto especificado de posibilidades. En otras palabras están adivinando en 
cada paso la solución pero no garantizan llegar a la solución óptima en el mejor de los casos. 
Para determinar si los algoritmos son buenos o malos se determinaron las siguientes convenciones: 
1. Todos los algoritmos, desde constantes hasta polinomiales, son polinomiales. 
2. Todos los algoritmos exponenciales y factoriales, son exponenciales. 
3. Los algoritmos polinomiales son “buenos” algoritmos. 
4. Los algoritmos exponenciales son “malos” algoritmos. 
Por lo tanto los problemas los podemos clasificar como: 
a) Fáciles si su método de solución cuyo tiempo de ejecución en una computadora crece 
de forma “razonable” o polinomial. 
b) Difíciles si no existe algoritmo. 
Realizar la determinación anterior se denomina establecer la complejidad computacional del 
problema. Hay razones para preferir algoritmos polinomiales a algoritmos exponenciales. Las funciones 
de complejidad exponencial tienen un crecimiento explosivo y en general resuelven solo pequeños 
problemas. 
Complejidad de los problemas 
Dependiendo de los requerimientosdel problema se pueden clasificar de la siguiente forma: 
1. Problemas de búsqueda: Encontrar un valor, en los datos de entrada, que satisfaga una 
propiedad. 
2. Problemas de estructura: Transformar los datos de entrada para satisfacer una propiedad. 
3. Problemas de construcción: Construir un valor que satisfaga una propiedad. 
31 | Introducción al Análisis de Algoritmos 
4. Problemas de optimización: Encontrar el mejor valor, en los datos de entrada, que satisfaga 
una propiedad. 
5. Problemas de decisión: Decidir si una entrada satisface o no una propiedad. 
6. Problemas adaptativos. Mantener una propiedad todo el tiempo. 
Podemos clasificar los problemas en cuatro clases de acuerdo a su grado de dificultad: 
1. Problemas indecidibles. Son aquellos problemas para los cuales no se puede escribir un 
algoritmo. Por ejemplo, se ha probado que un programa que se detendrá en una Máquina de Turín (1937) 
es de esta clase. El problema de Turing al igual que el décimo problema de Hilbert y el de programación 
cuadrática en enteros, son problemas de este tipo, es decir que no sólo no existe un algoritmo polinomial 
para su solución sino que no existe algoritmo. 
2. Problemas intratables (problemas que se demuestran que son difíciles). Son aquellos 
problemas para los cuales no se pueden desarrollar algoritmos polinomiales. En otras palabras, sólo se 
pueden resolver con algoritmos exponenciales. 
3. Problemas NP (donde NP se entiende por Polinomial no Determinístico). Esta clase incluye 
problemas que se pueden resolver en tiempo polinomial si podemos adivinar correctamente que ruta 
computacional se puede seguir. El concepto de adivinar es extraño ya que todos los programas 
computacionales son Determinísticos. En general, esta clase incluye todos los problemas que tienen 
algoritmos exponenciales pero que no se ha probado que no se puedan resolver con algoritmos de tiempo 
polinomial. 
4. Problemas P (donde P se entiende por polinomial). Esta clase incluye todos los problemas 
que tienen algoritmos de tiempo polinomial. Se pueden considerar como una subclase de la clase anterior. 
Un problema se dice polinomial si existe un algoritmo para el cual el tiempo requerido para su solución, 
está acotado por una función polinomial del tamaño del problema (donde entendemos por tamaño como 
la longitud de un código). Se tiene así por ejemplo que en un grafo G (V, E) donde y , 
un problema de la ruta más corta se encuentra a lo más en un tiempo , un flujo máximo en un 
tiempo , un árbol de peso mínimo en un tiempo . Sin embargo no todos los problemas 
combinatorios son polinomiales. 
5. Problemas NP-completos: Subconjunto de problemas NP que son los más difíciles de 
resolver. Se dice que un problema pertenece a esta clase si cada problema de la clase NP puede reducirse 
en tiempo polinomial a este. 
32 | Introducción al Análisis de Algoritmos 
El siguiente ejemplo nos dejará más claro cómo funciona y como se describe un algoritmo, en éste 
encontraremos el mínimo dentro de una lista de elementos de un orden parcial. 
Algoritmo del mínimo elemento y su posición en una lista. 
[Dado un listado de elementos de un orden parcial, encuentra el mínimo y lo 
despliega junto con su ubicación en la lista.] 
1. [La variable MIN representa el “primer elemento” actual] 
 
2. [Declara la variable p que nos dará la ubicación del elemento deseado] 
 
3. [Para cada elemento de la lista, distinto de , si el elemento es menor que 
MIN, entonces MIN es remplazado por y p por k. 
 
 
 
 
4. Desplegar MIN y p. 
Como este algoritmo hace n-1 comparaciones, es claro que su complejidad es n -1 = O(n), por lo 
que es polinomial y eficiente. 
Comparación de Algoritmos 
Se comparará la eficiencia de dos algoritmos utilizados para encontrar, si aparece y de ser así 
dónde, una palabra dentro de una lista ordenada alfabéticamente. Usaremos la relación a < b para indicar 
que la palabra a, alfabéticamente, se encuentra antes que la palabra b. 
El primer algoritmo llamado algoritmo secuencial de búsqueda realiza la búsqueda de la manera 
más lógica, empezando desde el principio, compara cada palabra de la lista con la palabra buscada, si la 
encuentra detiene el proceso y avisa que la palabra existe en la lista, si recorre toda la lista y no la 
encuentra despliega que no fue encontrada. 
 
33 | Introducción al Análisis de Algoritmos 
Algoritmo secuencial de búsqueda. 
[Determina si la palabra dada LLAVE aparece en un listado de palabras 
ordenado alfabéticamente, si aparece desplegar la posición] 
1. [Si la k-ésima palabra de la lista es LLAVE su ubicación es desplegada y el algoritmo 
termina]. 
Para k = 1 hasta n 
 
 desplegar k y detener 
 
2. Desplegar “no se encontró” 
Es claro que el algoritmo necesitará hacer n comparaciones antes de terminar en el peor de los 
casos, es decir, cuando la palabra no se encuentre en la lista. Por lo tanto la complejidad de este algoritmo 
es . 
El siguiente algoritmo lleva el nombre de Algoritmo Binario de Búsqueda, para esto definamos lo 
que es el piso de un número real x, denotado por , como el máximo entero menor que x. Con esto 
podemos describir el algoritmo formalmente como sigue: 
Algoritmo Binario de Búsqueda. 
[Determina si la palabra LLAVE aparece en un listado de palabras 
ordenado alfabéticamente, si lo aparece despliega donde.] 
1. [j y k representan la primera y la última palabra de la sublista siendo considerada. 
Inicialmente j = 1 y k = n] 
1.1 j = 1 
1.2 k = n 
 
2. [W (m) es la palabra a la mitad entre W (j) y W (k).] 
Mientras j<k hacer 
a) 
b) [Si la m-ésima palabra es LLAVE despliega su ubicación y el algoritmo termina] 
c) [Si LLAVE está antes alfabéticamente que W (m), entonces la nueva sublista se tomará 
entre W (j) y W (m – 1)] 
Si LLAVE < W (m), entonces k = m – 1 
34 | Introducción al Análisis de Algoritmos 
d) [Si LLAVE está después alfabéticamente que W (m), entonces la nueva sublista se tomará 
entre y ] 
Si LLAVE > W (m), entonces j = m + 1. 
 
3. Desplegar “no se encontró” 
Para determinar la complejidad de este algoritmo observemos que los pasos uno y tres sólo se 
realizan una vez por lo que su orden es constante . Ahora en el paso dos es claro que el mayor 
número de iteraciones se dará si la palabra no se encuentra en la lista. 
Llamemos B(n) al número de iteraciones del paso 2, como después de realizar este paso por primera 
vez habrá una lista con a lo más palabras a considerar, entonces 
 
Demostraremos ahora por inducción fuerte que 
 
Si n = 1 es claro que la desigualdad se da. 
Supongamos ahora que la desigualdad anterior se cumple para todo entero n con , 
probaremos entonces que 
 
Por la primera desigualdad 
 
Sin embargo por Hipótesis Inductiva 
 
Por lo tanto: 
 
Por consiguiente . Como en cada iteración del paso 2 sólo se hacen dos 
comparaciones y dos asignaciones, el orden de cada una es constante. Por lo que la complejidad 
resultante del paso 2 es . 
35 | Introducción al Análisis de Algoritmos 
Algoritmos de exploración en grafos 
Uno de los problemas fundamentales con grafos son las distintas maneras que tenemos de 
garantizar que todos los vértices de un grafo (o que todas las aristas) son alcanzados, con un cierto 
objetivo en mente. Esto tiene muchas aplicaciones, como puede ser contar el número de aristas presentes 
en un grafo, verificar que todas las conexiones en una red de computadoras están funcionando, etc. 
Definición. La exploración de un grafo significa visitar cada uno de sus vértices exactamente una 
vez. Esto es cumplido al visitar los vértices de una forma sistemática. 
Los algoritmos de exploración que vamos a revisar tienen todos un funcionamiento local; esto es, 
para llevar a cabo la exploración no es necesario tener presente toda la gráfica, sino únicamente, en cada 
momento, al vértice desde el que se hace la exploración en esa iteración, junto con los vecinos de