Componentes conexos y puntos de articulación (Grafos – E1)

Bosques: Definición

Un bosque no es mas que un grafo sin ciclos pero no conexo, es decir, todos sus puntos no están conectados a un camino simple. Esta es la única caractersistica que los diferencia de los arboles.

COMPONENTES CONEXOS Y PUNTO DE ARTICULACION

Un punto de articulación en un grafo es un vértice que al ser eliminado divide al grafo original en dos o más partes el grafo original convirtiéndolos en dos grafos.

Cuando en un grafo no existe un punto de articulación se dice que es un grafo biconexo  ya que existen dos o más caminos que conectan al vértice.

Se dice que un grafo tiene conectividad K si al eliminar un vértice (K-1) no los desconecta.

Se dice que mientras más conectividad tenga tendrá menos posibilidades de sufrir un fallo.

Para poder encontrar un  punto de articulación en un grafo se tiene el siguiente procedimiento:

1)      Crear un árbol del grafo

2) Elegir un nodo como raíz, este será el que tenga mayor conexión (hijos)

3) se recorre al siguiente nodo más cercano por la izquierda

4) se repite el paso dos hasta completar todos los nodos.

Cuando el árbol ya está creado se verifica el árbol esto es, comenzar a enumerar el árbol iniciando por la raíz (n [ ]=i à esto es un arreglo que guarda el orden de la matriz)

VERIFICAR LOS VALORES EN EL ÁRBOL

a) comenzar a enumerar el árbol iniciando por la raíz y continuando hacia el lado izquierdo

b) se continúa la numeración de la raíz pero ahora por el lado derecho

c) se calcula el valor de bajo:

Esto se hace seleccionando en nodo a calcular y descendiendo por los nodos hijos de este y regresando hasta el punto menor por los arcos de retroceso.

Para poderse considerar como punto de articulación debe cumplir con BAJO >= NODO [V]

ELABORADO POR OSWUALDO ALQUISIRIS QUECHA.

de lamdiscreta

Equipo 3

Presentado por: Itzel Meléndez Sosa

ARBOL-(Teoría de grafos)

Empezaremos por identificar términos previos para lograr una mayor comprensión de lo que son los arboles ya que en realidad no se tiene una sola y completa definición de lo que son.

Grafo.- es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que

Árbol

Un grafo simple unidireccional que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n – 1 aristas, y hay nn-2 árboles posibles. Su importancia radica en que son grafos que conectan todos los vértices utilizando el menor número posible de aristas, y satisface alguna de las siguientes condiciones equivalentes:

-G es conexo y no tiene ciclos simples
-G no tiene ciclos simples y, si se añade alguna arista deja der ser conexo
-G es conexo y si se le quita alguna arista deja de ser conexo
-G es conexo y el grafo completo de 3 vértices Kno es un número menor de G
-Dos vértices cualesquiera de G están conectados por un único camino simple
Operaciones básicas con árboles.

1.Entreorden
*Recorrer el subárbol izquierdo en entreorden.
*Examinar la raíz.
*Recorrer el subárbol derecho en entreorden.
2. Preorden
*Examinar la raíz.
*Recorrer el subárbol izquierdo en preorden.
*recorrer el subárbol derecho en preorden.
3. Postorden
*Recorrer el subárbol izquierdo en postorden.
*Recorrer el subárbol derecho en postorden.
*Examinar la raíz.

APLICACIONES DE LOS ARBOLES .-Un importante campo de aplicación de su estudio se encuentra en el análisis filogenético, el de la filiación de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguación del parentesco entre especies; aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas.

El ferrocarril y los grafos

los grafos y los problemas del tráfico urbano.

Subterráneos, tranvías y trenes elevados

 

 

Presentado por: Ana patricia Matus Vicente

Bosques y  componentes conexos

