Hoy en da es rara la disciplina cientfica o humanstica que no utiliza la teora de grafos. Como ejemplos podemos citar la psicologa en dinmica de grupos, la sociologa en los sociogramas, la fsica terica, que usa los diagramas de Feynmann, donde se representan mediante lneas las partculas elementales, el estudio de flujos en redes en programacin lineal e investigacin operativa, los cambios de variable en el clculo diferencial...Dibujar un grafo para resolver un problema es un reflejo muy comn, que no precisa conocimientos matemticos. Un grafo se parece a la figura siguiente, y consta devrticesy dearistasque renen algunos de ellos.En la teora de los grafos, slo se queda lo esencial del dibujo: la forma de las aristas no son relevantes, slo importan sus extremidades (o cabos); la posicin de los vertices tampoco, y se puede variar para obtener un grafo ms claro, y hasta sus nombres se pueden cambiar. Estos cambios se llamanisomorfismosde grafos. Generalmente, se considera que colocar los vrtices en forma de polgono regular da grafos muy lebles.

1.) EL ORIGEN DE LA TEORA DE GRAFOSse remonta alsiglo XVIIIcon elproblema de los puentes de Knigsberg, el cual consista en encontrar un camino que recorriera los siete puentes en la ciudad deKnigsberg, actualmenteKaliningrado, de modo que se recorrieran todos los puentes pasando una sola vez por cada uno de ellos. El trabajo deLeonhard Eulersobre el problema tituladoSolutio problematis ad geometriam situs pertinentis1(La solucin de un problema relativo a la geometra de la posicin) en1736, es considerado el primer resultado de la teora de grafos. Tambin se considera uno de los primeros resultados topolgicos en geometra (que no depende de ninguna medida). Este ejemplo ilustra la profunda relacin entre la teora de grafos y latopologa.

Los puentes de KnigsbergComenzamos esta semana con una entrada dedicada a un problema clsico pero no por ello falto de inters:los puentes de Konigsberg. Clsico porque es un problema muy conocido y estudiado; interesante porque est considerado como el comienzo de la topologa, y, en particular, de la teora de grafos.El artculo consta de cuatro partes: descripcin del problema y encuadre histrico del mismo, iniciacin a la teora de grafos, resolucin del problema y aplicacin a

la resolucin del problema del sobre y similares.Knigsberg (actualmente Kaliningrado, Rusia) era una ciudad de Prusia del siglo XVIII. El problema que nos ocupa tiene como protagonista a un ro, el ro Pregel, que cruzaba la ciudad, a dos islas que se encontraban en el mismo y a siete puentes que comunicaban las dos partes de la ciudad con las mismas. Concretamente la situacin era como se describe en la imagen (yson las dos partes de la ciudad yylas dos islas):

El problema consista en comenzar en un punto, pasar por los siete puentes sin repetir ninguno y volver al punto de partida. Antes de seguir leyendo podis intentarlo vosotros mismos, aunque os recomiendo que no le dediquis demasiado tiempo.Resolucin del problemaPara empezar, quin resolvi el problema? Pues como ya sabis los que conocais el problema y como habris intuido los que no lo conocais fueLeonhard Eulerquien dio solucin a este asunto. La idea genial de Euler fue representar la ciudad de Knigsberg como un grafo en el que las cuatro partes de la misma eran los vrtices y los siete puentes eran las aristas:

Por tanto el problema de los puentes de Knigsberg pasa a ser un problema de teora de grafos cuya solucin public Euler en su artculoSolucin de un problema relativo a la geometra de posicin

Luego, en1847,Gustav Kirchhoffutiliz la teora de grafos para el anlisis de redes elctricas publicando sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos elctricos, conocidas comoleyes de Kirchhoff, considerado la primera aplicacin de la teora de grafos a un problema deingeniera.En1852Francis Guthrieplante elproblema de los cuatro colores. Este problema, que no fue resuelto hasta un siglo despus porKenneth AppelyWolfgang Hakenen1976, puede ser considerado como el nacimiento de la teora de grafos. Al tratar de resolverlo, los matemticos definieron trminos y conceptos tericos fundamentales de los grafos.En1857,Arthur Cayleyestudi y resolvi el problema de enumeracin de losismeros, compuestos qumicos con idntica composicin (frmula) pero diferente estructura molecular. Para ello represent cadacompuesto, en este casohidrocarburos saturadosCnH2n+2, mediante un graforboldonde los vrtices representantomosy las aristas la existencia deenlaces qumicos.El trminografo, proviene de la expresinHgraphic notationusada por primera vez porEdward Frankland2y posteriormente adoptada porAlexander Crum Brownen1884, y haca referencia a la representacin grfica de los enlaces entre los tomos de unamolcula.Iniciacin a la teora de grafosUngrafoes bsicamente un conjunto no vaco (al menos contiene un elemento) de puntos llamadosvrticesy un conjunto de lneas llamadasaristascada una de las cuales une dos vrtices. Se llamalazoa una arista que une un vrtice consigo mismo. Se dice que dos vrtices sonadyacentessi existe una arista que los une.

