Teora de grafos

Los grafos son el objeto de estudio de esta rama de lasmatemticas. Arriba el grafo pez, en medio el grafo arcoy abajo el grafo dodecaedro.

La teora de grafos (tambin llamada teora de las gr-cas) es un campo de estudio de las matemticas y lasciencias de la computacin, que estudia las propiedadesde los grafos (tambin llamadas grcas, que no se debeconfundir con las grcas que tienen una acepcin muyamplia) estructuras que constan de dos partes, el conjuntode vrtices, nodos o puntos; y el conjunto de aristas, l-neas o lados (edges en ingls) que pueden ser orientadoso no.La teora de grafos es una rama de las matemticas dis-cretas y de las matemticas aplicadas, y es un trata-do que usa diferentes conceptos de diversas reas comocombinatoria, lgebra, probabilidad, geometra de pol-gonos, aritmtica y topologa.Actualmente ha tenido mayor preponderancia en el cam-po de la informtica, las ciencias de la computacin ytelecomunicaciones.

1 Historia

Los 7 puentes del ro Pregel en Knigsberg.

El origen de la teora de grafos se remonta al sigloXVIII con el problema de los puentes de Knigsberg, elcual consista en encontrar un camino que recorriera lossiete puentes del ro Pregel (544212N 203056E /54.70333, 20.51556) en la ciudad de Knigsberg, actual-mente Kaliningrado, de modo que se recorrieran todoslos puentes pasando una sola vez por cada uno de ellos.El trabajo de Leonhard Euler sobre el problema tituladoSolutio problematis ad geometriam situs pertinentis[1] (Lasolucin de un problema relativo a la geometra de la po-sicin) en 1736, 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 la topologa.Luego, en 1847, Gustav Kirchho 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 como leyes de Kirchho,considerado la primera aplicacin de la teora de grafos aun problema de ingeniera.En 1852 Francis Guthrie plante el problema de los cua-tro colores el cual arma 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 por Kenneth Appel y Wolfgang Haken en1976, puede ser considerado como el nacimiento de lateora de grafos. Al tratar de resolverlo, los matemticosdenieron trminos y conceptos tericos fundamentales

1

2 3 TIPOS DE GRAFOS

de los grafos.En 1857, Arthur Cayley estudi y resolvi el problema deenumeracin de los ismeros, compuestos qumicos conidntica composicin (frmula) pero diferente estructuramolecular. Para ello represent cada compuesto, en estecaso hidrocarburos saturados CH, mediante un graforbol donde los vrtices representan tomos y las aristasla existencia de enlaces qumicos.El trmino grafo, proviene de la expresin Hgraphicnotation usada por primera vez por Edward Frankland[2]y posteriormente adoptada por Alexander Crum Brownen 1884, y haca referencia a la representacin grca delos enlaces entre los tomos de una molcula.El primer libro sobre teora de grafos fue escrito porDnes Knig y publicado en 1936.[3]

2 AplicacionesGracias a la teora de grafos se pueden resolver diversosproblemas como por ejemplo la sntesis de circuitos se-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 diversos algoritmos como puede serel algoritmo de Floyd.Para la administracin de proyectos, utilizamos tcni-cas como tcnica de revisin y evaluacin de programas(PERT) en las que se modelan los mismos utilizando gra-fos y optimizando los tiempos para concretar los mismos.La teora de grafos tambin ha servido de inspiracin paralas ciencias sociales, en especial para desarrollar un con-cepto no metafrico de red social que sustituye los nodospor los actores sociales y verica la posicin, centralidade importancia de cada actor dentro de la red. Esta medi-da permite cuanticar y abstraer relaciones complejas, demanera que la estructura social puede representarse gr-camente. Por ejemplo, una red social puede representar laestructura de poder dentro de una sociedad al identicarlos 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 problemas de gentica y proble-mas de automatizacin de la proyeccin (SAPR). Apoyomatemtico 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 cientcospueden entender cmo esto puede cambiar o afectar a lasespecies en su hbitat.

Mapas conceptuales

Plano de estaciones del metro.

Plano de autopistas.

Circuito elctrico

Sociograma de una red social

Topologa de red de computadores

Organigramas

Isomeros

Arquitectura de redes de telefona mvil

Draws de eliminacin directa (ej: tenis)

3 Tipos de grafos Grafo simple. o simplemente grafo es aquel que

acepta una sola arista uniendo dos vrtices cuales-quiera. Esto es equivalente a decir que una aristacualquiera es la nica que une dos vrtices espec-cos. Es la denicin estndar de un grafo.