Un bosque es un conjunto de árboles o de otra manera podemos decir que un bosque es un grafo acíclico, de dice que el grafo es acíclico si no se tiene ningún ciclo simple.

La figura muestra un bosque, el cual está compuesto por tres árboles.

Un componente conexo es cada árbol que conforma al bosque.

Sea G un grafo un árbol abarcador de G es un grafo conexo que tienen los mismos vértices que G y no tiene ciclos.

A continuación se muestra los dos algoritmos para calcular el árbol abarcador de costo mínimo.

  1. Algoritmo de Kruskal
  2. Algoritmo de Prim

El primer algoritmo consiste en elegir las aristas de menor peso hasta conseguir el árbol de peso mínimo, en otras palabras podemos decir que este algoritmo busca un subconjunto de grafos que formando un árbol incluya a todos los vértices y el valor de los arcos sea mínimo

El segundo algoritmo consiste en ir borrando las aristas de mayor peso y que no sean aristas de separación.

Si tenemos un grafo G y calculamos el árbol abarcador atravéz de los dos algoritmos tendremos el mismo costo mínimo, en algunos casos se podrá tener el mismo árbol en ambos algoritmos pero en otros no.

Los siguientes link muestran ejemplos de cómo encontrar el árbol abarcador de costo mínimo atravéz de los dos algoritmos que ya conocemos.

http://www.youtube.com/watch?v=AR_Y88kkh58&feature=related

http://www.youtube.com/watch?v=O8XEOz8FCDQ

 

 

 

 

PRESENTADO POR: GEREMIAS SANCHEZ MARTINEZ.

ORDENAMIENTO TOPOLOGICO.

EL ORDENAMIENTO TOPOLOGICO ES UN METODO QUE SIRVE PARA DETERMINAR LA RELACION DE UN VERTICE A OTRO, ES DECIR, SE ESCRIBE EL INICIO O EL PUNTO DE PARTIDA DE LAS ARISTAS Y EL LUGAR A DONDE LLEGAN, POR EJEMPLO:

EN LA SIGUIENTE FIGURA, EL INICIO ES A Y LOS VERTICES CON QUE SE RELACIONAN MEDIANTE LAS ARISTAS SON B Y C, ASI COMO B A C.

Y SE DENOTA DE LA SIGUIENTE MANERA.

OTRO EJEMPLO ES EL SIGUIENTE:

 

Y SE DENOTA DE LA SIGUIENTE MANERA.

Presentado por: Elsa Cortes Rito

COMPONENTES CONEXOS Y PUNTOS DE ARTICULACIÓN

Los puntos de articulación en un grafo no dirigido conexo sin lazos G=(V,E) son los puntos donde el grafo se puede partir o separarse. Si no existen estos puntos entonces el grafo es biconexo.

1.-La raíz es un punto de articulación si y solo si tiene dos o más hijos.

2.-Un nodo cualquiera V distinto de la raíz es un punto de articulación si y solo si bajo>=n[v]

Árboles (Grafos – E1)

Jose Reyes Palacio
Ricardo Santos Cruz

de lamdiscreta

Equipo 2.

3.1.- CONCEPTO DE ÁRBOL

*David Hernandez trinidad.

El árbol es una estructura de datos fundamental en la informática, muy utilizada en todos sus campos, por que se adapta a la representación natural de información organizadas y de una gran comodidad y rapidez de manipulación.
Otra definición de árbol es como tipo de grafo cíclico, conexo y no dirigido.

Las estructuras tipo árbol se usan principalmente para representar datos con una relación jerárquica entre sus elementos, como son árboles genealógicos, tablas, etc.
Un árbol con ningún nodo es un árbol nulo;es decir no tiene raíz.

NODO : Es un punto de intersección o unión de varios elementos que confluyen en el mismo lugar.

La Figura 1.1

