• Author / Uploaded
• Julio c Resendiz

Citation preview

Ejercicio_3_U4

Grafos La teoría de grafos es una disciplina antigua con muchas aplicaciones modernas. Ya que fue introducida por el gran matemático suizo Leonard Euler en el siglo XVIII. Los grafos son estructuras discretas que constan de vértices y de artistas que conectan entre si esos vértices. Hay varios tipos de grafos.

Tipos De Grafos Definición 1. Un grafo simple G= (V, E) consta de V, un conjunto no vacío de vértices, y de E, un conjunto de pares no ordenados de elementos distintos de V.A estos pares se les llama aristas. Un multígrafo G= (V, E) constan de un conjunto V de vértices, un conjunto E de aristas y una función f de E en {[u, v]} [u, vc V, u .v]. Se dice que las aristas e1 y e2 son aristas múltiples o paralelas si f (e1)=f (e2). Definición 3. Un pseudografo G= (V.E) consta de un conjunto de V de vértices, un conjunto de E de aristas y una función f de E en {{u, v} Iu, v E V}. Una arista e es un bucle, o lazo, si f (e)= {u, u}= {u} para algún u E V. Definición 4. Un grafo dirigido (V, E) consta de un conjunto V de vértices y de un conjunto E de aristas. Que son pares ordenados de elementos de V. Definición 5. Un multígrafo dirigido G= (V, E) consta de un conjunto V de vértices, un conjunto E de aristas y una función f de E en (u, v) [u, v E V]. Se dice que las aristas e1 y e2 son aristas múltiples si f (e1)=f (e2).

Modelos de grafos Ejemplo 1. Grafos de solapamiento de nichos en ecología.

Los grafos se emplean en muchos modelos que tienen que ver con las interacciones entre especies animales distintas. Ya que cada especie se representa por un vértice. Ejemplo 2. Grafos de conocidos. Se puede usar el modelo de grafos para representar relaciones entre personas. Un ejemplo, es poder usar un grafo para representar el hecho de que dos personas se conozcan. Ejemplo 3. Grafos de influencias. Se ha observado en estudio del comportamiento de grupos que ciertas personas influyen en la forma en que piensan otras personas. Se puede usar un grafo dirigido, llamado grafo de influencias, para representar este comportamiento. Ejemplo 4. El grafo de Hollywood. El grafo de Hollywood representa a los actores como vértices y conecta dos vértices si los actores representados por dicho vértice han trabajado juntos en alguna película. Ejemplo 5. Torneos de todos contra todos. Un torneo en el que cada equipo se enfrenta exactamente una vez cada uno de los restantes se llama torneos de todo contra todos. Cada equipo se representa mediante un vértice. Ejemplo 6. Grafos de colaboración. Sirven para modelar la coautoría de artículos académicos. En un grafo de colaboración, los vértices representan personas (restringidas, quizás, a una cierta comunidad científica) y una arista conecta a dos personas si estás han escrito conjuntamente un artículo.

Ejemplo 7. Grafos llamadas. Los grafos se pueden utilizar para representar llamadas telefónicas hechas en una red. En particular, pueden usarse un multígrafo dirigido para representar llamadas: cada vértice representa un número de teléfono y cada arista representa una llamada. Ejemplo 8. Le red de internet se puede representar por medio de un grafo dirigido en el que cada página está dirigido por un vértice y en que una arista comienza en la pagina a y termina en la pagina b, si hay un enlace en la pagina a que conduce en la pagina b. Ejemplo 9. Los programas informáticos pueden ejecutarse más paridamente si ciertas sentencias se ejecutan simultáneamente, es importante no ejecutar sentencias que no requieran resultados de sentencias no ejecutadas aun, esto se representa en u grafo dirigido cada sentencia se representa por un vértice y hay un arista de un vértice a un segundo vértice , si la segunda sentencia no puede representarse hasta que la sentencia de la primera sea ejecutada se la llama grafo de precedencia.