5/19/2018 Teora de Grafos

1/8

Teora de grafos

Losgrafosson el objeto de estudio de esta rama de lasmatemticas. Arriba elgrafo pez, en medio elgrafo arcoy abajo elgrafo dodecaedro.

Lateora de grafos(tambin llamadateora de las gr-ficas) es un campo de estudio de las matemticasy las

ciencias de la computacin, que estudia las propiedadesde losgrafos(tambin llamadasgrficas, que no se debeconfundir con lasgrficasque tienen una acepcin muyamplia) estructuras que constan de dos partes, el conjuntodevrtices, nodos o puntos; y el conjunto de aristas, l-neas o lados (edgesen ingls) que pueden serorientadoso no.

La teora de grafos es una rama de laMatemtica discre-tay de lasaplicadas, y es un tratado que usa diferentesconceptos de diversas reas comoAnlisis combinatorio,lgebra abstracta,probabilidad,geometrade polgonos,aritmticaytopologa.

Actualmente ha tenido mayor preponderancia en el cam-po de lainformtica, lasciencias de la computacin ytelecomunicaciones.

1 Historia

Los 7 puentes del ro Pregel en Knigsberg.

El origen de la teora de grafos se remonta al sigloXVIIIcon elproblema de los puentes de Knigsberg, elcual consista en encontrar un camino que recorriera los

siete puentes delro Pregel(544212N 203056E /54.70333, 20.51556) en la ciudad deKnigsberg, actual-menteKaliningrado, de modo que se recorrieran todoslos puentes pasando una sola vez por cada uno de ellos.El trabajo deLeonhard Eulersobre el problema tituladoSolutio problematis ad geometriam situs pertinentis[1] (Lasolucin de un problema relativo a la geometra de la po-sicin) en1736, es considerado el primer resultado de lateora de grafos. Tambin se considera uno de los prime-ros resultados topolgicos en geometra (que no dependede ninguna medida). Este ejemplo ilustra la profunda re-lacin entre la teora de grafos y latopologa.

Luego, en 1847, Gustav Kirchhoff utiliz la teora de gra-fos para el anlisis de redes elctricas publicando sus leyesde los circuitos para calcular el voltaje y la corriente en loscircuitos elctricos, conocidas comoleyes de Kirchhoff,considerado la primera aplicacin de la teora de grafos aun problema deingeniera.

En1852 Francis Guthrieplante elproblema de los cua-tro coloresel cual afirma que es posible, utilizando sola-mente cuatro colores, colorear cualquier mapa de pasesde tal forma que dos pases vecinos nunca tengan el mis-mo color. Este problema, que no fue resuelto hasta unsiglo despus porKenneth AppelyWolfgang Hakenen

1976, puede ser considerado como el nacimiento de lateora de grafos. Al tratar de resolverlo, los matemticosdefinieron trminos y conceptos tericos fundamentales

1

https://es.wikipedia.org/wiki/1976https://es.wikipedia.org/wiki/Wolfgang_Hakenhttps://es.wikipedia.org/wiki/Kenneth_Appelhttps://es.wikipedia.org/wiki/Teorema_de_los_cuatro_coloreshttps://es.wikipedia.org/wiki/Teorema_de_los_cuatro_coloreshttps://es.wikipedia.org/wiki/Francis_Guthriehttps://es.wikipedia.org/wiki/1852https://es.wikipedia.org/wiki/Ingenier%C3%ADahttps://es.wikipedia.org/wiki/Leyes_de_Kirchhoffhttps://es.wikipedia.org/wiki/Gustav_Kirchhoffhttps://es.wikipedia.org/wiki/1847https://es.wikipedia.org/wiki/Topolog%C3%ADahttps://es.wikipedia.org/wiki/1736https://es.wikipedia.org/wiki/Leonhard_Eulerhttps://es.wikipedia.org/wiki/Kaliningradohttps://es.wikipedia.org/wiki/K%C3%B6nigsberghttp://tools.wmflabs.org/geohack/geohack.php?language=es&pagename=Teor%25C3%25ADa_de_grafos&params=54_42_12_N_20_30_56_E_region:RU_source:nlwikihttp://tools.wmflabs.org/geohack/geohack.php?language=es&pagename=Teor%25C3%25ADa_de_grafos&params=54_42_12_N_20_30_56_E_region:RU_source:nlwikihttps://es.wikipedia.org/wiki/R%C3%ADo_Pregolyahttps://es.wikipedia.org/wiki/Problema_de_los_puentes_de_K%C3%B6nigsberghttps://es.wikipedia.org/wiki/Siglo_XVIIIhttps://es.wikipedia.org/wiki/Siglo_XVIIIhttps://es.wikipedia.org/wiki/Telecomunicacioneshttps://es.wikipedia.org/wiki/Ciencias_de_la_computaci%C3%B3nhttps://es.wikipedia.org/wiki/Inform%C3%A1ticahttps://es.wikipedia.org/wiki/Topolog%C3%ADahttps://es.wikipedia.org/wiki/Aritm%C3%A9ticahttps://es.wikipedia.org/wiki/Geometr%C3%ADahttps://es.wikipedia.org/wiki/Probabilidadhttps://es.wikipedia.org/wiki/%C3%81lgebrahttps://es.wikipedia.org/wiki/Combinatoriahttps://es.wikipedia.org/wiki/Matem%C3%A1ticas_aplicadashttps://es.wikipedia.org/wiki/Matem%C3%A1ticas_discretashttps://es.wikipedia.org/wiki/Matem%C3%A1ticas_discretashttps://es.wikipedia.org/wiki/Grafo_dirigidohttps://es.wikipedia.org/wiki/Arista_(Teor%C3%ADa_de_grafos)https://es.wikipedia.org/wiki/V%C3%A9rtice_(Teor%C3%ADa_de_grafos)https://es.wikipedia.org/wiki/Conjunto_finitohttps://es.wikipedia.org/wiki/Gr%C3%A1ficahttps://es.wikipedia.org/wiki/Grafohttps://es.wikipedia.org/wiki/Ciencias_de_la_computaci%C3%B3nhttps://es.wikipedia.org/wiki/Matem%C3%A1ticashttps://es.wikipedia.org/wiki/Grafo_dodecaedrohttps://es.wikipedia.org/wiki/Grafo_arcohttps://es.wikipedia.org/wiki/Grafo_pez

