Repblica Bolivariana de Venezuela Ministerio del Poder Popular para la Defensa Nacional Universidad Nacional Experimental de La Fuerza Armada Nacional Sede Caracas Ncleo Chuao Ingeniera de Sistemas Ciclo Profesional 6 semestre Ctedra: Teora de Grafos Profesor: Ing. Gustavo Pez

Aplicaciones de la Teora de GrafosMetrocable, Expresos Occidente y Aeroexpresos Ejecutivos

Realizado por: Barreto E. Daniel De Sousa Juan C. De Sousa Maurdys Fernndez Fernando Velsquez Orlando

18/01/2010

1

IntroduccinEn el presente trabajo no discutiremos conceptos de la teora de grafos como tal, ya que lo hemos cubierto totalmente en la Unidad I de esta materia. Lo que s hemos de tomar en cuenta como principales factores para esta entrega, es la aplicacin de esta teora en empresas estatales y privadas en Venezuela del sector transporte. Hemos realizado un estudio sobre las rutas, como es el grafo de stas, como mejoraramos esta distribucin de las mismas y en general que factores de las mismas podemos destacar o cambiar. Esperamos las sugerencias que nos realicen quienes corrigen y leen este documento. Es para nosotros como estudiantes de la UNEFA y como ingenieros en formacin una muy importante labor el tomar en cuenta crticas constructivas que nos dirijan en la bsqueda de nuestra meta fundamental: el xito.

Los autores.

2

ContenidoMetro-Cable de Caracas..........................................................4Grafo del sistema......................................................................4 Son ptimas las rutas?.............................................................5 Qu mejoras se le puede aplicar a las rutas?............................5

Aeroexpresos ejecutivos.........................................................6Rutas........................................................................................6 Grafo del sistema......................................................................6 ................................................................................................6 Son ptimas las rutas?.............................................................9 Qu mejoras se le puede aplicar a las rutas?............................9

Expresos Occidente...............................................................10Rutas......................................................................................10 Grafo del sistema....................................................................10

............................................................................................10Son ptimas las rutas?...........................................................13 Qu mejoras se le puede aplicar a las rutas?..........................13

3

Metro-Cable de CaracasGrafo del sistema

Orden del grafo El orden de este grafo es de 5. Conjuntos de nodos y de lados Nodos = {Parque Central, San Agustn, Hornos de Cal, La Ceiba, Los Manguitos} Lados = {1, 2, 3, 4} Es un grafo simple o mltiple? Es un grafo simple ya que no posee lados mltiples o paralelos ni lazos o bucles. Es grafo dirigido o no dirigido? Es no dirigido, puesto que cada lado contribuye con dos grados, la suma de los grados de los vrtices de G es dos veces el nmero de lados de G. Grado de los vrtices El grado de sus vrtices es 4. Matrices adjuntas al grafo Matriz de incidencia Matriz de adyacencia Matriz de alcance

1. Es un grafo libre? No es un grafo libre porque la condicin que requiere para que sea as es que no posea aristas, caso contrario a este grafo que si las posee. Es un grafo completo? Es un grafo completo gracias a que todas sus aristas conectan cada par de vrtices, en este caso cada modulo perteneciente a cada estacin es 4

denotado como un nodo y cada traza o recorrido del metro-cable sern las aristas que los conecten. Tiene bucles? No tiene bucles porque no hay alguna arista que conecte un vrtice consigo mismo. Tiene ciclos? No posee bucles ya que no es un grafo que posea un camino cerrado, que recorra todos los nodos, pasando una y solo una vez por cada uno excepto el primero que sera su inicio y fin. Es un grafo Euleriano? Es euleriano gracias a que recorre todos los vrtices del grafo pasando una y slo una vez por cada arco (arista) del grafo. Es un grafo Hamiltoniano? No es hamiltoniano ya que al no poseer ciclos no cumple con la restriccin de ser un camino cerrado cuyo punto inicial sea el mismo en el cual culmine. Es un grafo plano? Es un grafo plano porque puede representarse en el plano cartesiano y sus lneas no se cruzan entre s. Es un grafo bipartito? Tambin es bipartito ya que su estructura es lineal. Cul es su nmero (polinomio) cromtico? El nmero cromtico que este grafo posee es 2. (nodos)

