4.2.-GRAFOS
Un grafo G es un par G = (V, E), donde V es un conjunto finito (vértices, nodos) y E es un multiconjunto de pares no ordenados de vértices, denotados por {x, y}, que se denominan lados, aristas, etc. En este caso decimos que X y Y son extremos de {x, y}. Denotamos V (G) por el conjunto de vértices del grafo G y por E (G) el conjunto de lados del grafo G.
Además (G) y "(G) denotan el número de vértices y el número de aristas de G respectivamente. Puesto que E es un multiconjunto es posible que existen pares repetidos, en este caso G tiene lados múltiples. También es posible que algún par no ordenado de E tenga el mismo vértice repetido, en este caso decimos que el lado es un lazo (loop) o bucle. Cuando existen lados múltiples y/o lazos decimos que G es un multígrafo.
Si no hay lados múltiples ni lazos decimos que es un grafo simple. Un dígrafo G es un par G = (V, E) donde V es un conjunto de vértices y E es un multiconjunto de pares ordenados. Los lados se denotan por pares ordenados, (u, v) denota el lado dirigido que tiene como vértice inicial a u y como vértice terminal a v.
A continuación damos unas definiciones:
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 esos pares se les llama aristas o lados.
Definición 2.-Un grafo dirigido o dígrafo G = (V, E) consta de un conjunto V de vértices, un conjunto E de aristas, que son pares ordenados de elementos de V.
En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas). Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).
4.2.1.- TERMINOLOGÍA DE GRAFOS
Dependiendo del tipo de relación entre los vértices del grafo, se definen distintos tipos de grafos. Así se distinguen aristas dirigidas y no dirigidas:
Arista dirigida: es aquella que define un par ordenado de vértices (u, v), donde el primer vértice u es el origen de la arista y el segundo vértice v es el término (o vértice final). El par (u, v) ≠ (v, u).
Arista no dirigida: es aquella que define un par no ordenado de vértices (u, v), donde (u, v) = (v, u).
De esta forma se distinguen entre grafos dirigidos y grafos no dirigidos.
Grafo dirigido: Es aquel cuyas aristas son dirigidas. Los grafos dirigidos suelen representar relaciones asimétricas como por ejemplo: relaciones de herencia, los vuelos entre ciudades, etc.
1. Vértice (Vertex) Un punto o un nodo de un grafo.
2. Arco (Edge) Una línea que un vértice con otro vértice del mismo grafo, en grafos no direccionados, o una fecha que une dos vértices del mismo grafo, en grafos direccionados.
3. Cabeza (Head) En grafos direccionados, es el vértice donde llega la flecha.
4. Cola (Tail) en grafos direccionados, es el vértice desde donde sale la fecha.
5. Vértices Adyacentes (Adjancent Edges) Son dos vértices que están unidos por un arco.
6. Arcos Incidentes (Incident Edges) Son los arcos que inciden en un determinado vértice.
2. Según el tipo y cantidad de arcos
1. Grafo No Direccionado (Undirected Graph) Son grafos donde los arcos unen un par de vértices desordenados. Así, el par (v1,v2) y el (v2,v1) representa el mismo arco.
2. Grafo (Graph) Es un sinónimo de grafo no direccionado. Los grafos no direccionados, normalmente se los llama grafos a secas.
3. Grafo Completo (Completed Graph) Es un grafo no direccionado donde existe un arco entre cada par de vértices cualesquiera del mismo. El número máximo de arcos que puede tener un grafo de n vértices es n * (n - 1) / 2.
4. Grafo Direccionado (Directed Graph) Son grafos donde los arcos unen un par de vértices ordenados. Así, el par [v1, v2] y [v2, v1] representan arcos distintos. En el caso del arco [v1, v2], v1 es la cola del arco y v2 en la cabeza. Los arcos de un grafo direccionado se representan con flechas.
5. Dígrafo (Digraph) Es un sinónimo de grafo direccionado.
6. Digrafo Completo (Completed Digraph) Es un grafo direccionado donde existe un arco entre cada dos vértices cualesquiera del mismo, tanto el que va desde un vértice al otro, como el que retorna. El número máximo de arcos que puede tener un dígrafo de n vértices es n * (n - 1).
7. Multígrafo (Multigraph) Se aceptan más de un arco uniendo dos vértices. En términos formales, no son grafos.
8. Subgrafo (Subgraph) Un subgrafo de G es un grafo G', tal que V(G') está incluido en V(G) y E(G') está incluido en E(G).
3. Según la conectividad
1. Componentes Conectados (Connected Component) Tiene distinto significado según se trate de grafos direccionados o no direccionados.
2. Fuertemente Conectado (Strongly Connected) Tiene distinto significado según se trate de grafos direccionados o no direccionados.
4. Conceptos vinculados al grado.
1. Grado de un Vértice (Vertex Degree) Es el número de arcos que inciden sobre el vértice.
2. Grado Entrante de un Vértice (Vertex In Degree) Es el número de arcos para los cuales el vértice es la cabeza.
3. Grado Saliente de un Vértice (Vertex Out Degree) Es el número de arcos para los cuales el vértice es la cola.
5. Conceptos vinculados al paso
1. Paso (Path) El paso desde un vértice vp a un vértice vq, en un grafo G, es una secuencia de vértices vp, vi1, vi2,..., vin, vq, tal que (vp, vi1), (vi1,vi2), ..., (vin,vq) son arcos en E(G). Si G es un grafo direccionado, el paso consiste de [vp, vi1], [vi1, vi2],..., [vin, vq], arcos en E (G).
2. Paso Simple (Simple Path) Es un paso, donde todos los vértices, excepto, posiblemente, el primero y el último, son distintos.
3. Paso Ciclo (Cycle Path) Es un paso simple, donde el primero y último vértice es el mismo vértice.
4. Longitud del Paso (Path Length) El número de vértices en un paso.
4.2.2.-OPERACIONES BÁSICAS DE LOS GRAFOS
En los grafos, como en todas las estructuras de datos, las dos operaciones básicas son insertar y borrar. En este caso, cada una de ellas se desdobla en dos, para insertar/eliminar vértices e insertar/eliminar aristas.
Insertar vértice
La operación de inserción de un nuevo vértice es una operación muy sencilla, únicamente consiste en añadir una nueva entrada en la tabla de vértices (estructura de datos que almacena los vértices) para el nuevo nodo. A partir de ese momento el grafo tendrá un vértice más, inicialmente aislado, ya que arista llegará a él.
Insertar arista
Esta operación es también muy sencilla. Cuando se inserte una nueva arista en el grafo, habrá que añadir un nuevo nodo a la lista de adyacencia (lista que almacena los nodos a los que un vértice puede acceder mediante una arista) del nodo origen, así si se añade la arista (A,C), se deberá incluir en la lista de adyacencia de A el vértice C como nuevo destino.
Eliminar vértice
Esta operación es inversa a la inserción de vértice. En este caso el procedimiento a realizar es la eliminación de la tabla de vértices del vértice en sí. A continuación habrá que eliminar las aristas que tuviesen al vértice borrado como origen o destino.
Eliminar arista
Mediante esta operación se borra un arco del grafo. Para llevar a cabo esta acción es necesario eliminar de la lista de adyacencia del nodo origen el nodo correspondiente al nodo destino.
Otras operaciones
Las operaciones adicionales que puede incluir un grafo son muy variadas. Además de las clásicas de búsqueda de un elemento o recorrido del grafo, también podemos encontrarnos con ejecución de algoritmos que busquen caminos más cortos entre dos vértices, o recorridos del grafo que ejecuten alguna operación sobre todos los vértices visitados, por citar algunas operaciones de las más usuales.
BIBLIOGRAFIA:
4.1 Arboles
4.1.1 Concepto de árbol
4.1.2 Clasificación de arboles
Rescooped by Cinthia Carrasco from Estructura de Datos
| |
| |
4.1.3 Operaciones básicas sobre arboles binarios
Unidad 4 Arboles y Grafos OAG (Investigacion 2)
Publicado por Osvaldo Apolinar
4.1.4 Aplicaciones
CUARTA UNIDAD- ESTRUCTURAS NO LINEALES | ESTRUCTURA DE DATOS- Rosa Ma. Cristobal Joaquin.
4.1.5 Arboles balanceados (AVL)
4.2 Grafos
4.2.1 Terminología de grafos
4.2.2 Operaciones básicas sobre grafos
DataStructures Tool
muy buena informacion.se los agradezco..gracias
ResponderEliminarEs muy buena información aunque estaría mejor con algunos mas ejemplos he imágenes y unos tutoriales para entender mejor su contenido pero muy bien
ResponderEliminarbuena informacion entendible. espero sea util para los programas en java....Muy bonito blogger!!
ResponderEliminaral revisar este blog puede observar que muestra definición
ResponderEliminares, ejemplos, imágenes, videos aunque no hubiese estado mal si hubieran puesto mas ejemplos o hasta ejercicios resueltos de acorde a los temas pero
estuvo bien.
MUY BUENA INFORMACIÓN SOLO TE SUGIERO QUE CHEQUES UN POCO ACERCA DE LA INFORMACIÓN QUE DIVIDISTE EN SECCIONES ESO DA MALA PRECENTACION COMO EQUIPO Y LOS HACE NOTAR QUE SE DIVIDIERON EL TRABAJO
ResponderEliminarAl igual que todos los compañeros en su blog se puede encontrar muy buenas definiciones sobre los arboles, su clasificacion, aplicacion y de igual manera los grafos. me parece un buen trabajo en equipo y creo que deberiamos seguir haciendo este tipo de actividades.
ResponderEliminar