Multigrafo. o pseudografo son grafos que aceptanms de una arista entre dos vrtices. Estas aristas sellamanmltiples o lazos (loops en ingls). Los grafossimples son una subclase de esta categora de grafos.Tambin se les llama grafos no-dirigido.

Grafo dirigido. Son grafos en los cuales se ha aa-dido una orientacin a las aristas, representada gr-camente por una echa

Grafo etiquetado. Grafos en los cuales se ha aadi-do un peso a las aristas (nmero entero generalmen-te) o un etiquetado a los vrtices.

Grafo aleatorio. Grafo cuyas aristas estn asocia-das a una probabilidad.

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

Grafo innito. Grafos con conjunto de vrtices yaristas de cardinal innito.

5.2 Grafos planos 3

4 Representacin de grafosExisten diferentes formas de representar un grafo (sim-ple), adems de la geomtrica y muchos mtodos paraalmacenarlos en una computadora. La estructura de da-tos usada depende de las caractersticas del grafo y elalgoritmo usado 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 en grafos dispersos por-que tienen un eciente 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 un vector de 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-dos o sucesin grca de 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 representado

por 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 elemento mx;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 hamiltonianosUn ciclo es 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. Un ciclo hamiltoniano tiene 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 del Louvre),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 de Camino hamiltoniano si 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 en tiempo 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 los NP-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 llevanbien en absoluto, no quieren cruzarse jams. Es posibletrazar los nueve caminos que juntan las tres casas con lostres pozos sin que haya cruces?

4 5 PROBLEMAS DE TEORA DE GRAFOS

Un grafo es plano si se puede dibujar sin cruces de aristas. Elproblema de las tres casas y los tres pozos tiene solucin sobreel toro, 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 el grafo completo con n vrtices, K, es el grafobipartito de n y p vrtices.El juego anterior equivale a descubrir si el grafo bipartitocompleto K, es plano, es decir, si se puede dibujar enun plano sin que haya cruces, siendo la respuesta que no.En general, puede determinarse que un grafo no es plano,si en su diseo puede encontrase una estructura anloga(conocida como menor) a K5 o a K,.Establecer qu grafos son planos no es obvio, y es un pro-blema que tiene que ver con topologa.

5.3 Coloracin de grafosSi G=(V, E) es un grafo no dirigido, una coloracin pro-pia de G, ocurre cuando coloreamos los vrtices de G demodo que si {a, b} es una arista en G entonces a y b tienendiferentes 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 0Sea G=(V, E) con |E|>0 entonces, la suma de los coe-