Matriz y grafosEnteora de los grafos Una matriz cuadrada est representada por los coeficientes son 0 o 1FILA I1234

COLUMNA J

10101

2

3

4

1 2

3 4 VERTICE

En lateora de grafos, se llama matriz de un grafo a la matriz que indica en la lnea i y la columna j el nmero de aristas que enlazan el vrtice i al vrtice j.

VECTORSegmento de recta, contado a partir de un punto del espacio, cuya longitud representa a escala una magnitud, en una direccin determinada y en uno de sus sentidos

2. QUE ES LATEORA DE GRAFOS(TAMBIN LLAMADATEORA DE LAS GRFICAS)es un campo de estudio de lasmatemticasy lasciencias de la computacin, que estudia las propiedades de losgrafos(tambin llamadasgrficas, que no se debe confundir con lasgrficas que tienen una acepcin muy amplia) estructuras que constan de dos partes, elconjuntodevrtices, nodos o puntos; y el conjunto dearistas, lneas o lados (edgesen ingls) que pueden serorientadoso no.La teora de grafos es una rama de lasmatemticas discretasy de lasmatemticas aplicadas, y es un tratado que usa diferentes conceptos de diversas reas comocombinatoria,lgebra,probabilidad,geometrade polgonos,aritmticay topologa.Actualmente ha tenido mayor preponderancia en el campo de lainformtica, lasciencias de la computaciny telecomunicaciones.6.1.1 Composicin de un grafoAristas Son las lneas con las que se unen los vrtices de un grafo y con la que se construyen tambin caminos.. Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vrtice. Aristas Paralelas: Se dice que dos aristas son paralelas si vrtice inicial y el final son el mismo. Aristas Cclicas: Arista que parte de un vrtice para entrar en el mismo. Cruce: Son dos aristas que cruzan en un punto. Vrtices Son los puntos o nodos con los que est conformado un grafo. Llamaremos grado de un vrtice al nmero de aristas de las que es extremo. Se dice que un vrtice es `par' o `impar' segn lo sea su grado. Vrtices Adyacentes: si tenemos un par de vrtices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vrtices adyacentes y se dice que U es el vrtice inicial y V el vrtice adyacente. Vrtice Aislado: Es un vrtice de grado cero. Vrtice Terminal: Es un vrtice de grado 1.

APLICACIONES DE LA TEORIA DE GRAFOSGracias a la teora de grafos se pueden resolver diversos problemas como por ejemplo la sntesis decircuitossecuenciales, contadores o sistemas de apertura. Se utiliza para diferentes reas por ejemplo, Dibujo computacional, en toda las reas de Ingeniera.circuito secuencial Los grafos se utilizan tambin para modelar trayectos como el de una lnea de autobs a travs de las calles de una ciudad, en el que podemos obtener caminos ptimos para el trayecto aplicando diversosalgoritmoscomo puede ser el algoritmo deFloyd.

