Uno de los aspectos más importantes en computación es la programación. Para elaborar un programa es conveniente tener una forma de representar las ideas antes de elaborar el código. Aquí presentamos una aplicación de los grafos en la representación de los conceptos básicos de diagramas de flujo. Por supuesto que los diagramas de flujo son mucho más generales que su uso en programación y pueden ser utilizados para muchas otras aplicaciones.
Los diagramas que se tratan son:
Secuencias
If-then-else
While
| ⇐ | Tema Anterior: 3.1.2 Clasificacion de Grafos |
| ⇒ | Siguiente Tema: 3.2.1 Secuencias |
| Regresar al TEMARIO: Matematicas Computacion |
‘COMIENZA’
Karla Leticia Delgadillo Del Toro
Rene Francisco Hernandez Osorio
Gonzales Leon Josue Jared
Chaves
Grafos
Clasificación de grafos
Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.
Ejemplos G1 = (V1, A1) V1 = {1, 2, 3, 4} A1 = (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) G2 = (V2, A2) V2 = {1, 2, 3, 4, 5, 6} A2 = (1, 2), (1, 3), (2, 4), (2, 5), (3, 6) G3 = (V3, A3) V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }
Grafos Conexos.
Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”. Representación de grafos.
Grafos Los grafos pueden ser utilizados como la estructura básica para múltiples aplicaciones en el área de la Computación. Un grafo G (N, A, f) es un conjunto no vacío, donde:•N={n1, n2, … ,nM) es el conjunto de nodos o vértices•A={a1, a2, …, a K} es el conjunto de aristas y•La función f : R →Μ×Μindica los pares de nodos que están relacionados.•Grafos Dirigidos (Dígrafos) En estos grafos, las aristas que comunican dos nodos tienen un único sentido, una arista puede ir de x a y, pero no de y a x. Se expresa gráficamente con flechas que indican el sentido de la relación entre cada par de nodos.Grafos•
Grafos no dirigidos En estos grafos, las aristas que comunican dos nodos tienen dos sentidos. Si una arista va de x a y, la misma arista va de y a x. Se expresa gráficamente por líneas. La representación gráfica de un grafo se define con un círculo o rectángulo para los nodos y las relaciones con líneas o flechas según sea un grafo no dirigido o un dígrafo, respectivamente.
El plan de estudios de determinada titulación se compone de 6 asignaturas, que por simplicidad, denominaremos y . A la hora de matricularse de las distintas asignaturas se ha de tener en cuenta una serie de dependencias entre ellas (prerrequisitos). De esta forma, un alumno no se puede matricular en una asignatura hasta haber aprobado aquellas otras que sean prerrequisito de dicha asignatura. Representaremos a continuación los prerrequisitos del plan de estudios como un grafo dirigido de dependencias.
Por ejemplo, un arco del nodo al nodo indica que no es posible matricularse de sin haber aprobado previamente . A continuación se muestran las operaciones del TAD grafos necesarios para construir el grafo de dependencias.
Teniendo en cuenta que una operación de la forma añade al grafo un arco con origen en y destino en , se pide: Representar gráficamente y mediante matrices de adyacencia cada uno de los grafos , y .