cientes de P (G,) es 0.Sea G=(V, E), con a, b pertenecientes al conjunto de vr-tices V pero {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 identicar los vrtices ay 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 dual asociado al mapa con una 4-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 sucientes para colorear unmapa.El mapa siguiente muestra que tres colores no bastan: Sise empieza por el pas central a y se esfuerza uno en uti-lizar el menor nmero de colores, entonces en la coronaalrededor de a alternan dos colores. Llegando al pas h setiene que introducir un cuarto color. Lo mismo sucede eni si 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.

6.1 Homeomorsmo 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 sucientes, y demos-trar que con cinco siempre se llega, es bastante fcil. Peroel teorema de los cuatro colores no es nada obvio. Pruebade ello es que se han tenido que emplear ordenadores pa-ra acabar la demostracin (se ha hecho un programa quepermiti vericar una multitud de casos, lo que ahorrmuchsimo tiempo a losmatemticos). 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 grafos6.0.2 Grafos simples

Un grafo es simple si 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-peccos.Un grafo que no es simple se denomina multigrafo.

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 desde a hacia b.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-goritmo Bsqueda en anchura (BFS) o Bsqueda en pro-fundidad (DFS).En trminos matemticos la propiedad de un grafo deser (fuertemente) conexo permite establecer con base enl una relacin de equivalencia para sus vrtices, la cuallleva a una particin de stos en componentes (fuerte-mente) conexas, es decir, porciones del grafo, que son(fuertemente) conexas cuando se consideran como gra-fos aislados. Esta propiedad es importante para muchasdemostraciones en teora de grafos.

6.0.4 Grafos completos

Un grafo es completo si existen aristas uniendo todos lospares posibles de vrtices. Es decir, todo par de vrtices(a, b) debe tener una arista e que los une.El conjunto de los grafos completos es denominadousualmente K , siendo Kn el grafo completo de n vr-tices.

1

432

5

1

432

5

Grafo conexo y no conexo

UnKn , es decir, grafo completo de n vrtices tiene exac-tamente n(n1)2 aristas.La representacin grca de los Kn como 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 =fV1 [ V2; Ag (es decir, sus vrtices son la unin de dosgrupos de vrtices), bajo las siguientes condiciones:

V1 y V2 son disjuntos y no vacos. Cada arista de A une un vrtice de V1 con uno de

V2. No existen aristas uniendo dos elementos de V1;

anlogamente para V2.

Bajo estas condiciones, el grafo se considera bipartito, ypuede describirse informalmente como el grafo que uneo relaciona dos conjuntos de elementos diferentes, comoaquellos resultantes de los ejercicios y puzzles en los quedebe unirse un elemento de la columnaA con un elementode la columna B.

6.1 Homeomorsmo de grafosDos grafos G1 y G2 son homeomorfos si ambos puedenobtenerse a partir del mismo grafo con una sucesin desubdivisiones elementales de aristas.

6.2 rbolesUn grafo que no tiene ciclos y que conecta a todos lospuntos, se llama un rbol. En un grafo con n vrtices, losrboles tienen exactamente n - 1 aristas, y hay nn-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 el anlisis loge-ntico, el de la liacin de entidades que derivan unas deotras en un proceso evolutivo, que se aplica sobre todo ala averiguacin del parentesco entre especies; aunque se

6 8 INVESTIGADORES RELEVANTES EN TEORA DE GRAFOS

Ejemplo de rbol.

ha usado tambin, por ejemplo, en el estudio del paren-tesco entre lenguas.

6.3 Grafos ponderados o etiquetadosEn muchos casos, es preciso atribuir a cada arista un n-mero especco, llamado valuacin, ponderacin o costesegn el contexto, y se obtiene as un grafo valuado.Formalmente, es un grafo con una funcin v: A R.Por ejemplo, un representante comercial tiene que visi-tar n ciudades 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 desde a hasta b, sin ms condicin.

6.4 Dimetro

En la gura se nota que K4 es plano (desviando la arista ab alexterior del cuadrado), que K5 no lo es, y que K3,2 lo es tambin(desvos en gris).

En un grafo, la distancia entre dos vrtices es el menornmero de aristas de un recorrido entre ellos. El dime-tro, en una gura 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 innito puede signicar que el grafo tiene una in-nidad de vrtices o simplemente que no es conexo. Tam-bin se puede considerar el dimetro 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 pginas web al azar: En cuntos clics sepuede 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 denicin, se estima que el dimetro de lahumanidad es de... ocho solamente!Este concepto reeja 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

7 Dirac, Gabriel Andrew

Dijkstra, Edsger

Edmonds, Jack

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 geometriam si-

tus pertinentis. Commentarii Academiae Scientiarum Im-perialis Petropolitanae 8. 128-140.

[2] http://booklens.com/l-r-foulds/graph-theory-applications pag 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 Commons alberga contenido multi-media sobre Teora 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 deuna entrada de la Enciclopedia Libre Universal,publicada en espaol bajo la licencia CreativeCommons Compartir-Igual 3.0.

8 12 TEXTO E IMGENES DE ORIGEN, COLABORADORES Y LICENCIAS

12 Texto e imgenes de origen, colaboradores y licencias12.1 Texto

Teora de grafos Fuente: http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos?oldid=82595550 Colaboradores: Pino, Rumpelstilts-kin, Rosarino, Ascnder, Julian Colina, Tano4595, PeiT, Taxman, Rondador, La Mantis, AlfonsoERomero, Emijrp, Rmolina, RobotQuist-nix, Alhen, BOT-Superzerocool, Boku wa kage, YurikBot, Equi, Otermin, Tomatejc, Mencey, Nihilo, Tessier, Ilan.ag1, BOTpolicia, Ada-ma~eswiki, Ludoviko, Rdaneel, Hawking, CEM-bot, Ferminmx, JMCC1, Alexav8, Baiji, Roberpl, Mcetina, Ingenioso Hidalgo, Thijs!bot,Ingridchan, Pablo Olmos, Tortillovsky, Davidrodriguez, IrwinSantos, Seba.29.8, Zifra, Sapiensjpa, Botones, Gusgus, Mpeinadopa, JAnD-bot, Nando.sm, Inmortra, Aalvarez12, Gullo, Humberto, Pabloallo, Esteban fcr, Chabbot, Plux, Rovnet, Mundokeko, VolkovBot, Xinu-Xano, Elmermosher, Matdrodes, AlleborgoBot, Muro Bot, Feministo, Numbo3, Gerakibot, SieBot, Loveless, Drinibot, Macarse, Raul.lara,Xiscobernal, PipepBot, Schwallex, Gato ocioso, Farisori, Eduardosalg, Neodop, Botelln, Leonpolanco, LordT, Juan Mayordomo, Darki-cebot, Aikasse, BodhisattvaBot, Raulshc, AVBOT, LucienBOT, MastiBot, Diegusjaimes, A.garridob, Luckas-bot, Ricardo Castelo, ElQuinche, Kilom691, Vic Fede, Habilbakhat, Marioxcc, Medium69, Diogeneselcinico42, SuperBraulio13, Xqbot, Jkbw, Angenio2, Bota-rel, 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, MetroBot, Invadibot,SoleFabrizio, Leitoxx, Addbot, DaveGomez, JacobRodrigues, Gonzalo.villarreal, Julian Araoz, Lectorina y Annimos: 169

12.2 Imgenes Archivo:6n-graph2.svg Fuente: http://upload.wikimedia.org/wikipedia/commons/2/28/6n-graph2.svg Licencia: Public domain Colabo-

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

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.svg Licencia: Public domainColaboradores: This version created by Pumbaa, using a proper partial circle and SVG geometry features. (Former versions used to be slightlywarped.) Artista original: SVG version was created by User:Grunt and cleaned up by 3247, based on the earlier PNG version, created byReidab.

Archivo:Connexe_et_pas_connexe.svg Fuente: http://upload.wikimedia.org/wikipedia/commons/6/65/Connexe_et_pas_connexe.svgLicencia: CC BY-SA 4.0 Colaboradores: Trabajo propio Artista original: Kilom691

Archivo:Dart_graph.svg Fuente: http://upload.wikimedia.org/wikipedia/commons/9/96/Dart_graph.svg Licencia: CC BY-SA 3.0 Cola-boradores: Trabajo propio Artista original: Koko90

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

Archivo:Fish_graph.svg Fuente: http://upload.wikimedia.org/wikipedia/commons/e/ee/Fish_graph.svg Licencia: CC BY-SA 3.0 Cola-boradores: Trabajo propio Artista original: Koko90

Archivo:Grafo_ejemplo_3_rbol.png Fuente: http://upload.wikimedia.org/wikipedia/commons/c/cc/Grafo_ejemplo_3_%C3%A1rbol.png Licencia: CC-BY-SA-3.0 Colaboradores: Transferido desde es.wikipedia a Commons. Artista original: Romero Schmidtke deWikipedia en espaol

Archivo:Grafo_ejemplo_5_conecsi.png Fuente: http://upload.wikimedia.org/wikipedia/commons/5/50/Grafo_ejemplo_5_conecsi.pngLicencia: CC-BY-SA-3.0 Colaboradores: Transferido desde es.wikipedia a Commons. Artista original: Romero Schmidtke de Wikipediaen espaol

Archivo:Grafo_ejemplo_5_pases.png Fuente: http://upload.wikimedia.org/wikipedia/commons/5/5e/Grafo_ejemplo_5_pa%C3%ADses.png Licencia: CC-BY-SA-3.0 Colaboradores: Transferido desde es.wikipedia a Commons. Artista original: Romero Schmidtke deWikipedia en espaol

Archivo:Grafo_ejemplo_6.png Fuente: http://upload.wikimedia.org/wikipedia/commons/0/04/Grafo_ejemplo_6.png Licencia: CC-BY-SA-3.0 Colaboradores: Transferido desde es.wikipedia a Commons. Artista original: Romero Schmidtke de Wikipedia en espaol

Archivo:Grafo_ejemplo_7.png Fuente: http://upload.wikimedia.org/wikipedia/commons/f/f7/Grafo_ejemplo_7.png Licencia: CC-BY-SA-3.0 Colaboradores: Transferido desde es.wikipedia a Commons. Artista original: Romero Schmidtke de Wikipedia en espaol

Archivo:Hamiltonian_path.svgFuente: http://upload.wikimedia.org/wikipedia/commons/6/60/Hamiltonian_path.svgLicencia:CC-BY-SA-3.0 Colaboradores: Trabajo propio Artista original: Christoph Sommer

12.3 Licencia de contenido Creative Commons Attribution-Share Alike 3.0

Historia Aplicaciones Tipos de grafos Representacin de grafos Estructura de lista Estructuras matriciales

Problemas de teora de grafos Ciclos y caminos hamiltonianos Grafos planos Coloracin de grafos Teorema de los cuatro colores

Caracterizacin de grafos Grafos simples Grafos conexos Grafos completos Grafos bipartitos

Homeomorfismo de grafos rboles Grafos ponderados o etiquetados Dimetro

Algoritmos importantes Investigadores relevantes en Teora de grafos Vase tambin Referencias Enlaces externos Texto e imgenes de origen, colaboradores y licenciasTextoImgenesLicencia de contenido