TEORIA DE GRAFOS
Conceptos básicos de la teoría de grafos
11.2.1 Concepto de grafo
Sea V el conjunto no vacío de vértices o nodos y E el conjunto de lados o aristas (pares de vértices); se dice que G es un grafo, si G= (V, E) es una estructura de datos compuesta por esos dos conjuntos V y E que forman un conjunto de pares ordenados o desordenados de vértices o nodos. Los pares de vértices van entre paréntesis y los pares desordenados, pondrán entre llaves.
11.3 Clasificación de los grafos
11.3.1 Grafo dirigido
Un grafico dirigido G, también llamado “dígrafo o digrafo”, consta de un conjunto V de vértices y un conjunto E de aristas tales que cada arista e E E se asocia con un par ordenado de vértices. Si existe una única arista e asociada con el par ordenado (v, w) de vértices, escribimos e = (v, w) lo cual denota una arista de v a w. En conclusión, se puede afirmar que un grafo dirigido es aquel que tiene uniones unidireccionales que suelen dibujarse con una flecha.
Un grafo dirigido es aquel que tiene todas sus aristas dirigidas; es decir, un dígrafo está asociado a un par ordenado (vea figura 9.1a). Por ejemplo, si w es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja ordenada (w,v), que es diferente de (v,w) ; es decir,
Los vértices de donde parten las aristas se denominan vértices salientes y los vértices a donde llegan las aristas se llaman vértices entrantes.
11.3.2 Grafo no dirigido
Un grafo no dirigido (vea figura 10.1b) consta de un conjunto de vértices y un conjunto E de aristas tal que cada arista e E E queda asociada a un par no ordenado de vértices. Si existe una única lista e asociada con los vértices v y w, escribimos e = {v,w} ó e = {w,v}. en este contexto, {v,w} denota una arista entre v y w en un grafo no dirigido y no un par ordenado. En conclusión un grafo no dirigido es aquel en el cual sus aristas son direccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A. Sus aristas son no dirigidas; es decir, un dígrafo está asociado a un par desordenado (vea figura 10.1d).
Ejemplo 11.1: si u es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja desordenada {w,v}, que es igual que escribir {v,w}; es decir, {w,v}={v,w}. En tal caso, w es vértice e partida o de llegada; igualmente sucede con v.
11.3.3 Grafo dirigido con peso
Es aquel grafo dirigido en el que sus aristas tienen una etiqueta (vea figura 10.1c). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso. Se usa en el modelado de problemas de la vida real; por ejemplo, al tiempo que se tardará en realizar una actividad determinada o la distancia que hay de un lugar a otro.
11.3.4 Grafo mixto
Es aquel grafo en el que algunas de sus aristas son dirigidas y otras son no dirigidas (vea figura 11.1d).
Según la figura 11.1c se podría interpretar por ejemplo, que para pasar de la actividad 1 a la 3 se tarda un tiempo p2; que pasar de actividad 3 a la 2 se tarda un tiempo p3 y, de la actividad 2 a la 1 se tardaría un tiempo p1. Un grafo no dirigido puede dibujarse con aristas dirigidas haciendo que cada lado les corresponda aristas invertidas.
11.4 Vértices adyacentes
Son aquellos que conforman un lado o arista. Todo lado conformado por dos vértices se dice que es incidente sobre esos vértices. Si un vértice no tiene otro adyacente se dice que es aislado.
Ejemplo 11.2: en G2 de la figura 11.2, son adyacentes los vértices 1 y 3. Así que la arista {1,3} incide sobre los vértices 1 y 3
En G1 de la figura 11.2: 1 es adyacente hacia 2 ó 2 es adyacente desde 1, donde la arista (1,2) incide sobre los vértices 1 y 2.
Ejemplo 11.3: en el grafo de la figura 11.2 la arista e1 incide sobre los vértices 1 y 2; igualmente, e7 incide sobre los vértices 5 y 6.
11.5 Representación de grafos
De cualquier manera, para dar algo de sentido a la terminología usada y también para desarrollar algunas ideas intuitivas, se representará un grafo por medio de un diagrama. Ese diagrama se llamará igualmente grafo.
1
Las definiciones y términos presentadas en este texto no están restringidos a aquellos grafos que pueden ser representados por medio de diagramas, aunque parezca ser el caso, ya que estos términos tengan una fuerte asociación con dicha representación. Debemos resaltar que una representación diagramática es posible únicamente en casos muy simples.
11.5.1 Representación gráfica de grafos
Los diagramas se pueden representar gráficamente cuando la cantidad de vértices no es grande. Para tal fin, puede utilizar los siguientes diagramas:
Los grafos G2, G3 y G4 son grafos no dirigidos; G1 es un grafo dirigido
Cuando un vértice se dirige a él mismo, se denomina “bucle”. Si un grafo no tiene bucles o si a lo sumo existe una arista uniendo 2 vértices cualesquiera, se denomina “Grafo simple”.
11.2.1 Concepto de grafo
Sea V el conjunto no vacío de vértices o nodos y E el conjunto de lados o aristas (pares de vértices); se dice que G es un grafo, si G= (V, E) es una estructura de datos compuesta por esos dos conjuntos V y E que forman un conjunto de pares ordenados o desordenados de vértices o nodos. Los pares de vértices van entre paréntesis y los pares desordenados, pondrán entre llaves.
11.3 Clasificación de los grafos
11.3.1 Grafo dirigido
Un grafico dirigido G, también llamado “dígrafo o digrafo”, consta de un conjunto V de vértices y un conjunto E de aristas tales que cada arista e E E se asocia con un par ordenado de vértices. Si existe una única arista e asociada con el par ordenado (v, w) de vértices, escribimos e = (v, w) lo cual denota una arista de v a w. En conclusión, se puede afirmar que un grafo dirigido es aquel que tiene uniones unidireccionales que suelen dibujarse con una flecha.
Un grafo dirigido es aquel que tiene todas sus aristas dirigidas; es decir, un dígrafo está asociado a un par ordenado (vea figura 9.1a). Por ejemplo, si w es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja ordenada (w,v), que es diferente de (v,w) ; es decir,
Los vértices de donde parten las aristas se denominan vértices salientes y los vértices a donde llegan las aristas se llaman vértices entrantes.
11.3.2 Grafo no dirigido
Un grafo no dirigido (vea figura 10.1b) consta de un conjunto de vértices y un conjunto E de aristas tal que cada arista e E E queda asociada a un par no ordenado de vértices. Si existe una única lista e asociada con los vértices v y w, escribimos e = {v,w} ó e = {w,v}. en este contexto, {v,w} denota una arista entre v y w en un grafo no dirigido y no un par ordenado. En conclusión un grafo no dirigido es aquel en el cual sus aristas son direccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A. Sus aristas son no dirigidas; es decir, un dígrafo está asociado a un par desordenado (vea figura 10.1d).
Ejemplo 11.1: si u es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja desordenada {w,v}, que es igual que escribir {v,w}; es decir, {w,v}={v,w}. En tal caso, w es vértice e partida o de llegada; igualmente sucede con v.
11.3.3 Grafo dirigido con peso
Es aquel grafo dirigido en el que sus aristas tienen una etiqueta (vea figura 10.1c). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso. Se usa en el modelado de problemas de la vida real; por ejemplo, al tiempo que se tardará en realizar una actividad determinada o la distancia que hay de un lugar a otro.
11.3.4 Grafo mixto
Es aquel grafo en el que algunas de sus aristas son dirigidas y otras son no dirigidas (vea figura 11.1d).
Según la figura 11.1c se podría interpretar por ejemplo, que para pasar de la actividad 1 a la 3 se tarda un tiempo p2; que pasar de actividad 3 a la 2 se tarda un tiempo p3 y, de la actividad 2 a la 1 se tardaría un tiempo p1. Un grafo no dirigido puede dibujarse con aristas dirigidas haciendo que cada lado les corresponda aristas invertidas.
11.4 Vértices adyacentes
Son aquellos que conforman un lado o arista. Todo lado conformado por dos vértices se dice que es incidente sobre esos vértices. Si un vértice no tiene otro adyacente se dice que es aislado.
Ejemplo 11.2: en G2 de la figura 11.2, son adyacentes los vértices 1 y 3. Así que la arista {1,3} incide sobre los vértices 1 y 3
En G1 de la figura 11.2: 1 es adyacente hacia 2 ó 2 es adyacente desde 1, donde la arista (1,2) incide sobre los vértices 1 y 2.
Ejemplo 11.3: en el grafo de la figura 11.2 la arista e1 incide sobre los vértices 1 y 2; igualmente, e7 incide sobre los vértices 5 y 6.
11.5 Representación de grafos
De cualquier manera, para dar algo de sentido a la terminología usada y también para desarrollar algunas ideas intuitivas, se representará un grafo por medio de un diagrama. Ese diagrama se llamará igualmente grafo.
1
Las definiciones y términos presentadas en este texto no están restringidos a aquellos grafos que pueden ser representados por medio de diagramas, aunque parezca ser el caso, ya que estos términos tengan una fuerte asociación con dicha representación. Debemos resaltar que una representación diagramática es posible únicamente en casos muy simples.
11.5.1 Representación gráfica de grafos
Los diagramas se pueden representar gráficamente cuando la cantidad de vértices no es grande. Para tal fin, puede utilizar los siguientes diagramas:
Los grafos G2, G3 y G4 son grafos no dirigidos; G1 es un grafo dirigido
Cuando un vértice se dirige a él mismo, se denomina “bucle”. Si un grafo no tiene bucles o si a lo sumo existe una arista uniendo 2 vértices cualesquiera, se denomina “Grafo simple”.
Te quedo bien lupita👌
ResponderBorrar