La Figura 1.1 muestra un árbol en el que hemos rotulado cada nodo con un tipo de transacción. Los  sub-árboles del raíz  transacción valida son los tipos de transacción y a si respectivamente, donde tipo de transacción  es la raíz de un árbol con un sub-árbol.

  • TERMINOLOGÍA Y REPRESENTACIÓN DE UN ÁRBOL GENERAL

La representación y terminología de los arboles se realiza con las típicas notaciones de las relaciones familiares en los árboles genealógicos: padre, hijo, hermano, ascendente, descendiente, etc.

  • RAIZ: Todos loa árboles que no esta vacíos tienen un único nodo raíz. Todos los demás elementos o nodos derivan o descienden de el. El nodo Raíz no tiene Padre es decir no es hijo de ningún elemento.
  • PADRE: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.
  • HIJO: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.
  • HERMANO: Dos nodos serán hermanos si son descendientes directos de un mismo nodo.
  • HOJA. Se le llama hoja o Terminal a aquellos nodos que no tienen ramificaciones (hijos).
  • NODO. Son los Vértices o elementos del Árbol.
  • NODO INTERIOR. Es un nodo que no es raíz ni Terminal.
  • GRADO. Es el número de descendientes directos de un determinado nodo.
  • GRADO DEL ARBOL Es el máximo grado de todos los nodos del árbol.
  • NIVEL. Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.
  • ALTURA. Es el máximo número de niveles de todos los nodos del árbol. Equivale al nivel más alto de los nodos más 1.
  • PESO. Es el número de nodos terminales del árbol
  • LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.

Ejemplo de la terminologia de un arbol.

FIGURA 1.2 EJEMPLO DE LA TERMINOLOGIA DE UN ARBOL

3.3 BOSQUES DE ARBOL Y COMPONENTES TOPOLOGICOS.

*lennin

Un grafo es conexo si existe un camino entre cualquiera de sus nodos.
Grafo conexo sin ciclos se llama árbol.
Si no es conexo se denomina bosque y cada uno de sus componentes conexos es un árbol.

Ejemplo de un bosque:

Un grafo conexo acíclico algunas veces se conoce como “árbol libre”. Este árbol se puede convertir en ordinario si se elige cualquier vértice deseado como raíz y se orienta cada arista desde ella.

  • Árbol como raíz: es un árbol con vértice marcado como raíz.
  • Árbol libre: un árbol sin marca en alguno de sus vértices.
  • Árbol generador (árbol abarcador): T es un árbol generador de un grafo G si T es un subconjunto de G y V(T) = V(G).

Algoritmo de Prim

Sea V el conjunto de nodos de un grafo pesado no dirigido. El algoritmo de Prim comienza cuando se asigna a un conjunto U de nodos un nodo inicial perteneciente a V, en el cual “crece” un árbol de expansión, arista por arista. En cada paso se localiza la arista más corta (u,v) que conecta a U con V-U, y después se agrega v, el vértice en V-U, a U. Este paso se repite hasta que V=U. El algoritmo de Prim es de O(N2), donde | V | = N.

Algoritmo de Kruskal

El algoritmo de Prim construye un MST una arista a la vez, encontrando una nueva arista que agregar a un MST que va creciendo en cada paso. El algoritmo de Kruskal también construye el MST una arista a la vez, con la diferencia que este encuentra una arista que conecte dos MST que van creciendo dentro de un bosque de MST crecientes, formado de los nodos del grafo original.

El algoritmo comienza a partir de un conjunto de árboles degenerados formados por un solo nodo, que son los nodos del grafo, y se comienzan a combinar los árboles de dos en dos usando la arista menos costosa posible, hasta que solo quede un solo árbol: El MST.

Dada una lista de las aristas del grafo, el primer paso del algoritmo de Kruskal es ordenarlas por peso (usando un quicksort por ejemplo). Luego se van procesando las aristas en el orden de su peso, agregando aristas que no produzcan ciclos en el MST. El algoritmo de Kruskal es de O(A*log2A), donde A es el número de aristas del grafo.