Son ptimas las rutas?Las rutas es este proyecto fueron trazadas debido a las necesidades que padeca la comunidad en cuanto a su movilizacin debido al alto flujo de personas, es por ello q cada uno de los mdulos u estaciones fue posicionado donde ocurriera la mayor afluencia de personas en las zonas ms cntricas de esta parroquia, por esta razn encontramos el desarrollo de las vas de este proyecto bastante optimas.

Qu mejoras se le puede aplicar a las rutas?Estas rutas estn totalmente optimizadas, la nica sugerencia al respecto es disminuir el tiempo en que llegan las cabinas a las estaciones del sistema pero hace falta verificar mediante el funcionamiento si el tiempo actual (27 seg.) es suficiente o implica demora en el servicio debido a la insuficiencia.

5

Aeroexpresos ejecutivosRutasOrigenBarquisime to Cd Bolvar Caracas El Tigre Maracaibo Maracay Maturn Pto La Cruz Pto Ordaz San Flix Valencia

DestinoCaracas, Maracaibo, Pto La Cruz, Valencia Caracas, El Tigre, Pto Ordaz, San Flix Barquisimeto, Cd Bolvar, El Tigre, Maracaibo, Maracay, Maturn, Pto La Cruz, Pto Ordaz, San Flix, Valencia Cd Bolvar, Caracas, Maracay, Pto Ordaz, San Flix, Valencia Barquisimeto, Caracas, Maracay, Valencia Barquisimeto, Caracas, El Tigre, Maracaibo, Maturn, Pto La Cruz, Pto Ordaz, Valencia Caracas, Maracay, Valencia Barquisimeto, Caracas, Maracay, Valencia Cd Bolvar, Caracas, El Tigre, San Flix, Valencia Cd Bolvar, Caracas, Pto Ordaz Barquisimeto, Caracas, El Tigre, Maracaibo, Maracay, Maturn, Pto La Cruz, Pto Ordaz

Grafo del sistema

Orden del grafo El grafo es de orden n = 11. Es decir tiene 11 nodos. Tiene en total 29 lados. Conjuntos de nodos y de lados El conjunto de nodos est conformado por los elementos del conjunto V y el conjunto de lados est conformado por los elementos del conjunto E.

G = Barquisimeto, Cd Bolvar, Caracas, El Tigre, Maracaibo, Maracay, Maturn, Pto La Cruz, Pto Ordaz, San Flix, Valencia6

V = Barquisimeto Caracas; Barquisimeto Maracaibo; Barquisimeto Puerto La Cruz; Barquisimeto Valencia; Ciudad Bolvar Caracas; Ciudad Bolvar El Tigre; Ciudad Bolvar Puerto Ordaz; Ciudad Bolvar San Flix; Caracas El Tigre. Caracas Maracaibo; Caracas Maracay; Caracas Maturn; Caracas Puerto La Cruz; Caracas Puerto Ordaz; Caracas San Flix; Caracas Valencia; El Tigre Maracay; El Tigre Puerto Ordaz; El Tigre Valencia; Maracaibo Maracay; Maracaibo Valencia; Maracay Maturn; Maracay Puerto La Cruz; Maracay Puerto Ordaz; Maracay Valencia; Maturn Valencia; Puerto La Cruz Valencia; Puerto Ordaz San Felipe; Puerto Ordaz ValenciaEs un grafo simple o mltiple? El grafo es simple, no tiene lados o aristas mltiples desde un nodo hasta otro. Pero es un grafo conexo, es decir, si quitamos un nodo, no aumenta el nmero de componentes conexas del mismo. Es grafo dirigido o no dirigido? El grafo es no dirigido, por lo cual las rutas que cubren los autobuses desde una ciudad origen a una ciudad destino es tambin una ruta inversa. Grado de los vrtices Ciudad Nmero de Orig Ciudades en conectadasBarquisimet o Cd Bolvar Caracas El Tigre Maracaibo Maracay 5 4 10 5 4 6

Ciudad OrigenMaturn Pto La Cruz Pto Ordaz San Flix Valencia

Nmero de Ciudades conectadas3 4 6 3 9

Matriz de adyacencias a. Matriz de Adyacencias simple b. Matriz de Adyacencias con peso (Bs. F.)

7

Matriz de alcance

