Programa

Solo disponible en BuenasTareas
  • Páginas : 3 (592 palabras )
  • Descarga(s) : 0
  • Publicado : 9 de diciembre de 2010
Leer documento completo
Vista previa del texto
GRAFOS
Este ensayo profundiza en otra estructura de datos no lineal: el grafo. Como hemos hecho con otras estructuras de datos discutiremos la representación y clasificación y aplicación de losgrafos en memoria y presentaremos varias operaciones y algoritmos sobre de ellos en particular, discutiremos la búsqueda en anchura y la búsqueda en profundidad para nuestros grafos.Un grafo dirigido Gconsiste en un conjunto de vértices V y un conjunto de arcos o aristas A. Los vértice se denominan también nodos o puntos. Un arco, es un par ordenado de vértices (V, W) donde V es el vértice inicial yW es el vértice terminal del arco. Un arco se expresa como: V–>W y se representa de la siguiente manera: Los vértices de un grafo pueden usarse para representar objetos. Los arcos se utilizan pararepresentar relaciones entre estos objetos. Algunas de las operaciones sobre grafos, como:
1. Creación.
2. Inserción.
3. Búsqueda.
4. Eliminación.
Inserción en un grafo: suponga quese va a insertar un nodo N en el grafo G.
Búsqueda en un grafo: suponga que queremos encontrar la posición pos de un nodo N de un grafo C.
Eliminación en un grafo: suponga que se va eliminar unaarista (A,B)del grafo G.
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.. En un grafo dirigidocada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes:
Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lollamaremos k-regular.
* Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto
* Grafocompleto: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.
* Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto...
tracking img