Para la administracin de proyectos, utilizamos tcnicas comotcnica de revisin y evaluacin de programas(PERT) en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.La teora de grafos tambin ha servido de inspiracin para las ciencias sociales, en especial para desarrollar un concepto no metafrico dered socialque sustituye los nodos por los actores sociales y verifica la posicin, centralidad e importancia de cada actor dentro de la red. Esta medida permite cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse grficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al identificar los vnculos (aristas), su direccin e intensidad y da idea de la manera en que el poder se transmite y a quines.Se emplea en problemas de control de produccin, para proyectar redes de ordenadores, para disear mdulos electrnicos modernos y proyectar sistemas fsicos con parmetros localizados (mecnicos, acsticos y elctricos).Se usa para la solucin de problemas de gentica y problemas de automatizacin de la proyeccin (SAPR). Apoyo matemtico de los sistemas modernos para el procesamiento de la informacin. Acude en las investigaciones nucleares (tcnica de diagramas de Feynman. Los grafos son importantes en el estudio de labiologay hbitat. El vrtice representa un hbitat y las aristas (o "edges" en ingls) representa los senderos de los animales o las migraciones. Con esta informacin, los cientficos pueden entender cmo esto puede cambiar o afectar a las especies en su hbitat.

TEORA DE GRAFOS Y CONTABILIDADPara aplicar la teora de grafos a la contabilidad consideraremos que los elementos de la coleccin son las cuentas del sistema contable y las relaciones entre los elementos son las transferencias de recursos entre las cuentas.La propiedad general de las cuentas se definir as: Desde una cuenta Xia otra cuenta Xjse pueden transferir recursos, tales como dinero, mercancas, bienes econmicos y derechos legales debidamente medidos en unidades monetarias.Para representar una transferencia de recursos desde Cia Cj, se trazar en el plano una lnea, orientada (arco) desde Cia Cj. Encima de cada arco se escribir una cifra, Nij, que indique la medida en unidades monetarias de la transferencia. Esta cifra ser la relacin entre las dos cuentas y se denominar nmero asociado al arco.Ci cj Transferencia de informacin de las operaciones

3. TIPOS DE GRAFOS. Grafo simple.o simplementegrafoes aquel que acepta una sola arista uniendo dos vrtices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la nica que une dos vrtices especficos. Es la definicin estndar de un grafo.

Multgrafo. opseudografoson grafos que aceptan ms de una arista entre dos vrtices. Estas aristas se llamanmltiplesolazos(loopseningls). Losgrafos simplesson una subclase de esta categora de grafos. Tambin se les llamagrafos no-dirigido.

Grafo dirigido. Son grafos en los cuales se ha aadido unaorientacina las aristas, representada grficamente por una flecha

Grafo etiquetado. Grafos en los cuales se ha aadido unpesoa las aristas (nmero enterogeneralmente) o unetiquetadoa los vrtices.

Grafo aleatorio. Grafo cuyas aristas estn asociadas a unaprobabilidad.

Tienen estructuras tpicas de procesos aleatorios Hipergrafo. Grafos en los cuales las aristas tienen ms de dos extremos, es decir, las aristas son incidentes a 3 o ms vrtices.

Grafo infinito. Grafos con conjunto de vrtices y aristas decardinal infinito.

El cardinal indica el nmero o cantidad de elementos de un conjunto, en este caso es infinita

4. REPRESENTACIN DE LOS GRAFOSExisten diferentes formas de representar un grafo (simple), adems de la geomtrica y muchos mtodos para almacenarlos en una computadora. Laestructura de datosusada depende de las caractersticas del grafo y elalgoritmousado para manipularlo. Entre las estructuras ms sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinacin de ambas. Las listas son preferidas engrafos dispersosporque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rpido, pero pueden consumir grandes cantidades de memoria.Estructura de lista lista de incidencia- Las aristas son representadas con unvectorde pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas. lista de adyacencia- Cada vrtice tiene una lista de vrtices los cuales son adyacentes a l. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las bsquedas son ms rpidas, al costo de almacenamiento extra. lista de grados- Tambin llamadasecuencia de gradososucesin grficade un grafo no-dirigido es una secuencia de nmeros, que corresponde a los grados de los vrtices del grafo.

Estructuras matriciales Matriz de adyacencia- El grafo est representado por una matriz cuadrada M de tamao, dondees el nmero de vrtices. Si hay una arista entre un vrtice x y un vrtice y, entonces el elementoes 1, de lo contrario, es 0. Matriz de incidencia- El grafo est representado por unamatrizde A (aristas) por V (vrtices), donde [vrtice, arista] contiene la informacin de la arista (1 - conectado, 0 - no conectado)

5. PROBLEMAS DE TEORA DE GRAFOSCiclos y caminos hamiltonianosUncicloes una sucesin de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Unciclo hamiltonianotiene adems que recorrer todos los vrtices exactamente una vez (excepto el vrtice del que parte y al cual llega).Por ejemplo, en un museo grande (al estilo delLouvre), lo idneo sera recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vrtices son las salas, y las aristas los corredores o puertas entre ellas).Se habla tambin deCamino hamiltonianosi no se impone regresar al punto de partida, como en un museo con una nica puerta de entrada. Por ejemplo, un caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano. Ejemplo de un ciclo hamiltoniano en el grafo deldodecaedro.Hoy en da, no se conocen mtodos generales para hallar un ciclo hamiltoniano entiempo polinmico, siendo la bsqueda por fuerza bruta de todos los posibles caminos u otros mtodos excesivamente costosos. Existen, sin embargo, mtodos para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeos.El problema de determinar la existencia de ciclos hamiltonianos, entra en el conjunto de losNP-completos.