5/19/2018 Teora de Grafos

2/8

2 3 TIPOS DE GRAFOS

de los grafos.

En1857,Arthur Cayleyestudi y resolvi el problema deenumeracin de losismeros, compuestos qumicos conidntica composicin (frmula) pero diferenteestructuramolecular. Para ello represent cadacompuesto, en este

casohidrocarburos saturadosCH, mediante un graforboldonde los vrtices representantomosy las aristasla existencia deenlaces qumicos.

El trminografo, proviene de la expresinHgraphicnotationusada por primera vez porEdward Frankland[2]

y posteriormente adoptada porAlexander Crum Brownen1884, y haca referencia a la representacin grfica delos enlaces entre los tomos de unamolcula.

El primer libro sobre teora de grafos fue escrito porDnes Knigy publicado en1936.[3]

2 Aplicaciones

Gracias a la teora de grafos se pueden resolver diversosproblemas como por ejemplo la sntesis decircuitosse-cuenciales, contadores o sistemas de apertura. Se utilizapara diferentes reas por ejemplo, Dibujo computacional,en toda las reas de Ingeniera.

Los grafos se utilizan tambin para modelar trayectos co-mo el de una lnea de autobs a travs de las calles de unaciudad, en el que podemos obtener caminos ptimos parael trayecto aplicando diversosalgoritmoscomo puede serel algoritmo deFloyd.Para la administracin de proyectos, utilizamos tcnicascomoPERTen las que se modelan los mismos utilizan-do grafos y optimizando los tiempos para concretar losmismos.

La teora de grafos tambin ha servido de inspiracin paralas ciencias sociales, en especial para desarrollar un con-cepto no metafrico dered socialque sustituye los nodospor los actores sociales y verifica la posicin, centralidade importancia de cada actor dentro de la red. Esta medi-da permite cuantificar y abstraer relaciones complejas, de

manera que la estructura social puede representarse grfi-camente. Por ejemplo, una red social puede representar laestructura de poder dentro de una sociedad al identificarlos vnculos (aristas), su direccin e intensidad y da ideade la manera en que el poder se transmite y a quines.

Se emplea en problemas de control de produccin, pa-ra proyectar redes de ordenadores, para disear mduloselectrnicos modernos y proyectar sistemas fsicos conparmetros localizados (mecnicos, acsticos y elctri-cos).

Se usa para la solucin de problemasde gentica y proble-mas de automatizacin de la proyeccin (SAPR). Apoyo

matemtico de los sistemas modernos para el procesa-miento de la informacin. Acude en las investigacionesnucleares (tcnica de diagramas de Feynman).[4]

Los grafos son importantes en el estudio de la biologay hbitat. El vrtice representa un hbitat y las aristas (oedges en ingls) representa los senderos de los animaleso las migraciones. Con esta informacin, los cientficospueden entender cmo esto puede cambiar o afectar a lasespecies en su hbitat.

Mapas conceptuales

Plano de estaciones delmetro.

Plano deautopistas.

Circuito elctrico

Sociogramade unared social

Topologa de reddecomputadores

Organigramas

Isomeros

Arquitectura de redesdetelefona mvil

Draws deeliminacin directa(ej:tenis)

3 Tipos de grafos

Grafo simple. o simplemente grafoes aquel queacepta una sola arista uniendo dos vrtices cuales-quiera. Esto es equivalente a decir que una aristacualquiera es la nica que une dos vrtices especfi-cos. Es la definicin estndar de un grafo.

Multigrafo. opseudografoson grafos que aceptanms de una arista entre dos vrtices. Estas aristas sellamanmltiplesolazos(loopseningls). Losgrafossimplesson una subclase de esta categora de grafos.Tambin se les llamagrafos no-dirigido.

Grafo dirigido. Son grafos en los cuales se ha aa-

dido unaorientacina las aristas, representada gr-ficamente por una flecha

Grafo etiquetado. Grafos en los cuales se ha aadi-do unpesoa las aristas (nmero enterogeneralmen-te) o unetiquetadoa los vrtices.

Grafo aleatorio. Grafo cuyas aristas estn asocia-das a unaprobabilidad.

Hipergrafo. Grafos en los cuales las aristas tienenms de dos extremos, es decir, las aristas son inci-dentes a 3 o ms vrtices.

Grafo infinito. Grafos con conjunto de vrtices yaristas decardinal infinito.