Es un grafo libre? No es un grafo libre dado que contiene ciclos. Por ejemplo, podramos viajar de Caracas a Maracaibo, luego de Maracaibo a Barquisimeto y por ltimo de Barquisimeto a Caracas. Esto sera llegar al nodo inicial habiendo realizado un ciclo. Es un grafo regular? No es un grafo regular dado que al menos un par de nodos tiene distinto grado. En este caso, Caracas tiene grado 10 y ninguna otra ciudad tiene dicho grado. Es un grafo completo? No es un grafo completo, hay al menos un par de ciudades que no se conectan. Por ejemplo, Maturn no se conecta con Ciudad Bolvar. Es un grafo rueda? No, no es un grafo rueda. Aunque incluye subgrafos de que forman un grafo rueda. Por ejemplo, el subgrafo compuesto por las ciudades Valencia, Puerto La Cruz, Caracas, Barquisimeto. Es un grafo cubo? No es un grafo cubo, aunque contiene subgrafos Qn o grafos cubo. Un ejemplo de ello lo podemos ver en la figura, conformado por las ciudades Caracas, Ciudad Bolvar, Maracay, Maturn, Valencia, San Flix, Puerto Ordaz, El Tigre:

8

Es un grafo bipartito? No, no es un grafo bipartito. No hay dos tipos de nodos. Hay muchas ms conexiones entre ellos, que hacen que el grafo no sea bipartito. Es isomorfo u homomorfo a algn grafo? No, este grafo no es homomorfo a ningn grafo. Pero contiene subgrafos homomorfos a otros grafos, como mostramos en el ejemplo del grafo cubo. Tiene bucles? No tiene ninguna ruta de una ciudad consigo misma. Tiene ciclos? S, contiene varios ciclos, entre ellos tenemos: Maracaibo, Barquisimeto, Puerto La Cruz, Maracaibo; Caracas, Ciudad Bolvar, San Flix, Puerto Ordaz, Caracas o Valencia, Barquisimeto, Puerto La Cruz, Maracay, Maturn, Caracas, Valencia. Es un grafo Euleriano? El grafo completo no es Euleriano. No cumple con las condiciones para serlo porque tiene ms de dos vrtices de grado impar. Es un grafo Hamiltoniano? S, es un grafo Hamiltoniano. Tiene al menos este camino de Hamilton: Valencia, Puerto La Cruz, Barquisimeto, Maracaibo, Maracay, Maturn, Caracas, Puerto Ordaz, San Flix, Ciudad Bolvar, El Tigre. Es un grafo plano? No, sus aristas se cruzan inevitablemente al dibujarlo. Necesariamente habra que realizarlo en otra dimensin para poder evitar que stas se crucen. Cul es su nmero (polinomio) cromtico? El nmero cromtico del grafo es 11. Igual que el nmero de nodos.

Son ptimas las rutas?Desde nuestra perspectiva despus del anlisis, concluimos que las rutas podran ser ptimas desde la ptica de la conectividad, pero hay otros factores como la seguridad, la vialidad, las estaciones de servicio, las condiciones climticas y sus consecuencias y la factibilidad de uso que afectan la decisin de la empresa en la creacin de nuevas rutas o eliminacin de algunas existentes.

Qu mejoras se le puede aplicar a las rutas?Siendo consistentes con la optimizacin de rutas, es considerablemente mayor el gasto de tiempo y dinero en la ruta San Flix Puerto Ordaz y Puerto Ordaz Ciudad Bolvar que los ingresos que pueden generar debido a que la cercana entre las ciudades hace que la movilizacin pueda fluir mayormente por otros medios. Esta ruta puede perfectamente ser eliminada y traera como consecuencia desde el punto de vista de grafos que se rompa un camino hamiltoniano. 9

Expresos OccidenteRutasEl Viga Machiques Valera Trujillo Coro Puerto Cabello Maracaibo La Fra Colon San Cristbal Barinas Maracay Caracas Valencia Mrida Cabimas

Grafo del sistema

Orden del grafo El grafo es de orden n =18. Es decir tiene 18 nodos. Tiene en total 21 lados. Conjuntos de nodos y de lados El conjunto de nodos est conformado por los elementos del conjunto V y el conjunto de lados est conformado por los elementos del conjunto E. 10

