TRABAJO ESCRITO SOBRE OPERACIONES DE GRAFOS

EDGAR YESID CORTES INSUASTYDAVID ENRIQUE MAECHA

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDASFACULTAD INGENIERIASISTEMASVI SEMESTRECONSULTABOGOTA2014

TRABAJO ESCRITO SOBRE INDICE DE OPERACIONES DE GRAFOS

EDGAR YESID CORTES INSUASTYDAVID ENRIQUE MAECHA

DOCENTEJULIO FLOREZ SANCHEZ

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDASFACULTAD INGENIERIASISTEMASVI SEMESTRECONSULTABOGOTA2014ContenidoINTRODUCCION4OPERACIONES ENTRE GRAFOS5UNION5INTERSECCION5SUMA ANILLO6FUSION DE VERTICES6ADICION DE UNA ARISTA6EJERCICIOS PROPUESTOS8BIBLIOGRAFIA9

INTRODUCCIONEl origen de la palabra grafo es griego y su significado etimolgico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos podran ser los siguientes: un grfico de una serie de tareas a realizar indicando su secuenciacin (un organigrama), grafos matemticos que representan las relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o areos o la red elctrica de una ciudad. En cada caso, es conveniente representar grficamente el problema dibujando un grafo como un conjunto de puntos(vrtices)con lneas conectndolos (arcos).

OPERACIONES ENTRE GRAFOSPuesto que los grafos son definidos en trminos de los conjuntos de vrtices y aristas, es natural que las operaciones definidas en la teora de conjuntos puedan ser aplicadas a la Teora de grafos.Sean G1 = (V1,A1,fG1) y G2 = (V2,A2,fG2) dos subgrafos de un grafo G = (V,A,fG)

UNIONLa unin de los subgrafos G,G1 y G2, es otro subgrafo G3 = (V3,A3,fG3) de G tal queV3 = V1 U V2, A3 = A1 U A2 y FG3 asigna a toda arista de A3 un par de vrtices de VINTERSECCIONSean V1 V2 0 la interseccin de los subgrafos G1 y G2,G1G2, es otro subgrafo.G4 = (V4, A4, fG4) de G, tal que V4 = V1 V2 , A4 = A1 A2 y FG4 asigna a toda arista de A4 un par de vrtices de V4.

SUMA ANILLOLa suma anillo de los subgrafos G1 y G2, G1o G2, es otro subgrafo G5 = (V5, A5, FG5) de G, tal que V5 = V1U V2, A5= (A1U A2) (A1U A2) y FG5 asigna a toda arista A5 un par de vrtices de V5.(1) Sean M y N dos conjuntos . La diferencia simtrica de M y N, escrita (M U N) (M N), es el conjunto de todos los elementos que pertenecen a M U N, pero que no pertenecen a M N.Las tres operaciones mencionadas son conmutativas, es decir:G1U G2= G2U G1, G1 G2 = G2 G1 y G1G2 = G2G1Si G1 y G2 son arista-disjuntos entonces G1 G2 es igual al grafo vacio y G1 G2= G1 U G2. Si G1 y G2 son vrtice-disjuntos, entonces G1 G2 no esta definido Para todo grafo G se tiene que:G U G = G G = GG G es igual a grafo vacio. Si G1 es un grafo de G, entonces G G1 = G A(G1)FUSION DE VERTICES Un par de vrtices a y b de un grafo G se dice que ha sido Fusionados, si los vrtices son remplazados por un nuevo vrtice, tal que toda arista incidente en a o en b, o en ambos es Incidente en el nuevo vrtice.ADICION DE UNA ARISTASea G = ( V, A, f ) un grafo y u y v dos vrtices de G. El grafo G+a, donde f(a) = uv denota el grafo cuyo conjunto de vrtices es V(G) y cuyo conjunto de aristas es A(G) U {a} esta operacin se llama adicin de una arista a.INSERTAR VERTICE La operacin de insercin de un nuevo vrtice es una operacin muy sencilla, nicamente consiste en aadir una nueva entrada en la tabla de vrtices (estructura de datos que almacena los vrtices) para el nuevo nodo. A partir de ese momento el grafo tendr un vrtice ms, inicialmente aislado, ya que ningna arista llegar a l.INSERTAR ARISTAEsta operacin es tambin muy sencilla. Cuando se inserte una nueva arista en el grafo, habr que aadir un nuevo nodo a la lista de adyacencia (lista que almacena los nodos a los que un vrtice puede acceder mediante una arista) del nodo origen, as si se aade la arista (A,C), se deber incluir en la lista de adyacencia de A el vrtice C como nuevo destino.ELIMINAR VERTICE Esta operacin es inversa a la insercin de vrtice. En este caso el procedimiento a realizar es la eliminacin de la tabla de vrtices del vrtice en s. A continuacin habr que eliminar las aristas que tuviesen al vrtice borrado como origen o destino.ELIMINAR ARISTAMediante esta operacin se borra un arco del grafo. Para llevar a cabo esta accin es necesario eliminar de la lista de adyacencia del nodo origen el nodo correspondiente al nodo destino.

EJERCICIOS PROPUESTOS Halle la unin entre G1 Y G2Sol: Halle la interseccin entre G1 Y G2Sol:

Halle la suma anillo entre G1 Y G2Sol:

Realice la fusin de vrtices con el siguiente grafo GSol:

BIBLIOGRAFIA

http://es.wikipedia.org/wiki/Uni%C3%B3n_de_grafoshttp://teoriadegrafos.blogspot.com/2007/03/grafo-interseccin.html