https://es.wikipedia.org/wiki/Infinitohttps://es.wikipedia.org/wiki/Grafo_infinitohttps://es.wikipedia.org/wiki/Hipergrafohttps://es.wikipedia.org/wiki/Probabilidadhttps://es.wikipedia.org/wiki/Grafo_aleatoriohttps://es.wikipedia.org/wiki/N%C3%BAmero_enterohttps://es.wikipedia.org/wiki/Grafo_etiquetadohttps://es.wikipedia.org/wiki/Grafo_dirigidohttps://es.wikipedia.org/wiki/Idioma_ingl%C3%A9shttps://es.wikipedia.org/wiki/Multigrafohttps://es.wikipedia.org/wiki/Tenishttps://es.wikipedia.org/wiki/Eliminaci%25C3%25B3n_directahttps://es.wikipedia.org/wiki/Telefon%25C3%25ADa_m%25C3%25B3vilhttps://es.wikipedia.org/wiki/Red_de_celdashttps://es.wikipedia.org/wiki/Isomerohttps://es.wikipedia.org/wiki/Organigramahttps://es.wikipedia.org/wiki/Computadorhttps://es.wikipedia.org/wiki/Topolog%25C3%25ADa_de_redhttps://es.wikipedia.org/wiki/Red_socialhttps://es.wikipedia.org/wiki/Sociogramahttps://es.wikipedia.org/wiki/Circuito_el%25C3%25A9ctricohttps://es.wikipedia.org/wiki/Autopistahttps://es.wikipedia.org/wiki/Metro_(sistema_de_transporte)https://es.wikipedia.org/wiki/Mapas_conceptualeshttps://es.wikipedia.org/wiki/Biolog%C3%ADahttps://es.wikipedia.org/wiki/Red_socialhttps://es.wikipedia.org/wiki/PERThttps://es.wikipedia.org/wiki/Robert_W._Floydhttps://es.wikipedia.org/wiki/Algoritmohttps://es.wikipedia.org/wiki/Circuitohttps://es.wikipedia.org/wiki/1936https://es.wikipedia.org/wiki/D%C3%A9nes_K%C5%91nighttps://es.wikipedia.org/wiki/Mol%C3%A9culahttps://es.wikipedia.org/wiki/1884https://es.wikipedia.org/wiki/Alexander_Crum_Brownhttps://es.wikipedia.org/wiki/Edward_Franklandhttps://es.wikipedia.org/wiki/Enlaces_qu%C3%ADmicoshttps://es.wikipedia.org/wiki/%C3%81tomohttps://es.wikipedia.org/wiki/%C3%81rbol_(teor%C3%ADa_de_grafos)https://es.wikipedia.org/wiki/Hidrocarburos_saturadoshttps://es.wikipedia.org/wiki/Compuesto_qu%C3%ADmicohttps://es.wikipedia.org/wiki/Estructura_molecularhttps://es.wikipedia.org/wiki/Estructura_molecularhttps://es.wikipedia.org/wiki/Is%C3%B3meroshttps://es.wikipedia.org/wiki/Arthur_Cayleyhttps://es.wikipedia.org/wiki/1857

5/19/2018 Teora de Grafos

3/8

5.2 Grafos planos 3

4 Representacin de grafos

Existen diferentes formas de representar un grafo (sim-ple), adems de la geomtrica y muchos mtodos paraalmacenarlos en una computadora. Laestructura de da-

tosusada depende de las caractersticas del grafo y elalgoritmousado para manipularlo. Entre las estructurasms sencillas y usadas se encuentran las listas y las ma-trices, aunque frecuentemente se usa una combinacin deambas. Las listas son preferidas engrafos dispersospor-que tienen un eficiente uso de la memoria. Por otro lado,las matrices proveen acceso rpido, pero pueden consu-mir grandes cantidades de memoria.

4.1 Estructura de lista

lista de incidencia - Las aristas son representa-

das con unvectorde pares (ordenados, si el grafoes dirigido), donde cada par representa una de lasaristas.[5]

lista de adyacencia- Cada vrtice tiene una lista devrtices los cuales son adyacentes a l. Esto causa re-dundancia en un grafo no dirigido (ya que A existeen la lista de adyacencia de B y viceversa), pero lasbsquedas son ms rpidas, al costo de almacena-miento extra.

lista de grados - Tambin llamada secuencia de gra-

dososucesin grficade un grafo no-dirigido es unasecuencia de nmeros, que corresponde a los gradosde los vrtices del grafo.

4.2 Estructuras matriciales

Matriz de adyacencia- El grafo est representadopor una matriz cuadrada M de tamao n2 , donde nes el nmero de vrtices. Si hay una arista entre unvrtice x y un vrtice y, entonces el elementomx,yes 1, de lo contrario, es 0.

Matriz de incidencia- El grafo est representadopor una matriz de A (aristas) por V (vrtices), donde[vrtice, arista] contiene la informacin de la arista(1 - conectado, 0 - no conectado)

5 Problemas de teora de grafos

5.1 Ciclos y caminos hamiltonianos

Uncicloes una sucesin de aristas adyacentes, donde nose recorre dos veces la misma arista, y donde se regresa

Ejemplo de un ciclo Hamiltoniano.