Un grafo esplanosi se puede dibujar sin cruces de aristas. Elproblema de las tres casas y los tres pozostiene solucin sobre el toro, pero no en el plano.Grafos planos Cuando un grafo o multigrafo se puede dibujar en un plano sin que dos segmentos se corten, se dice que es plano.Un juego muy conocido es el siguiente: Se dibujan tres casas y tres pozos. Todos los vecinos de las casas tienen el derecho de utilizar los tres pozos. Como no se llevan bien en absoluto, no quieren cruzarse jams. Es posible trazar los nueve caminos que juntan las tres casas con los tres pozos sin que haya cruces?Cualquier disposicin de las casas, los pozos y los caminos implica la presencia de al menos un cruce.

Sea Knelgrafo completoconnvrtices, Kn, pes elgrafo bipartitodenypvrtices.El juego anterior equivale a descubrir si elgrafo bipartito completoK3,3esplano, es decir, si se puede dibujar en un plano sin que haya cruces, siendo la respuesta que no. En general, puede determinarse que un grafonoes plano, si en su diseo puede encontrase una estructura anloga (conocida comomenor) a K5o a K3,3.Establecer qu grafos son planos no es obvio, y es un problema que tiene que ver contopologa.Coloracin de grafos

Teorema de los cuatro coloresGrafo dualasociado al mapa con una4-vrtice coloracin.Otro problema famoso relativo a los grafos: Cuntos colores son necesarios para dibujar un mapa poltico, con la condicin obvia que dos pases adyacentes no puedan tener el mismo color? Se supone que los pases son de un solo pedazo, y que el mundo es esfrico o plano. En un mundo en forma de toroide; el teorema siguiente no es vlido:Cuatro colores son siempre suficientes para colorear un mapa.El mapa siguiente muestra que tres colores no bastan: Si se empieza por el pas centralay se esfuerza uno en utilizar el menor nmero de colores, entonces en la corona alrededor dea alternan dos colores. Llegando al pashse tiene que introducir un cuarto color. Lo mismo sucede enisi se emplea el mismo mtodo.La forma precisa de cada pas no importa; lo nico relevante es saber qu pas toca a qu otro. Estos datos estn incluidos en el grafo donde los vrtices son los pases y las aristas conectan los que justamente son adyacentes. Entonces la cuestin equivale a atribuir a cada vrtice un color distinto del de sus vecinos.Hemos visto que tres colores no son suficientes, y demostrar que con cinco siempre se llega, es bastante fcil. Pero el teorema de los cuatro colores no es nada obvio. Prueba de ello es que se han tenido que emplear ordenadores para acabar la demostracin (se ha hecho un programa que permiti verificar una multitud de casos, lo que ahorr muchsimo tiempo a los matemticos). Fue la primera vez que la comunidad matemtica acept una demostracin asistida por ordenador, lo que cre en su da una cierta polmica dentro de la comunidad matemtica.

CARACTERISTICAS DE LOS GRAFOSGrafo ES completoUn grafo escompletosi existen aristas uniendotodoslos pares posibles de vrtices. Es decir, todo par de vrtices (a, b) debe tener una aristaeque los une.

GRAFO ES CONEXOSe dice que un grafo esconexosi no puede expresarse como la unin de dos grafos de vrtices disjuntos. Os dejo un ejemplo:NO CONEXO HAY DESUNION

Grafo ES bipartitoUn grafo G es bipartito si puede expresarse como(es decir, sus vrtices son la unin de dos grupos de vrtices), bajo las siguientes condiciones: yson disjuntos y no vacos. Cada arista de A une un vrtice de V1con uno de V2. No existen aristas uniendo dos elementos de V1; anlogamente para V2.Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios en los que debe unirse un elemento de la columna A con un elemento de la columna B.

Homeomorfismo de grafosDos grafosyson homeomorfos si ambos pueden obtenerse a partir del mismo grafo con una sucesin desubdivisiones elementalesde aristas.

rbolesUn grafo que no tiene ciclos y que conecta a todos los puntos, se llama unrbol. En un grafo connvrtices, los rboles tienen exactamenten - 1aristas, y haynn-2rboles posibles. Su importancia radica en que los rboles son grafos que conectan todos los vrtices utilizando el menor nmero posible de aristas. Un importante campo de aplicacin de su estudio se encuentra en elanlisis filogentico, el de la filiacin de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguacin del parentesco entre especies; aunque se ha usado tambin, por ejemplo, en el estudio del parentesco entre lenguas.