Nota: MTS (Minimum Spanning Tree – Árbol de Expansión Mínimo)

3.3 ORDENAMIENTO TOPOLOGICO

*Sandy Guadalupe Salinas Antonio

Un grafo dirigido es en donde las aristas  del grafo tienen una dirección, son representadas en forma de flechas se debe de tomar en cuenta que para que sea un ordenamiento topológico el grafo no debe contener ciclos, el ordenamiento topológico es una ordenación lineal aquí los nodos deben ser procesados antes que a los nodos a los que apuntan.

EJEMPLO:

  1. Ejecutamos el algoritmo ORDENACIÓN_TOPOLÓGICA (grafo G) sobre el siguiente grafo.

2. El algoritmo nos devuelve una lista enlazada con los nodos del grafo en orden decreciente en tiempo de finalización.

CODIGO:

ORDENACIÓN_TOPOLÓGICA(grafo G)

ORDENACIÓN_TOPOLÓGICA(grafo G)

for each vertice u ∈ V[G]do

estado[u] = NO_VISITADO

padre[u] = NULL

tiempo =0

for each vertice u ∈ V[G]do

if estado[u] = NO_VISITADO then

TOPOLÓGICO-Visitar(u)

TOPOLÓGICO-Visitar(nodo u)

estado[u]=VISITADO

tiempo = tiempo+1

distancia[u] = tiempo

for each v ∈ Adyacencia[u] do

if estado[v]=NO_VISITADO then

padre[v]=u

TOPOLÓGICO-Visitar(v)

estado[u] = TERMINADO

tiempo = tiempo+1

finalización[u] = tiempo

insertar (lista, u)

3.4.-COMPONENTES CONEXOS Y PUNTOS DE ARTICULACION.

* Estefania Cano Martinez

En teoría de grafos, un punto de articulación es un vértice de un grafo tal que al eliminarlo de éste se produce un incremento en el número de componentes conexos. Si el grafo estaba conectado antes de retirar el vértice, entonces pasará a desconectarse. Cualquier grafo conexo con un punto de articulación tiene una conectividad de 1.

A pesar de que estén bien definidos para grafos dirigidos, los puntos de articulación se usan principalmente en los grafos no dirigidos. En general, un grafo conexo, no dirigido y con n vértices, puede tener no más que n-2 punto de articulación. A un grafo sin puntos de articulación se le llama biconexo.

El problema de encontrar los puntos de articulación es el más simple de muchos problemas importantes relacionados con la conectividad de grafos.

Una arista de corte o puente, es una arista análoga a un punto de articulación es decir, una que al eliminarla incrementa el número de componentes conexos del grafo.

En un árbol, cada vértice con grado mayor que 1 es un punto de articulación.

La búsqueda en profundidad es muy útil para encontrar los componentes biconexos de un grafo, este un algoritmo que permite recorrer todos los nodos de un grafo o árbol de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.

Sea  G (V, E) un grafo conexo y  v un vértice de  V. El algoritmo de búsqueda en profundidad puede detallarse así:

1.  Se comienza en un vértice  v (vértice activo) y se toma como la raíz del árbol generador T que se construirá. Se marca el vértice v.

2.  Se elige un vértice u, no marcado, entre los vecinos del vértice activo. Si no existe tal vértice, ir a 4.

3.  Se añade la arista (v, u) al árbol T.  Se marca el vértice u y se toma como activo. Ir al paso 2.

4.  Si se han alcanzado todos los vértices de G el algoritmo termina. En caso contrario, se toma  el vértice padre del vértice activo como nuevo vértice activo y se vuelve al paso

Ejemplo: hallar los puntos de articulación.

En esta figura solo existe un punto de articulación que es “a”.

Pagina recomendada: http://www.udg.co.cu/cmap/estrdatos/Grafos/Grafos-Web/index.htm

de lamdiscreta