G = Colon, San Cristbal, Barinas, Maracay, Caracas, Valencia, Mrida, Cabimas, Maracaibo, La Fra, El Viga, Machiques, Valera, Trujillo, Coro, Puerto Cabello, Barquisimeto V = Colon La Fra, Colon San Cristobal, San Cristobal El Vigia, San Cristbal Barinas, Barinas Valencia, Barinas Merida, Barinas Barquisimeto, Maracay Caracas, Maracay Valencia, Valencia Puerto Cabello, Merida El Vigia, Merida Valera, Maracaibo Machiques, Machiques Cabimas, Cabimas Coro, La Fra Machiques, La Fra El Vigia, Valera Trujillo, Trujillo Barquisimeto, Coro Puerto Cabello, Puerto Cabello BarquisimetoEs un grafo simple o mltiple? El grafo es simple, no tiene lados o aristas mltiples desde un nodo hasta otro. Pero es un grafo conexo, es decir, si quitamos un nodo, no aumenta el nmero de componentes conexas del mismo. Es grafo dirigido o no dirigido? El grafo es no dirigido, por lo cual las rutas que cubren los autobuses desde una ciudad origen a una ciudad destino es tambin una ruta inversa. Grado de los vrticesCiudad Orig en Colon San Cristbal Barinas Maracay Caracas Valencia Mrida Cabimas Maracaibo Nmero de Ciudades conectadas 2 3 4 2 1 3 3 2 2 Ciudad Orig en La Fra El Viga Machiques Valera Trujillo Coro Puerto Cabello Barquisimet o Nmero de Ciudades conectadas 3 4 3 2 2 2 3 3

11

1. Matriz de adyacencias Matriz de Adyacencias simple:

Matriz de alcance Todos los nodos son alcanzables desde cualquier otro nodo.

Es un grafo libre? No es un grafo libre dado que contiene ciclos. Por ejemplo, existen varias vas para ir a San Cristbal. Es un grafo regular? No es un grafo regular dado que al menos un par de nodos tiene distinto grado. En este caso, El Viga tiene grado 4 que comparte con Barinas. Es un grafo completo? No es un grafo completo, hay al menos un par de ciudades que no se conectan. Por ejemplo, Valencia no se conecta con Colon.

12

Es un grafo rueda? No, no es un grafo rueda. Es un grafo bipartito? No, no es un grafo bipartito. No hay dos tipos de nodos. Hay muchas ms conexiones entre ellos, que hacen que el grafo no sea bipartito. Es isomorfo u homomorfo a algn grafo? No, este grafo no es homomorfo a ningn grafo. Pero contiene subgrafos homomorfos a otros grafos. Tiene bucles? No tiene ninguna ruta de una ciudad consigo misma. Tiene ciclos? S, contiene varios ciclos, entre ellos tenemos: Maracaibo, Cabimas, Coro, Puerto Cabello, Barinas, Mrida, El Vigia, La Fra, Machiques, Maracaibo; Valencia, Barquisimeto, Puerto Cabello, Valencia, Maracay, Caracas. Es un grafo Euleriano? El grafo completo no es Euleriano. No cumple con las condiciones para serlo porque tiene ms de dos vrtices de grado impar. Es un grafo Hamiltoniano? No es un grafo Hamiltoniano. Es un grafo plano? No, sus aristas se cruzan inevitablemente al dibujarlo. Necesariamente habra que realizarlo en otra dimensin para poder evitar que stas se crucen. Cul es su nmero (polinomio) cromtico? El nmero cromtico del grafo es 18. Igual que el nmero de nodos.

Son ptimas las rutas?Desde nuestra perspectiva despus del anlisis, concluimos que las rutas podran ser ptimas desde la ptica de la conectividad, pero hay otros factores como la seguridad, la vialidad, las estaciones de servicio, las condiciones climticas y sus consecuencias y la factibilidad de uso que afectan la decisin de la empresa en la creacin de nuevas rutas o eliminacin de algunas existentes.

Qu mejoras se le puede aplicar a las rutas?Como a cualquier empresa de transporte nacional, es posible mejorarle. Sin duda, en cuanto a condiciones de seguridad, las rutas del occidente del pas tienen muchas deficiencias en cuanto a vialidad, por lo cual hay terminales en ciudades con vas no aptas para la comunicacin con otras ciudades, sin embargo, observamos que desde el punto de vista econmico las rutas presentan una atractiva cantidad de rutas a ciudades con alto potencial turstico. Mejoras se le puede realizar en la vialidad para que el servicio sea 13

muchsimo ms fluido, dado que la ruta ptima se puede calcular en base a seguridad, seguridad vial, precios, duracin del trayecto en cuanto a tiempo o bien longitud del mismo entre otros parmetros de seguridad principales.

14

Bibliografa www.aeroexpresos.com.ve

www.venezueladeverdad.gob.ve/obras-del-gobiernobolivariano/metrocable-de-san-agustin.html

jessechacon.psuv.org.ve/?page_id=656

15