Grafos ponderados o etiquetadosEn muchos casos, es preciso atribuir a cada arista un nmero especfico, llamadovaluacin,ponderacinocostesegn el contexto, y se obtiene as ungrafo valuado.Formalmente, es un grafo con una funcin v: A R+.Por ejemplo, un representante comercial tiene que visitarnciudades conectadas entre s por carreteras; su inters previsible ser minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendr como vrtices las ciudades, como aristas las carreteras y la valuacin ser la distancia entre ellas. Y, de momento, no se conocen mtodos generales para hallar un ciclo de valuacin mnima, pero s para los caminos desdeahastab, sin ms condicin.

DimetroEn la figura se nota que K4es plano (desviando la aristaabal exterior del cuadrado), que K5no lo es, y que K3,2lo es tambin (desvos en gris).

En un grafo, la distancia entre dos vrtices es el menor nmero de aristas de un recorrido entre ellos. Eldimetro, en una figura como en un grafo, es la mayor distancia de entre todos los pares de puntos de la misma.El mundo de Internet ha puesto de moda esa idea del dimetro: Si descartamos los sitios que no tienen enlaces, y escogemos dos pginaswebalazar: En cuntosclicsse puede pasar de la primera a la segunda? El resultado es el dimetro de la Red, vista como un grafo cuyos vrtices son los sitios, y cuyas aristas son lgicamente los enlaces.En el mundo real hay una analoga: tomando al azar dos seres humanos del mundo, En cuntos saltos se puede pasar de uno a otro, con la condicin de slo saltar de una persona a otra cuando ellas se conocen personalmente? Con esta definicin, se estima que el dimetro de la humanidad es de... ocho solamente!Este concepto refleja mejor la complejidad de una red que el nmero de sus elementos.Redes teorema de flujo mximo teorema de flujo mnimo pareos y redes de PetriUna Red de Transporte es una grafica dirigida, simple, con pesos y que debe cumplir las siguientes: Poseer una fuente o vrtice fijo que no tiene aristas de entrada. Poseer un sumidero o vrtice fijo que no tiene arista de salida El peso Cij de la arista dirigida de i a j llamado capacidad de ij es un numero no negativo.

Ejemplo de una red que parte de un punto a que es un Muelle y llega a un punto z que es una refinera. Teorema de flujo mximo. Siendo G una red de trasporte, un flujo mximo es un flujo con valor mximo. En general, habr varias flujos con el mismo valor mximo. La idea es sencilla: comenzar con cierto flujo inicial e incrementar de forma iterativa hasta que no pueda mejorarse ms. El flujo resultante ser el mximo. Para aumentar el valor de un flujo dado, debemos determinar un camino de la fuente al sumidero e incrementar el flujo a lo largo de ese camino. Teorema del flujo mnimo. En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedando partes disjuntas del conjunto de vrtices, V1 y V2 que, situados en la red, dejan la fuente en una de ellas y al sumidero en la otra. Se llama capacidad de un corte a la suma: Capacidad (v,w) ; vV1, w?V2 V1es la parte que contiene a la fuente V2 es la parte que contiene al sumidero Sea F un flujo en G y sea (P, P) un corte en G. Entonces la capacidad de (p, p) es mayor o igual que el valor de FRedes de Petri

Una red de Petri es un grafo orientado con dos tipos de nodos: lugares (representados mediante circunferencias) y transiciones (representadas por segmentos rectos verticales). Los lugares y las transiciones se unen mediante arcos o flechas

Un arco une siempre lugares con transiciones y nunca dos lugares o dos transiciones. Una transicin puede ser destino de varios lugares y un lugar puede ser el destino de varias transiciones. Una transicin puede ser origen de varios lugares y un lugar puede ser origen de varias transiciones Los lugares pueden presentar marcas (una marca se representa mediante un punto en el interior del crculo).Cada lugar tiene asociada una accin o salida. Los lugares que contienen marcas se consideran lugares activos. Cuando un lugar est activo sus salidas estn a uno. A las transiciones se les asocia eventos (funciones lgicas de las variables de entrada).Una transicin se dice que est sensibilizada cuando todos su lugares origen estn marcados. Cuando ocurre un evento asociado a una transicin (la funcin lgica se hace uno), se dice que la transicin est validada.