al punto inicial. Unciclo hamiltonianotiene adems querecorrer todos los vrtices exactamente una vez (exceptoel 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, estoes buscar un ciclo hamiltoniano en el grafo que representael museo (los vrtices son las salas, y las aristas los corre-dores o puertas entre ellas).

Se habla tambin deCamino hamiltonianosi no se im-

pone regresar al punto de partida, como en un museocon una nica puerta de entrada. Por ejemplo, un caballopuede recorrer todas las casillas de un tablero de ajedrezsin pasar dos veces por la misma: es un camino hamilto-niano. Ejemplo de un ciclo hamiltoniano en el grafo deldodecaedro.

Hoy en da, no se conocen mtodos generales para ha-llar un ciclo hamiltoniano entiempo polinmico, siendola bsqueda por fuerza bruta de todos los posibles cami-nos u otros mtodos excesivamente costosos. Existen, sinembargo, mtodos para descartar la existencia de cicloso caminos hamiltonianos en grafos pequeos.

El problema de determinar la existencia de ciclos hamil-tonianos, entra en el conjunto de losNP-completos.

5.2 Grafos planos

Cuando un grafo o multigrafo se puede dibujar en unplano sin que dos segmentos se corten, se dice que esplano.

Un juego muy conocido es el siguiente: Se dibujan trescasas y tres pozos. Todos los vecinos de las casas tienenel derecho de utilizar los tres pozos. Como no se llevan

bien en absoluto, no quieren cruzarse jams. Es posibletrazar los nueve caminos que juntan las tres casas con lostres pozos sin que haya cruces?

https://es.wikipedia.org/wiki/NP-completohttps://es.wikipedia.org/wiki/Tiempo_polin%C3%B3micohttps://es.wikipedia.org/wiki/Dodecaedrohttps://es.wikipedia.org/wiki/Camino_hamiltonianohttps://es.wikipedia.org/wiki/Louvrehttps://es.wikipedia.org/wiki/Matriz_(matem%C3%A1tica)https://es.wikipedia.org/wiki/Matriz_de_incidenciahttps://es.wikipedia.org/wiki/Matriz_de_adyacenciahttps://es.wikipedia.org/wiki/Secuencia_de_gradoshttps://es.wikipedia.org/wiki/Lista_de_adyacenciahttps://es.wikipedia.org/wiki/Vectorhttps://es.wikipedia.org/wiki/Lista_de_incidenciahttps://es.wikipedia.org/wiki/Grafo_dispersohttps://es.wikipedia.org/wiki/Algoritmohttps://es.wikipedia.org/wiki/Estructura_de_datoshttps://es.wikipedia.org/wiki/Estructura_de_datos

5/19/2018 Teora de Grafos

4/8

4 5 PROBLEMAS DE TEORA DE GRAFOS

Un grafo es planosi se puede dibujar sin cruces de aristas. Elproblema de las tres casas y los tres pozos tiene solucin sobreeltoro, pero no en el plano.

Cualquier disposicin de las casas, los pozos y los cami-nos implica la presencia de al menos un cruce.

Sea K elgrafo completoconnvrtices, K, es elgrafobipartitodenypvrtices.

El juego anterior equivale a descubrir si elgrafo bipartitocompletoK, esplano, es decir, si se puede dibujar enun 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 K,.

Establecer qu grafos son planos no es obvio, y es un pro-blema que tiene que ver contopologa.

5.3 Coloracin de grafos

Si G=(V, E) es un grafo no dirigido, una coloracin pro-pia de G, ocurre cuando coloreamos los vrtices de G demodoquesi{a,b}esunaaristaenGentoncesaybtienendiferentes colores. (Por lo tanto, los vrtices adyacentestienen colores diferentes). El nmero mnimo de coloresnecesarios para una coloracin propia de G es el nmerocromtico de G y se escribe como C (G). Sea G un grafono dirigido sea el nmero de colores disponibles parala coloracin propia de los vrtices de G. Nuestro obje-tivo es encontrar una funcin polinomial P (G,), en lavariable , llamada polinomio cromtico de G, que nosindique el nmero de coloraciones propias diferentes delos vrtices de G, usando un mximo de colores.

Descomposicin de polinomios cromticos. Si G=(V, E)es un grafo conexo y e pertenece a , entonces: P (G,)=P(G+e,)+P (G/e,), donde G/e es el grafo se obtene porcontraccin de aristas.

Para cualquier grafo G, el trmino constante en P (G,)es 0

Sea G=(V, E) con |E|>0 entonces, la suma de los coefi-

cientes de P (G,) es 0.

Sea G=(V, E), cona,bpertenecientes al conjunto de vr-ticesVpero {a, b}=e, no perteneciente a al conjunto dearistas E. Escribimos G+e para el grafo que se obtiene deG al aadir la arista e={a, b}. Al identificar los vrtices a

y b en G, obtenemos el subgrafo G++e de G.0000

5.3.1 Teorema de los cuatro colores

Mapa coloreado con 4-colores.

Grafo dualasociado al mapa con una4-vrtice colora-cin.

Otro problema famoso relativo a los grafos: Cuntos co-lores son necesarios para dibujar un mapa poltico, con lacondicin obvia que dos pases adyacentes no puedan te-ner el mismo color? Se supone que los pases son de unsolo pedazo, y que el mundo es esfrico o plano. En unmundo en forma de toroide; el teorema siguiente no esvlido:

Cuatro colores son siempre suficientes para colorear unmapa.

El mapa siguiente muestra que tres colores no bastan: Sise empieza por el pas centralay se esfuerza uno en uti-lizar el menor nmero de colores, entonces en la coronaalrededor deaalternan dos colores. Llegando al pashsetiene que introducir un cuarto color. Lo mismo sucede enisi se emplea el mismo mtodo.

La forma precisa de cada pas no importa; lo nico rele-

vante es saber qu pas toca a qu otro. Estos datos estnincluidos en el grafo donde los vrtices son los pases ylas aristas conectan los que justamente son adyacentes.

https://es.wikipedia.org/wiki/Coloraci%C3%B3n_de_grafoshttps://es.wikipedia.org/wiki/Coloraci%C3%B3n_de_grafoshttps://es.wikipedia.org/wiki/Grafo_dualhttps://es.wikipedia.org/wiki/Contracci%C3%B3n_de_aristashttps://es.wikipedia.org/wiki/Topolog%C3%ADahttps://es.wikipedia.org/wiki/Grafo_bipartito_completohttps://es.wikipedia.org/wiki/Grafo_bipartito_completohttps://es.wikipedia.org/wiki/Grafo_bipartitohttps://es.wikipedia.org/wiki/Grafo_bipartitohttps://es.wikipedia.org/wiki/Grafo_completohttps://es.wikipedia.org/wiki/Toro_(matem%C3%A1ticas)

5/19/2018 Teora de Grafos

5/8

6.1 Homeomorfismo de grafos 5

Entonces la cuestin equivale a atribuir a cada vrtice uncolor distinto del de sus vecinos.

Hemos visto que tres colores no son suficientes, y demos-trar que con cinco siempre se llega, es bastante fcil. Peroel teorema de los cuatro colores no es nada obvio. Prueba

de ello es que se han tenido que emplear ordenadores pa-ra acabar la demostracin (se ha hecho un programa quepermiti verificar una multitud de casos, lo que ahorrmuchsimotiempoa los matemticos). Fue la primera vezque la comunidad matemtica acept una demostracinasistida por ordenador, lo que cre en su da una ciertapolmica dentro de la comunidad matemtica.

6 Caracterizacin de grafos

6.0.2 Grafos simples

Un grafo essimplesi a lo ms existe una arista uniendodos vrtices cualesquiera. Esto es equivalente a decir queuna arista cualquiera es la nica que une dos vrtices es-pecficos.

Un grafo que no es simple se denominamultigrafo.

6.0.3 Grafos conexos

Un grafo es conexo si cada par de vrtices est conectadopor un camino; es decir, si para cualquier par de vrtices(a, b), existe al menos un camino posible desdeahaciab.

Un grafo es doblemente conexo si cada par de vrticesest conectado por al menos dos caminos disjuntos; esdecir, es conexo y no existe un vrtice tal que al sacarloel grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un al-goritmoBsqueda en anchura(BFS) oBsqueda en pro-fundidad(DFS).

En trminos matemticos la propiedad de un grafo de

ser (fuertemente) conexo permite establecer con baseen l una relacin de equivalencia para sus vrtices,la cual lleva a una particin de stos en compo-nentes (fuertemente) conexas, es decir, porcionesdel grafo, que son (fuertemente) conexas cuando seconsideran como grafos aislados. Esta propiedad es im-portante para muchas demostraciones en teora de grafos.

6.0.4 Grafos completos

Un grafo escompletosi existen aristas uniendotodoslospares posibles de vrtices. Es decir, todo par de vrtices(a, b) debe tener una aristaeque los une.

El conjunto de los grafos completos es denominadousualmente K, siendo Knel grafo completo de nvr-tices.

UnKn, es decir, grafo completoden vrtices tiene exac-tamente n(n1)2 aristas.

La representacin grfica de los Kncomo los vrtices deun polgono regular da cuenta de su peculiar estructura.

6.0.5 Grafos bipartitos

Un grafo G es bipartito si puede expresarse como G =

{V1 V2, A}(es decir, sus vrtices son la unin de dosgrupos de vrtices), bajo las siguientes condiciones:

V1y V2son disjuntos y no vacos.

Cada arista de A une un vrtice de V1con uno deV2.

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 uneo relaciona dos conjuntos de elementos diferentes, comoaquellos resultantes de los ejercicios y puzzles en los quedebeunirseunelementodelacolumnaAconunelementode la columna B.

6.1 Homeomorfismo de grafos

Dos grafosG1y G2son homeomorfos si ambos puedenobtenerse a partir del mismo grafo con una sucesin desubdivisiones elementalesde aristas.

6.2 rboles

Un grafo que no tiene ciclos y que conecta a todos lospuntos, se llama unrbol. En un grafo connvrtices, losrboles tienen exactamenten - 1aristas, y haynn-2 rbo-les posibles. Su importancia radica en que los rboles songrafos que conectan todos los vrtices utilizando el me-nor nmero posible de aristas. Un importante campo deaplicacin de su estudio se encuentra en elanlisis filoge-ntico, el de la filiacin de entidades que derivan unas deotras en un proceso evolutivo, que se aplica sobre todo a

la averiguacin del parentesco entre especies; aunque seha usado tambin, por ejemplo, en el estudio del paren-tesco entre lenguas.

https://es.wikipedia.org/wiki/An%C3%A1lisis_filogen%C3%A9ticohttps://es.wikipedia.org/wiki/An%C3%A1lisis_filogen%C3%A9ticohttps://es.wikipedia.org/wiki/Subdivisiones_elementaleshttps://es.wikipedia.org/wiki/Relaci%C3%B3n_de_equivalenciahttps://es.wikipedia.org/wiki/B%C3%BAsqueda_en_profundidadhttps://es.wikipedia.org/wiki/B%C3%BAsqueda_en_profundidadhttps://es.wikipedia.org/wiki/B%C3%BAsqueda_en_anchurahttps://es.wikipedia.org/wiki/Multigrafo

5/19/2018 Teora de Grafos

6/8

6 8 INVESTIGADORES RELEVANTES EN TEORA DE GRAFOS

Ejemplo de rbol.

6.3 Grafos ponderados o etiquetados

En muchos casos, es preciso atribuir a cada arista un n-mero 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 visi-tarnciudades conectadas entre s por carreteras; su inte-rs previsible ser minimizar la distancia recorrida (o eltiempo, si se pueden prever atascos). El grafo correspon-

diente tendr como vrtices las ciudades, como aristas lascarreteras y la valuacin ser la distancia entre ellas.Y, de momento, no se conocen mtodos generales parahallar un ciclo de valuacin mnima, pero s para los ca-minos desdeahastab, sin ms condicin.

6.4 Dimetro

En la figura se nota que K4es plano (desviando la arista abalexterior 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 menornmero de aristas de un recorrido entre ellos. Eldime-tro, en una figura como en un grafo, es la mayor distanciade entre todos los pares de puntos de la misma.

El dimetro de los K es 1, y el de los K, es 2. Un di-metro infinito puede significar que el grafo tiene una infi-nidad de vrtices o simplemente que no esconexo. Tam-

bin se puede considerar eldimetro promedio, comoel promedio de las distancias entre dos vrtices.

El mundo de Internet ha puesto de moda esa idea del di-metro: Si descartamos los sitios que no tienen enlaces, yescogemos dos pginaswebalazar: En cuntosclicsse

puede pasar de la primera a la segunda? El resultado esel dimetro de la Red, vista como un grafo cuyos vrticesson los sitios, y cuyas aristas son lgicamente los enlaces.

En el mundo real hay una analoga: tomando al azar dosseres humanos del mundo, En cuntos saltos se puedepasar de uno a otro, con la condicin de slo saltar deuna persona a otra cuando ellas se conocen personalmen-te? Con esta definicin, se estima que el dimetro de lahumanidad es de... ocho solamente!

Este concepto refleja mejor la complejidad de una red queel nmero de sus elementos.

7 Algoritmos importantes

Algoritmo de bsqueda en anchura (BFS)

Algoritmo de bsqueda en profundidad (DFS)

Algoritmo de bsqueda A*

Algoritmo del vecino ms cercano

Ordenacin topolgica de un grafo

Algoritmo de clculo de los componentes fuerte-mente conexos de un grafo

Algoritmo de Dijkstra

Algoritmo de Bellman-Ford

Algoritmo de Prim

Algoritmo de Ford-Fulkerson

Algoritmo de Kruskal

Algoritmo de Floyd-Warshall

8 Investigadores relevantes en Teo-ra de grafos

Alon, Noga

Berge, Claude

Bollobs, Bla

Brightwell, Graham

Chung, Fan

Dirac, Gabriel Andrew

Dijkstra, Edsger

https://es.wikipedia.org/wiki/Edsger_Dijkstrahttps://es.wikipedia.org/wiki/Gabriel_Andrew_Dirachttps://es.wikipedia.org/wiki/Fan_Chunghttps://es.wikipedia.org/wiki/Graham_Brightwellhttps://es.wikipedia.org/wiki/B%C3%A9la_Bollob%C3%A1shttps://es.wikipedia.org/wiki/Claude_Bergehttps://es.wikipedia.org/wiki/Noga_Alonhttps://es.wikipedia.org/wiki/Algoritmo_de_Floyd-Warshallhttps://es.wikipedia.org/wiki/Algoritmo_de_Kruskalhttps://es.wikipedia.org/wiki/Algoritmo_de_Ford-Fulkersonhttps://es.wikipedia.org/wiki/Algoritmo_de_Primhttps://es.wikipedia.org/wiki/Algoritmo_de_Bellman-Fordhttps://es.wikipedia.org/wiki/Algoritmo_de_Dijkstrahttps://es.wikipedia.org/wiki/Algoritmo_de_c%C3%A1lculo_de_los_componentes_fuertemente_conexos_de_un_grafohttps://es.wikipedia.org/wiki/Algoritmo_de_c%C3%A1lculo_de_los_componentes_fuertemente_conexos_de_un_grafohttps://es.wikipedia.org/wiki/Ordenaci%C3%B3n_topol%C3%B3gicahttps://es.wikipedia.org/wiki/Algoritmo_del_vecino_m%C3%A1s_cercanohttps://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_A*https://es.wikipedia.org/wiki/B%C3%BAsqueda_en_profundidadhttps://es.wikipedia.org/wiki/B%C3%BAsqueda_en_anchurahttps://es.wikipedia.org/wiki/Azar

5/19/2018 Teora de Grafos

7/8

7

Erds, Paul

Euler, Leonhard

Faudree, Ralph

Golumbic, Martin

Graham, Ronald

Harary, Frank

Heawood, Percy John

Kaufmann, Walter Arnold

Knig, Dnes

Kuratowski, Kazimierz

Lovsz, Lszl

Neetil, Jaroslav

Rnyi, Alfrd

Ringel, Gerhard

Robertson, Neil

Seymour, Paul

Szemerdi, Endre

Thomas, Robin

Thomassen, Carsten

Turn, Pl Tutte, W. T.

Whitney, Hassler

9 Vase tambin

Grafo

Anexo:Galera de grafos

10 Referencias

[1] Euler, L. (1736). Solutio problematis ad geome-triam situs pertinentis. Commentarii Academiae Scien-tiarum Imperialis Petropolitanae8. 128-140.http://math.dartmouth.edu/~{}euler/docs/originals/E053.pdf.

[2] http://booklens.com/l-r-foulds/graph-theory-applicationspag 7

[3] Tutte, W.T.(2001), Graph Theory, Cambridge Univer-sity Press, p. 30,ISBN 978-0-521-79489-3,http://books.google.com/books?id=uTGhooU37h4C&pg=PA30.

[4] Gorbtov:Fundamentos de la matemtica discreta

[5] Ejemplo de una lista de incidencia

11 Enlaces externos

Wikimedia Commonsalberga contenido multi-media sobreTeora de grafos.Commons

Sobre los grafos VPT y los grafos EPT. Mazzoleni,Mara Pa. 30 de mayo de 2014.

El contenido de este artculo incorpora material deunaentrada de la Enciclopedia Libre Universal,publicada en espaol bajo la licencia CreativeCommons Compartir-Igual 3.0.

http://creativecommons.org/licenses/by-sa/3.0/deed.eshttp://creativecommons.org/licenses/by-sa/3.0/deed.eshttp://enciclopedia.us.es/index.php/Teor%25C3%25ADa_de_grafoshttp://sedici.unlp.edu.ar/handle/10915/36487https://commons.wikimedia.org/wiki/Category:Graph%2520theoryhttps://commons.wikimedia.org/wiki/Category:Graph%2520theoryhttps://es.wikipedia.org/wiki/Wikimedia_Commonshttps://upload.wikimedia.org/wikipedia/commons/thumb/1/18/Incidence_list_2.svg/500px-Incidence_list_2.svg.pnghttp://books.google.com/books?id=uTGhooU37h4C&pg=PA30http://books.google.com/books?id=uTGhooU37h4C&pg=PA30https://es.wikipedia.org/wiki/Especial:FuentesDeLibros/978-0-521-79489-3https://es.wikipedia.org/wiki/ISBNhttp://books.google.com/books?id=uTGhooU37h4C&pg=PA30https://es.wikipedia.org/wiki/W._T._Tuttehttp://booklens.com/l-r-foulds/graph-theory-applicationshttp://booklens.com/l-r-foulds/graph-theory-applicationshttp://math.dartmouth.edu/~euler/docs/originals/E053.pdfhttp://math.dartmouth.edu/~euler/docs/originals/E053.pdfhttp://math.dartmouth.edu/~euler/docs/originals/E053.pdfhttp://math.dartmouth.edu/~euler/docs/originals/E053.pdfhttps://es.wikipedia.org/wiki/Anexo:Galer%C3%ADa_de_grafoshttps://es.wikipedia.org/wiki/Grafohttps://es.wikipedia.org/wiki/Hassler_Whitneyhttps://es.wikipedia.org/wiki/W._T._Tuttehttps://es.wikipedia.org/wiki/P%C3%A1l_Tur%C3%A1nhttps://es.wikipedia.org/wiki/Carsten_Thomassenhttps://es.wikipedia.org/wiki/Robin_Thomas_(mathematician)https://es.wikipedia.org/wiki/Endre_Szemer%C3%A9dihttps://es.wikipedia.org/wiki/Paul_Seymour_(mathematician)https://es.wikipedia.org/wiki/Neil_Robertson_(mathematician)https://es.wikipedia.org/wiki/Gerhard_Ringelhttps://es.wikipedia.org/wiki/Alfr%C3%A9d_R%C3%A9nyihttps://es.wikipedia.org/wiki/Jaroslav_Ne%C5%A1et%C5%99ilhttps://es.wikipedia.org/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1szhttps://es.wikipedia.org/wiki/Kazimierz_Kuratowskihttps://es.wikipedia.org/wiki/D%C3%A9nes_K%C5%91nighttps://es.wikipedia.org/wiki/Htp://en.wikipedia.org/wiki/Walter_Kaufmann_(philosopher)https://es.wikipedia.org/wiki/Percy_John_Heawoodhttps://es.wikipedia.org/wiki/Frank_Hararyhttps://es.wikipedia.org/wiki/Ronald_Grahamhttps://es.wikipedia.org/wiki/Martin_Charles_Golumbichttps://es.wikipedia.org/wiki/Ralph_Faudreehttps://es.wikipedia.org/wiki/Leonhard_Eulerhttps://es.wikipedia.org/wiki/Paul_Erd%C5%91s

5/19/2018 Teora de Grafos

8/8

8 12 TEXT AND IMAGE SOURCES, CONTRIBUTORS, AND LICENSES

12 Text and image sources, contributors, and licenses

12.1 Text Teora de grafos Fuente:http://es.wikipedia.org/wiki/Teora_de_grafos?oldid=77683621Colaboradores:Pino, Rumpelstiltskin, Rosa-

rino, Ascnder, Julian Colina, Tano4595, PeiT, Taxman, Rondador, La Mantis, AlfonsoERomero, Emijrp, Rmolina, RobotQuistnix, Alhen,BOT-Superzerocool, Boku wa kage, YurikBot, Equi, Otermin, Tomatejc, Mencey, Nihilo, Tessier, Ilan.ag1, BOTpolicia, Adama, Ludovi-ko, Rdaneel, Hawking, CEM-bot, Ferminmx, JMCC1, Alexav8, Baiji, Roberpl, Mcetina, Ingenioso Hidalgo, Thijs!bot, Ingridchan, PabloOlmos, Tortillovsky, Davidrodriguez, IrwinSantos, Seba.29.8, Zifra, Sapiensjpa, Botones, Gusgus, Mpeinadopa, JAnDbot, Nando.sm, In-mortra, Aalvarez12, Gullo, Humberto, Pabloallo, Esteban fcr, Chabbot, Plux, Rovnet, Mundokeko, VolkovBot, XinuXano, Elmermosher,Matdrodes, AlleborgoBot, Muro Bot, Feministo, Numbo3, Gerakibot, SieBot, Loveless, Drinibot, Macarse, Raul.lara, Xiscobernal, Pi-pepBot, Schwallex, Gato ocioso, Farisori, Eduardosalg, Neodop, Botelln, Leonpolanco, LordT, Juan Mayordomo, Darkicebot, Aikasse,BodhisattvaBot, Raulshc, AVBOT, LucienBOT, MastiBot, Diegusjaimes, A.garridob, Luckas-bot, Ricardo Castelo, El Quinche, Vic Fede,Habilbakhat, Marioxcc, Diogeneselcinico42, SuperBraulio13, Xqbot, Jkbw, Angenio2, Botarel, Andrestand, Paladium, Linux65, RedBot,Wsu-dm-jb, Galileicanarias, Dinamik-bot, TjBot, Ripchip Bot, Dark Bane, Jorge c2010, Foundling, EleferenBot, Axvolution, EmausBot,Savh, Khaos258, Grillitus, ChuispastonBot, Alejozsz, AvocatoBot, Invadibot, SoleFabrizio, Leitoxx, Addbot, DaveGomez, JacobRodri-gues, Gonzalo.villarreal y Annimos: 165

12.2 Images Archivo:6n-graph2.svgFuente:http://upload.wikimedia.org/wikipedia/commons/2/28/6n-graph2.svgLicencia:Public domainColabo-

radores:?

Artista original:?

Archivo:7_bridges.svgFuente:http://upload.wikimedia.org/wikipedia/commons/9/91/7_bridges.svgLicencia:CC-BY-SA-3.0Colabo-radores:?Artista original:?

Archivo:Commons-emblem-question_book_orange.svg Fuente: http://upload.wikimedia.org/wikipedia/commons/1/1f/Commons-emblem-question_book_orange.svg Licencia: CC-BY-SA-3.0 Colaboradores: + Artista original:GNOME icon artists,Jorge 2701

Archivo:Commons-logo.svg Fuente:http://upload.wikimedia.org/wikipedia/commons/4/4a/Commons-logo.svgLicencia:Public domainColaboradores:

Thisversioncreatedby Pumbaa, using a proper partial circleand SVGgeometry features. (Formerversions usedto be slightlywarped.)Artista original:SVG version was created byUser:Gruntand cleaned up by3247, based on the earlier PNG version, created byReidab.

Archivo:Dart_graph.svgFuente:http://upload.wikimedia.org/wikipedia/commons/9/96/Dart_graph.svgLicencia:CC-BY-SA-3.0-2.5-2.0-1.0Colaboradores:Trabajo propioArtista original:Koko90

Archivo:Dodecahedral_graph.neato.svg Fuente:http://upload.wikimedia.org/wikipedia/commons/0/05/Dodecahedral_graph.neato.svgLicencia:CC-BY-SA-3.0Colaboradores:Trabajo propioArtista original:Koko90

Archivo:Fish_graph.svg Fuente:http://upload.wikimedia.org/wikipedia/commons/e/ee/Fish_graph.svg Licencia:CC-BY-SA-3.0-2.5-2.0-1.0Colaboradores:Trabajo propioArtista original:Koko90

Archivo:GrafoConexo.jpg Fuente:http://upload.wikimedia.org/wikipedia/commons/7/7c/GrafoConexo.jpg Licencia:Public domainColaboradores:Trabajo propioArtista original:Fran VH

Archivo:Grafo_ejemplo_3_rbol.png Fuente: http://upload.wikimedia.org/wikipedia/commons/c/cc/Grafo_ejemplo_3_%C3%A1rbol.pngLicencia:CC-BY-SA-3.0Colaboradores:Originally fromes.wikipedia; description page is/washere.Artista original:Originaluploader wasRomero Schmidtkeates.wikipedia

Archivo:Grafo_ejemplo_5_conecsi.pngFuente:http://upload.wikimedia.org/wikipedia/commons/5/50/Grafo_ejemplo_5_conecsi.pngLicencia:CC-BY-SA-3.0Colaboradores:Originally fromes.wikipedia; description page is/washere.Artista original:Original uploader wasRomero Schmidtkeates.wikipedia

Archivo:Grafo_ejemplo_5_pases.png Fuente: http://upload.wikimedia.org/wikipedia/commons/5/5e/Grafo_ejemplo_5_pa%C3%ADses.pngLicencia:CC-BY-SA-3.0Colaboradores:Originally fromes.wikipedia; description page is/washere.Artista original:Originaluploader wasRomero Schmidtkeates.wikipedia

Archivo:Grafo_ejemplo_6.png Fuente:http://upload.wikimedia.org/wikipedia/commons/0/04/Grafo_ejemplo_6.png Licencia: CC-BY-SA-3.0Colaboradores:Originally fromes.wikipedia; description page is/washere. Artista original:Original uploader wasRomeroSchmidtkeates.wikipedia

Archivo:Grafo_ejemplo_7.pngFuente:http://upload.wikimedia.org/wikipedia/commons/f/f7/Grafo_ejemplo_7.pngLicencia:CC-BY-SA-3.0 Colaboradores:Originally from es.wikipedia; description pageis/was here. Artista original:Originaluploader was RomeroSchmidtkeates.wikipedia

Archivo:Hamiltonian_path.svg Fuente:http://upload.wikimedia.org/wikipedia/commons/6/60/Hamiltonian_path.svg Licencia:CC-BY-SA-3.0Colaboradores:Trabajo propioArtista original:Christoph Sommer

12.3 Content license Creative Commons Attribution-Share Alike 3.0

http://creativecommons.org/licenses/by-sa/3.0/http://upload.wikimedia.org/wikipedia/commons/6/60/Hamiltonian_path.svghttp://es.wikipedia.org/http://localhost/var/www/apps/conversion/tmp/scratch_7//es.wikipedia.org/wiki/User:Romero_Schmidtkehttp://es.wikipedia.org/w/index.php?title=Image%253AGrafo_ejemplo_7.pnghttp://es.wikipedia.org/http://upload.wikimedia.org/wikipedia/commons/f/f7/Grafo_ejemplo_7.pnghttp://es.wikipedia.org/http://localhost/var/www/apps/conversion/tmp/scratch_7//es.wikipedia.org/wiki/User:Romero_Schmidtkehttp://localhost/var/www/apps/conversion/tmp/scratch_7//es.wikipedia.org/wiki/User:Romero_Schmidtkehttp://es.wikipedia.org/w/index.php?title=Image%253AGrafo_ejemplo_6.pnghttp://es.wikipedia.org/http://upload.wikimedia.org/wikipedia/commons/0/04/Grafo_ejemplo_6.pnghttp://es.wikipedia.org/http://localhost/var/www/apps/conversion/tmp/scratch_7//es.wikipedia.org/wiki/User:Romero_Schmidtkehttp://es.wikipedia.org/w/index.php?title=Image%253AGrafo_ejemplo_5_pa%25C3%25ADses.pnghttp://es.wikipedia.org/http://upload.wikimedia.org/wikipedia/commons/5/5e/Grafo_ejemplo_5_pa%25C3%25ADses.pnghttp://upload.wikimedia.org/wikipedia/commons/5/5e/Grafo_ejemplo_5_pa%25C3%25ADses.pnghttp://es.wikipedia.org/http://localhost/var/www/apps/conversion/tmp/scratch_7//es.wikipedia.org/wiki/User:Romero_Schmidtkehttp://es.wikipedia.org/w/index.php?title=Image%253AGrafo_ejemplo_5_conecsi.pnghttp://es.wikipedia.org/http://upload.wikimedia.org/wikipedia/commons/5/50/Grafo_ejemplo_5_conecsi.pnghttp://es.wikipedia.org/http://localhost/var/www/apps/conversion/tmp/scratch_7//es.wikipedia.org/wiki/User:Romero_Schmidtkehttp://es.wikipedia.org/w/index.php?title=Image%253AGrafo_ejemplo_3_%25C3%25A1rbol.pnghttp://es.wikipedia.org/http://upload.wikimedia.org/wikipedia/commons/c/cc/Grafo_ejemplo_3_%25C3%25A1rbol.pnghttp://upload.wikimedia.org/wikipedia/commons/c/cc/Grafo_ejemplo_3_%25C3%25A1rbol.pnghttp://upload.wikimedia.org/wikipedia/commons/7/7c/GrafoConexo.jpghttp://localhost/var/www/apps/conversion/tmp/scratch_7//commons.wikimedia.org/wiki/User:Koko90http://upload.wikimedia.org/wikipedia/commons/e/ee/Fish_graph.svghttp://localhost/var/www/apps/conversion/tmp/scratch_7//commons.wikimedia.org/wiki/User:Koko90http://upload.wikimedia.org/wikipedia/commons/0/05/Dodecahedral_graph.neato.svghttp://localhost/var/www/apps/conversion/tmp/scratch_7//commons.wikimedia.org/wiki/User:Koko90http://upload.wikimedia.org/wikipedia/commons/9/96/Dart_graph.svghttp://localhost/var/www/apps/conversion/tmp/scratch_7//meta.wikimedia.org/wiki/User:Reidabhttp://localhost/var/www/apps/conversion/tmp/scratch_7//commons.wikimedia.org/wiki/User:3247http://localhost/var/www/apps/conversion/tmp/scratch_7//commons.wikimedia.org/wiki/User:Grunthttp://upload.wikimedia.org/wikipedia/commons/4/4a/Commons-logo.svghttp://localhost/var/www/apps/conversion/tmp/scratch_7//commons.wikimedia.org/wiki/User:Jorge_2701http://svn.gnome.org/viewvc/gnome-icon-theme/trunk/AUTHORS?view=markuphttp://upload.wikimedia.org/wikipedia/commons/1/1f/Commons-emblem-question_book_orange.svghttp://upload.wikimedia.org/wikipedia/commons/1/1f/Commons-emblem-question_book_orange.svghttp://upload.wikimedia.org/wikipedia/commons/9/91/7_bridges.svghttp://upload.wikimedia.org/wikipedia/commons/2/28/6n-graph2.svghttp://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos?oldid=77683621