Hispanopedia Wiki
Articulo de referencia

teoría de grafos

Un grafo con 6 vértices y 7 aristas En matemáticas e informática , la teoría de grafos estudia los grafos , que son estructuras matemáticas utilizadas para modelar relaciones bi...

Hispanopedia WikiContenido en espanolLectura gratuita
Un grafo con 6 vértices y 7 aristas

En matemáticas e informática , la teoría de grafos estudia los grafos , que son estructuras matemáticas utilizadas para modelar relaciones binarias entre objetos. Un grafo, en este contexto, está formado por vértices (también llamados nodos o puntos) conectados por aristas (también llamadas arcos, enlaces o líneas). Se distingue entre grafos no dirigidos, donde las aristas unen dos vértices simétricamente, y grafos dirigidos , donde las aristas unen dos vértices asimétricamente. Los grafos son uno de los principales objetos de estudio en matemáticas discretas .

Definición y etimología

Un grafo consta de vértices conectados por aristas. A veces se denomina grafo:

  • Un grafo no dirigido (arriba a la izquierda), que se distingue de un grafo dirigido que tiene una flecha en cada arista (arriba a la derecha). Los grafos no dirigidos y dirigidos se pueden fusionar en un grafo mixto (abajo a la izquierda); y
  • Un gráfico simple, que se distingue de un multigrafo (abajo a la derecha).

La teoría de grafos es una rama de las matemáticas que estudia los grafos , estructuras matemáticas para modelar relaciones binarias entre objetos. Forma parte de las matemáticas discretas , a menudo considerada parte de la combinatoria , aunque es un campo independiente debido a su gran crecimiento y distinto de otros campos, ya que presenta su propio tipo de problemas. [ 1 ] El término "grafo" fue introducido por James Joseph Sylvester en un artículo publicado en 1878 en Nature , donde estableció una analogía entre los "invariantes cuánticos" y los "covariantes" del álgebra y los diagramas moleculares. [ 2 ]

La definición de un grafo puede variar, pero se puede entender que un grafo es una estructura que consta de vértices (también llamados nodos o puntos) y aristas (también llamadas arcos, enlaces o líneas). Dos vértices de una arista se llaman puntos extremos. [ 3 ] Ocasionalmente, un grafo se denomina grafo no dirigido, para distinguirlo de un grafo dirigido . Un grafo dirigido es un grafo donde cada arista tiene una dirección asignada conocida como orientación , designada con una flecha. [ 4 ] Un grafo mixto puede tener aristas que pueden ser dirigidas y algunas pueden ser no dirigidas. [ 5 ] Un grafo también puede denominarse grafo simple, para distinguirlo de un multigrafo . Un multigrafo permite que muchas aristas tengan el mismo par de puntos extremos, y también permite que una arista conecte un vértice consigo mismo, lo que se conoce como bucle . [ 6 ] A un grafo se le puede asignar un número a sus aristas, que se conoce como peso. Dicho grafo se denomina grafo ponderado.

Historia

Mapa de Königsberg de 1651 que muestra la disposición de los siete puentes , destacando el río Pregel (en azul) y los puentes (en verde lima). Este problema sienta las bases tanto de la teoría de grafos como de la topología .

En 1736, Leonhard Euler publicó un artículo titulado Solutio Problematis ad Geometriam Situs Pertinentis sobre los Siete Puentes de Königsberg , considerado el primer artículo en la historia de la teoría de grafos. [ 7 ] El artículo de Euler y el artículo de Alexandre-Théophile Vandermonde de 1771 , Remarques sur les Problèmes de Situation sobre el recorrido del caballero, continuaron con el análisis situs , iniciado por Gottfried Wilhelm Leibniz . [ 8 ] La característica de Euler que relaciona el número de aristas, vértices y caras de un poliedro convexo fue estudiada y generalizada por Augustin-Louis Cauchy y Simon Antoine Jean L'Huilier , [ 9 ] y representa el comienzo de la rama de las matemáticas conocida como topología . [ 10 ]

Más de un siglo después del artículo de Euler sobre los puentes de Königsberg , y mientras Johann Benedict Listing introducía el concepto de topología, Arthur Cayley, impulsado por un interés en formas analíticas particulares derivadas del cálculo diferencial, estudió una clase particular de grafos: los árboles . [ 11 ] Este estudio tuvo muchas implicaciones para la química teórica . Las técnicas que empleó se centran principalmente en la enumeración de grafos con propiedades particulares. La teoría enumerativa de grafos surgió entonces de los resultados de Cayley y de los resultados fundamentales publicados por Pólya entre 1935 y 1937. Estos fueron generalizados por Nicolaas Govert de Bruijn en 1959. Cayley vinculó sus resultados sobre árboles con estudios contemporáneos de composición química. [ 11 ] La fusión de ideas de las matemáticas con las de la química dio origen a lo que se ha convertido en parte de la terminología estándar de la teoría de grafos.

El desarrollo autónomo de la topología entre 1860 y 1930 fertilizó la teoría de grafos a través de las obras de Camille Jordan , Kazimierz Kuratowski y Hassler Whitney . Otro factor importante en el desarrollo común de la teoría de grafos y la topología provino del uso de las técnicas del álgebra moderna. El primer ejemplo de dicho uso proviene del trabajo del físico Gustav Kirchhoff , quien publicó en 1845 sus leyes de circuitos de Kirchhoff para calcular el voltaje y la corriente en circuitos eléctricos .

El primer libro de texto sobre teoría de grafos fue escrito por Dénes Kőnig y publicado en 1936. [ 12 ] Otro libro de Frank Harary , publicado en 1969, fue considerado mundialmente como el libro de texto definitivo sobre el tema, [ 13 ] y permitió que matemáticos, químicos, ingenieros eléctricos y científicos sociales se comunicaran entre sí. Harary donó todos los derechos de autor para financiar el Premio Pólya . [ 14 ]

Uno de los problemas más famosos de la teoría de grafos es el problema de los cuatro colores : ¿Es cierto que cualquier mapa dibujado en el plano puede tener sus regiones coloreadas con cuatro colores, de tal manera que dos regiones cualesquiera con una frontera común tengan colores diferentes? Este problema fue planteado por primera vez por Francis Guthrie en 1852, y su primer registro escrito se encuentra en una carta de Augustus De Morgan dirigida a William Rowan Hamilton ese mismo año. Se han propuesto muchas demostraciones incorrectas, incluidas las de Augustin Cayley, Alfred Kempe y otros. El estudio y la generalización de este problema por Peter Tait , Percy John Heawood , Frank P. Ramsey y Hadwiger condujeron al estudio de las coloraciones de los grafos incrustados en superficies con género arbitrario . La reformulación de Tait generó una nueva clase de problemas, los problemas de factorización , estudiados particularmente por Petersen y Dénes Kőnig . Los trabajos de Ramsey sobre coloraciones, y más especialmente los resultados obtenidos por Pál Turán en 1941, fueron el origen de otra rama de la teoría de grafos, conocida como teoría extremal de grafos .

El problema de los cuatro colores permaneció sin resolver durante más de un siglo. En 1969, Heinrich Heesch publicó un método para resolver el problema utilizando computadoras. [ 15 ] Una demostración asistida por computadora, realizada en 1976 por Kenneth Appel y Wolfgang Haken, utiliza fundamentalmente la noción de "descarga" desarrollada por Heesch. [ 16 ] [ 17 ] La demostración implicó verificar las propiedades de 1936 configuraciones mediante computadora y no fue completamente aceptada en su momento debido a su complejidad. Una demostración más simple, que consideraba solo 633 configuraciones, fue presentada veinte años después por Robertson , Seymour , Sanders y Thomas . [ 18 ]

La introducción de métodos probabilísticos en la teoría de grafos, especialmente en el estudio de Erdős y Rényi sobre la probabilidad asintótica de la conectividad de grafos, dio origen a otra rama, conocida como teoría de grafos aleatorios , que ha sido una fuente fructífera de resultados en teoría de grafos. [ 19 ]

Subáreas

Teoría topológica de grafos

La teoría topológica de grafos se ocupa del estudio de los grafos relacionados con la topología. Los temas, junto con las ilustraciones dadas de arriba a abajo, son:

La teoría topológica de grafos se ocupa del estudio de los grafos como espacios topológicos . El grafo en una topología es un conjunto de símplices que se denomina complejo unidimensional simplicial . [ 20 ] Esta subárea estudia la incrustación (o inmersión) de un grafo en incrustaciones de superficie y sin enlaces , menores de grafos , número de cruces , coloración de mapas y grafo de voltaje . [ 21 ]

La incrustación de un grafo en una superficie es la representación de un grafo en la que los puntos se asocian con los vértices y los arcos simples con las aristas de la superficie. Los extremos se asocian con una arista y los puntos con los vértices extremos. Ningún arco incluye puntos asociados con otros vértices, y dos arcos nunca se intersecan en un punto interior a ninguno de ellos. La incrustación de grafos se puede generalizar a la incrustación sin enlaces, en la que no hay dos ciclos del grafo enlazados en el espacio euclidiano tridimensional, [ 22 ] y a un libro , una colección de semiplanos que tienen la misma línea como límite. [ 23 ]

Se dice que el grafo es menor si se puede formar a partir de otro grafo eliminando vértices y aristas, y mediante la contracción de aristas . [ 22 ] El primer resultado de la teoría de los menores de grafos proviene del teorema de Wagner , que establece que un grafo finito es planar si y solo si su menor no incluye ni el grafo completo de cinco vérticesK5{\displaystyle K_{5}}ni el grafo de utilidad . [ 24 ] Un resultado relacionado es el teorema de Robertson-Seymour , que implica la existencia de un menor prohibido para cada propiedad de los grafos preservada por eliminaciones y contracciones de aristas. [ 25 ]

El número de cruces indica el número mínimo de aristas que se cruzan en un grafo. Este estudio se originó a partir de una propuesta del matemático húngaro Pál Turán, quien solicitó un plano de fábrica que minimizara el número de cruces entre las vías que conectan los hornos de ladrillos con los almacenes . Este problema puede formalizarse como la búsqueda del número de cruces de un grafo bipartito completo . [ 26 ]

La coloración de un grafo es una asignación metódica de etiquetas a los elementos del mismo, lo que tradicionalmente se denomina coloración . En la coloración, dos elementos adyacentes no pueden tener el mismo color. Se requiere un número mínimo de colores, conocido como número cromático. El teorema de los cuatro colores establece que no se requieren más de cuatro colores para colorear las regiones de cualquier mapa de manera que dos regiones adyacentes no tengan el mismo color; es decir, que dos regiones no compartan un límite común. [ 27 ] Este teorema es más fuerte que el teorema de los cinco colores . En relación con esto, el problema Tierra-Luna es conocido por ser un problema abierto actualmente sobre la extensión del problema de coloración de mapas planos, resuelto mediante el teorema de los cuatro colores.

Un grafo de voltaje es un grafo dirigido cuyas aristas están etiquetadas de forma invertible por elementos de un grupo . Este grafo especifica concisamente el grafo derivado . [ 28 ] También es una forma común de formar un grafo de recubrimiento . [ 29 ]

Teoría algebraica de grafos

La teoría algebraica de grafos utiliza la teoría de grupos para estudiar la simetría de un grafo. Por ejemplo, el grafo de Petersen es altamente simétrico, conocido por ser transitivo en vértices , simétrico , transitivo en distancia y regular en distancia . Su grupo de automorfismos tiene 120 elementos y grupo simétrico.S5{\displaystyle S_{5}}.

La teoría algebraica de grafos es el estudio de la teoría de grafos que involucra las principales ramas del álgebra . Las principales ramas del álgebra que se utilizan son el álgebra lineal y la teoría de grupos .

El estudio de la teoría de grafos mediante álgebra lineal se denomina teoría espectral de grafos . Este estudio se centra en la matriz de adyacencia , una matriz que representa el grafo, y su espectro , que se centra en el polinomio característico , los valores propios y los vectores propios de la matriz de adyacencia dada. También se centra en la matriz laplaciana de un grafo, que involucra la matriz de grados (una matriz diagonal que representa el grado de un vértice) y la matriz de adyacencia. [ 30 ]

La teoría de grupos, en particular los grupos de automorfismos y la teoría geométrica de grupos , se centra en diversas familias de grafos basadas en la simetría en la teoría algebraica de grafos. [ 31 ] Dicha simetría incluye grafos simétricos , grafos transitivos en vértices , grafos transitivos en aristas , grafos transitivos en distancia , grafos regulares en distancia y grafos fuertemente regulares . [ 32 ] El teorema de Frucht establece que todo grupo finito es el grupo de simetrías de un grafo finito no dirigido, o más fuertemente, existen infinitos grafos conexos simples no isomorfos tales que el grupo de automorfismos de cada uno de ellos es isomorfo a un grupo finito. [ 33 ]

La teoría algebraica de grafos también estudia los invariantes algebraicos , el polinomio cromático , el polinomio de Tutte de un grafo y el invariante de nudo . [ 32 ] Un invariante de grafo es una propiedad de los grafos que depende únicamente de la estructura abstracta, en lugar de las etiquetas o dibujos del grafo. Un polinomio cromático es un polinomio que cuenta el número de coloraciones de grafos en función del número de colores. [ 34 ] El polinomio de Tutte es un polinomio de dos variables sobre la conectividad de grafos. [ 35 ]

teoría geométrica de grafos

La teoría geométrica de grafos estudia combinatoriamente un grafo dibujado con líneas rectas o aristas curvas continuas con propiedades geométricas. En estas ilustraciones, la teoría geométrica de grafos estudia:

La teoría geométrica de grafos se centra en las propiedades combinatorias y geométricas de un grafo dibujado en un plano con aristas rectas o curvas continuas en el espacio euclidiano . [ 36 ] Como parte de la geometría discreta y la geometría computacional , la teoría geométrica de grafos estudia los grafos planares , [ 37 ] la relación con politopos convexos de dimensiones superiores , [ 38 ] la intersección de conjuntos con formas geométricas, [ 39 ] y otras subáreas de geometrías como la geometría de incidencia y la geometría proyectiva . [ 40 ]

Un grafo planar cuyos vértices están incrustados como puntos y cuyas aristas son segmentos de línea que no se cruzan en el plano euclidiano se denomina grafo planar de líneas rectas . Cualquier grafo planar puede representarse como un grafo planar de líneas rectas mediante el teorema de Fáry . El grafo planar de líneas rectas es un caso especial de un grafo euclidiano. El grafo euclidiano permite que sus aristas tengan la longitud de la distancia euclidiana entre sus extremos. Sus nociones son el árbol de expansión mínima euclidiana, que consiste en minimizar la longitud total de los segmentos para un número finito de puntos en cualquier espacio euclidiano ; el problema de Hadwiger-Nelson, que consiste en buscar el número mínimo de planos de coloración tales que no haya dos puntos a una distancia unitaria entre sí que tengan el mismo color; y el problema del camino más corto , que consiste en encontrar un camino entre dos vértices en un grafo que minimice la suma de los valores asignados a sus aristas. [ 37 ]

Un grafo de visibilidad es un grafo cuyos vértices y aristas son las ubicaciones de los puntos y las conexiones visibles, respectivamente. En un polígono simple , donde sus aristas no se autointersecan y no tienen agujeros, los vértices de un grafo de visibilidad están conectados por aristas que representan los lados y las diagonales de un polígono. Los vértices se definen como las ubicaciones de los puntos. [ 41 ] Un grafo poliédrico es un grafo no dirigido que forma los vértices y las aristas de un poliedro convexo tridimensional . Para lograrlo, dicho grafo debe cumplir los requisitos del teorema de Steinitz , que establece que todo poliedro convexo es un grafo planar conexo de 3 vértices . El grafo planar permanece conexo siempre que se eliminen dos cualesquiera de sus vértices. [ 42 ]

Un grafo de intersección es un grafo en el que cada vértice está asociado con un conjunto y en el que los vértices están conectados por aristas siempre que los conjuntos correspondientes tengan una intersección no vacía . [ 39 ] Cada vértice se representa como un conjunto, y cada par de vértices están conectados. Por lo tanto, el grafo de intersección de conjuntos finitos se puede representar mediante el número más pequeño de elementos requeridos, conocido como el número de intersección . El grafo resultante puede ser geométrico siempre que los conjuntos sean objetos geométricos. Por ejemplo, el grafo de intersección de segmentos de línea en una dimensión es un grafo de intervalo . El grafo de intersección de discos unitarios en el plano es un grafo de disco unitario . La intersección de un empaquetamiento de círculos es un grafo de moneda , donde un vértice y una arista representan un círculo y cada par de círculos tangentes; por el teorema de Koebe-Andreev-Thurston, los grafos de intersección de círculos que no se cruzan son exactamente los grafos planares. [ 43 ] El teorema de Scheinerman establece que todo grafo planar se puede representar como el grafo de intersección de segmentos de línea en el plano. [ 44 ]

El grafo de Levi es un grafo bipartito que se asocia a la estructura de incidencia y a la configuración proyectiva . [ 40 ]

Al aplicarse a la visualización de información , esto crea otra subárea de la teoría de grafos que se conoce como dibujo de grafos , que visualiza una representación de un grafo. Frecuentemente dibujados como diagramas de nodos y enlaces, los vértices de un grafo se representan como discos, cajas o etiquetas de texto, y las aristas se representan como segmentos de línea, polilíneas o curvas en el plano euclidiano. [ 45 ] Muchas definiciones para dibujos de grafos basadas en medidas de calidad incluyen el número de cruces, [ 46 ] el área , la visualización de simetría al encontrar el problema del automorfismo de grupo de un grafo, [ 47 ] la minimización de curvatura , la resolución angular , [ 48 ] y el número de pendiente . [ 48 ] Las herramientas para dibujos de grafos son el empaquetamiento de círculos, [ 49 ] el grafo de intersección y otras visualizaciones de la matriz de adyacencia.

teoría de grafos extremal

La teoría extremal de grafos estudia el número máximo de aristas de un grafo, conocido como número extremal. Su origen se encuentra en el teorema de Mantel sobre cómo hallar el número extremal de un grafo sin triángulos (ilustrado), que es⌊norte2/4⌋{\displaystyle \lfloor n^{2}/4\rfloor }.

La teoría de grafos extremal es una rama de las matemáticas que se encuentra en la intersección de la combinatoria extremal y la teoría de grafos. Esta área estudia el número máximo de aristas de un grafo, conocido como número extremal. [ 50 ] El hito de esta subárea se originó a partir del teorema de Mantel sobre el número extremal de un grafo sin triángulos . El teorema de Turán extendió el teorema de Mantel a cualquier grafo no dirigido que no tenga un subgrafo completo de un tamaño dado. El teorema de Turán se generaliza mediante el teorema de Erdős-Stone , que ocasionalmente se conoce como el "teorema fundamental de la teoría de grafos extremal". [ 51 ]

La teoría de grafos extremales también estudia el problema de los subgrafos prohibidos , la densidad de homomorfismos y el lema de regularidad de Szemerédi . El problema de los subgrafos prohibidos sugiere encontrar el número extremal de un grafo connorte{\displaystyle n}vértices tales que no tiene un subgrafo que sea isomorfo al grafo. [ 52 ] Una densidad de homomorfismo es un parámetro que involucra el homomorfismo de grafos . La densidad puede referirse a la probabilidad de que un mapeo de los vértices de un grafo a los vértices de otro elegido uniformemente al azar sea un homomorfismo de grafos. Ser homomórfico significa que existe un mapeo entre dos grafos que respeta su estructura, o equivalentemente, una función entre los conjuntos de vértices de dos grafos que mapea vértices adyacentes a vértices adyacentes. [ 53 ] El lema de regularidad de Szemerédi establece que un grafo puede particionarse en un número limitado de partes de modo que las aristas entre las partes seanε{\displaystyle \varepsilon }-regular.

Teoría de grafos aleatorios

La teoría de grafos aleatorios se centra en grafos que utilizan métodos probabilísticos . Esta subárea fue fundada por los matemáticos húngaros Paul Erdős y Alfréd Rényi , cuyo modelo genera grafos aleatorios, conocido como modelo de Erdős-Rényi . [ 19 ]

Árbol de expansión mínima aleatorio en el mismo grafo pero con pesos aleatorios.

Esta subárea estudia el árbol aleatorio . Un árbol es un grafo no dirigido donde cada par de vértices está conectado por exactamente un camino . Por lo tanto, un árbol aleatorio es un árbol que se forma mediante un proceso estocástico . Muchos tipos de árboles aleatorios incluyen:

enumeración de grafos

Aplicaciones

El gráfico de red formado por los editores de Wikipedia (aristas) que contribuyeron a diferentes versiones lingüísticas de Wikipedia (vértices) durante un mes en el verano de 2013 [ 58 ]

Los grafos pueden utilizarse para modelar muchos tipos de relaciones y procesos en sistemas físicos, biológicos, [ 59 ] [ 60 ] sociales y de información. [ 61 ] Muchos problemas prácticos pueden representarse mediante grafos. Haciendo hincapié en su aplicación a sistemas del mundo real, el término red se define a veces como un grafo en el que los atributos (por ejemplo, nombres) están asociados con los vértices y las aristas, y la disciplina que expresa y comprende los sistemas del mundo real como una red se denomina ciencia de redes .

Ciencias de la Computación

En informática , las estructuras enlazadas « causales » y «no causales» son grafos que se utilizan para representar redes de comunicación, organización de datos, dispositivos computacionales, flujo de computación, etc. Por ejemplo, la estructura de enlaces de un sitio web puede representarse mediante un grafo dirigido, en el que los vértices (nodos) representan páginas web y las aristas dirigidas representan enlaces de una página a otra. Un enfoque similar puede aplicarse a problemas en redes sociales, [ 62 ] viajes, biología, diseño de chips informáticos, mapeo de la progresión de enfermedades neurodegenerativas, [ 63 ] [ 64 ] y muchos otros campos. Por lo tanto, el desarrollo de algoritmos para manejar grafos es de gran interés en informática. La transformación de grafos a menudo se formaliza y representa mediante sistemas de reescritura de grafos . Complementarios a los sistemas de transformación de grafos que se centran en la manipulación en memoria basada en reglas de grafos son las bases de datos de grafos orientadas al almacenamiento y consulta persistente y seguro de transacciones de datos estructurados en grafos .

Lingüística

Los métodos de la teoría de grafos, en diversas formas, han demostrado ser particularmente útiles en lingüística , ya que el lenguaje natural a menudo se presta bien a la estructura discreta. Tradicionalmente, la sintaxis y la semántica composicional siguen estructuras basadas en árboles, cuyo poder expresivo reside en el principio de composicionalidad , modelado en un grafo jerárquico. Enfoques más contemporáneos, como la gramática de estructura de frases dirigida por núcleos, modelan la sintaxis del lenguaje natural utilizando estructuras de rasgos tipificadas , que son grafos acíclicos dirigidos . Dentro de la semántica léxica , especialmente cuando se aplica a las computadoras, modelar el significado de las palabras es más fácil cuando una palabra dada se entiende en términos de palabras relacionadas; por lo tanto, las redes semánticas son importantes en la lingüística computacional . Aun así, otros métodos en fonología (por ejemplo, la teoría de la optimalidad , que utiliza grafos reticulares ) y morfología (por ejemplo, la morfología de estados finitos, que utiliza transductores de estados finitos ) son comunes en el análisis del lenguaje como un grafo. De hecho, la utilidad de esta área de las matemáticas para la lingüística ha dado lugar a organizaciones como TextGraphs , así como a varios proyectos de "redes", como WordNet , VerbNet y otros.

Física y química

La teoría de grafos también se utiliza para estudiar moléculas en química y física . En física de la materia condensada , la estructura tridimensional de estructuras atómicas simuladas complejas se puede estudiar cuantitativamente mediante la recopilación de estadísticas sobre propiedades de la teoría de grafos relacionadas con la topología de los átomos. Además, "los grafos de Feynman y las reglas de cálculo resumen la teoría cuántica de campos de una forma que guarda un estrecho contacto con los datos experimentales que se desean comprender". [ 65 ] En química, un grafo constituye un modelo natural para una molécula, donde los vértices representan átomos y las aristas enlaces . Este enfoque se utiliza especialmente en el procesamiento informático de estructuras moleculares, desde editores químicos hasta búsquedas en bases de datos. En física estadística , los grafos pueden representar conexiones locales entre partes interactuantes de un sistema, así como la dinámica de un proceso físico en dichos sistemas. De manera similar, en neurociencia computacional, los grafos se pueden utilizar para representar conexiones funcionales entre áreas cerebrales que interactúan para dar lugar a diversos procesos cognitivos, donde los vértices representan diferentes áreas del cerebro y las aristas representan las conexiones entre esas áreas. La teoría de grafos desempeña un papel importante en el modelado eléctrico de redes eléctricas; en este caso, se asocian pesos con la resistencia de los segmentos de cable para obtener las propiedades eléctricas de las estructuras de la red. [ 66 ] Los grafos también se utilizan para representar los canales a microescala de medios porosos , donde los vértices representan los poros y las aristas representan los canales más pequeños que los conectan. La teoría de grafos químicos utiliza el grafo molecular como medio para modelar moléculas. Los grafos y las redes son excelentes modelos para estudiar y comprender las transiciones de fase y los fenómenos críticos. La eliminación de nodos o aristas conduce a una transición crítica en la que la red se divide en pequeños cúmulos, lo que se estudia como una transición de fase. Esta ruptura se estudia mediante la teoría de la percolación . [ 67 ]

ciencias sociales

Teoría de grafos en sociología: Sociograma de Moreno (1953). [ 68 ]

La teoría de grafos también se utiliza ampliamente en sociología como una forma, por ejemplo, de medir el prestigio de los actores o de explorar la propagación de rumores , especialmente mediante el uso de software de análisis de redes sociales . Bajo el paraguas de las redes sociales se encuentran muchos tipos diferentes de grafos. [ 69 ] Los grafos de conocidos y amistad describen si las personas se conocen entre sí. Los grafos de influencia modelan si ciertas personas pueden influir en el comportamiento de otras. Finalmente, los grafos de colaboración modelan si dos personas trabajan juntas de una manera particular, como actuar juntas en una película.

Biología y ecología

Asimismo, la teoría de grafos resulta útil en biología y en la conservación, donde un vértice puede representar regiones donde existen (o habitan) ciertas especies y las aristas representan rutas migratorias o el movimiento entre dichas regiones. Esta información es importante para analizar los patrones de reproducción o rastrear la propagación de enfermedades y parásitos, o cómo los cambios en el movimiento pueden afectar a otras especies.

Los grafos también se utilizan comúnmente en biología molecular y genómica para modelar y analizar conjuntos de datos con relaciones complejas. Por ejemplo, los métodos basados ​​en grafos se utilizan a menudo para agrupar células en tipos celulares en el análisis del transcriptoma de células individuales . Otro uso es modelar genes o proteínas en una vía metabólica y estudiar las relaciones entre ellos, como las vías metabólicas y las redes de regulación génica. [ 70 ] Los árboles evolutivos, las redes ecológicas y la agrupación jerárquica de patrones de expresión génica también se representan como estructuras de grafos.

La teoría de grafos también se utiliza en la conectómica ; [ 71 ] los sistemas nerviosos pueden verse como un grafo, donde los nodos son neuronas y las aristas son las conexiones entre ellas.

Otros temas

Una estructura gráfica puede extenderse asignando un peso a cada arista. Los grafos ponderados se utilizan para representar estructuras en las que las conexiones entre pares de aristas tienen valores numéricos. Por ejemplo, si un grafo representa una red de carreteras, los pesos podrían representar la longitud de cada carretera. Cada arista puede tener varios pesos asociados, como la distancia (como en el ejemplo anterior), el tiempo de viaje o el coste. Estos grafos ponderados se utilizan habitualmente para programar sistemas GPS y motores de búsqueda de viajes que comparan tiempos y costes de vuelo.

Representación

Un grafo es una abstracción de las relaciones que surgen en la naturaleza; por lo tanto, no puede asociarse a una representación específica. La forma en que se representa depende del grado de conveniencia que dicha representación ofrezca para una aplicación determinada. Las representaciones más comunes son la visual, en la que, generalmente, se dibujan los vértices y se conectan mediante aristas, y la tabular, en la que las filas de una tabla proporcionan información sobre las relaciones entre los vértices del grafo.

Visual: Dibujo de gráficos

Los grafos se representan visualmente dibujando un punto o un círculo por cada vértice, y una línea entre dos vértices conectados por una arista. Si el grafo es dirigido, la dirección se indica con una flecha. Si el grafo es ponderado, el peso se añade a la flecha.

No se debe confundir el dibujo de un grafo con el grafo en sí (la estructura abstracta y no visual), ya que existen diversas maneras de estructurarlo. Lo importante es qué vértices están conectados entre sí mediante cuántas aristas, y no la disposición exacta. En la práctica, suele ser difícil determinar si dos dibujos representan el mismo grafo. Dependiendo del ámbito del problema, algunas representaciones pueden ser más adecuadas y fáciles de comprender que otras.

La labor pionera de WT Tutte fue muy influyente en el campo de la representación gráfica. Entre otros logros, introdujo el uso de métodos algebraicos lineales para obtener representaciones gráficas.

El dibujo de grafos también abarca problemas relacionados con el número de cruces y sus diversas generalizaciones. El número de cruces de un grafo es el número mínimo de intersecciones entre aristas que debe contener un dibujo del grafo en el plano. Para un grafo planar , el número de cruces es cero por definición. También se estudian los dibujos en superficies distintas del plano.

Existen otras técnicas para visualizar un grafo más allá de los vértices y las aristas, como los empaquetamientos de círculos , el grafo de intersección y otras visualizaciones de la matriz de adyacencia .

Tabular: Estructuras de datos de grafos

La representación tabular se presta bien a las aplicaciones computacionales. Existen diferentes maneras de almacenar grafos en un sistema informático. La estructura de datos utilizada depende tanto de la estructura del grafo como del algoritmo empleado para manipularlo. Teóricamente, se puede distinguir entre estructuras de lista y de matriz, pero en aplicaciones concretas, la mejor estructura suele ser una combinación de ambas. Las estructuras de lista suelen preferirse para grafos dispersos, ya que requieren menos memoria. Por otro lado, las estructuras de matriz proporcionan un acceso más rápido para algunas aplicaciones, pero pueden consumir grandes cantidades de memoria. Las implementaciones de estructuras de matriz dispersa que sean eficientes en arquitecturas informáticas paralelas modernas son objeto de investigación actual. [ 72 ]

Las estructuras de lista incluyen la lista de aristas , una matriz de pares de vértices, y la lista de adyacencia , que enumera por separado los vecinos de cada vértice: Al igual que la lista de aristas, cada vértice tiene una lista de los vértices a los que es adyacente.

Las estructuras matriciales incluyen la matriz de incidencia , una matriz de 0 y 1 cuyas filas representan vértices y cuyas columnas representan aristas, y la matriz de adyacencia , en la que tanto las filas como las columnas están indexadas por vértices. En ambos casos, un 1 indica dos objetos adyacentes y un 0 indica dos objetos no adyacentes. La matriz de grados indica el grado de los vértices. La matriz laplaciana es una forma modificada de la matriz de adyacencia que incorpora información sobre los grados de los vértices y es útil en algunos cálculos, como el teorema de Kirchhoff sobre el número de árboles de expansión de un grafo. La matriz de distancias , al igual que la matriz de adyacencia, tiene tanto sus filas como sus columnas indexadas por vértices, pero en lugar de contener un 0 o un 1 en cada celda, contiene la longitud del camino más corto entre dos vértices.

Problemas

Enumeración

Existe una amplia bibliografía sobre enumeración gráfica : el problema de contar grafos que cumplen ciertas condiciones. Parte de este trabajo se encuentra en Harary y Palmer (1973).

Subgrafos, subgrafos inducidos y menores

Un problema común, denominado problema de isomorfismo de subgrafos , consiste en encontrar un grafo fijo como subgrafo en un grafo dado. Una razón para interesarse en esta cuestión es que muchas propiedades de los grafos son hereditarias para los subgrafos, lo que significa que un grafo posee la propiedad si y solo si todos sus subgrafos también la poseen. Encontrar subgrafos maximales de un tipo determinado suele ser un problema NP-completo . Por ejemplo:

Un caso particular del isomorfismo de subgrafos es el problema del isomorfismo de grafos . Este problema plantea la cuestión de si dos grafos son isomorfos. Se desconoce si este problema es NP-completo o si puede resolverse en tiempo polinomial.

Un problema similar es encontrar subgrafos inducidos en un grafo dado. Nuevamente, algunas propiedades importantes de los grafos son hereditarias con respecto a los subgrafos inducidos, lo que significa que un grafo tiene una propiedad si y solo si todos sus subgrafos inducidos también la tienen. Encontrar subgrafos inducidos máximos de un tipo determinado también suele ser un problema NP-completo. Por ejemplo:

Otro problema de este tipo, el problema de contención de menores, consiste en encontrar un grafo fijo como menor de un grafo dado. Un menor o subcontracción de un grafo es cualquier grafo obtenido al tomar un subgrafo y contraer algunas (o ninguna) aristas. Muchas propiedades de los grafos son hereditarias para los menores, lo que significa que un grafo tiene una propiedad si y solo si todos sus menores también la tienen. Por ejemplo, el teorema de Wagner establece:

Un problema similar, el problema de contención de subdivisiones, consiste en encontrar un grafo fijo como subdivisión de un grafo dado. Una subdivisión u homeomorfismo de un grafo es cualquier grafo obtenido al subdividir algunas (o ninguna) aristas. La contención de subdivisiones está relacionada con propiedades de grafos como la planaridad . Por ejemplo, el teorema de Kuratowski establece:

Otro problema en la contención de subdivisiones es la conjetura de Kelmans-Seymour :

Otro tipo de problemas tiene que ver con el grado en que diversas especies y generalizaciones de grafos están determinadas por sus subgrafos sin puntos . Por ejemplo:

Coloreado de gráficos

Muchos problemas y teoremas en teoría de grafos tienen que ver con diversas formas de colorear grafos. Típicamente, se busca colorear un grafo de manera que no haya dos vértices adyacentes del mismo color, o con otras restricciones similares. También se puede considerar colorear aristas (posiblemente de manera que no haya dos aristas coincidentes del mismo color), u otras variaciones. Entre los resultados y conjeturas más conocidos sobre la coloración de grafos se encuentran los siguientes:

Subsunción y unificación

Las teorías de modelado de restricciones se refieren a familias de grafos dirigidos relacionados por un orden parcial . En estas aplicaciones, los grafos se ordenan por especificidad, lo que significa que los grafos más restringidos —que son más específicos y, por lo tanto, contienen mayor cantidad de información— se incluyen dentro de los más generales. Las operaciones entre grafos incluyen evaluar la dirección de una relación de subsunción entre dos grafos, si la hay, y calcular la unificación de grafos. La unificación de dos grafos de argumentos se define como el grafo más general (o su cálculo) que es consistente con (es decir, contiene toda la información de) las entradas, si tal grafo existe; se conocen algoritmos de unificación eficientes.

Para los marcos de restricciones estrictamente composicionales , la unificación de grafos es la función de satisfacibilidad y combinación suficiente. Entre las aplicaciones más conocidas se incluyen la demostración automática de teoremas y el modelado de la elaboración de estructuras lingüísticas .

Problemas de ruta

Flujo de red

Existen numerosos problemas que surgen especialmente de aplicaciones relacionadas con diversas nociones de flujos en redes , por ejemplo:

Problemas de visibilidad

Problemas de cobertura

Los problemas de cobertura en grafos pueden referirse a diversos problemas de cobertura de conjuntos en subconjuntos de vértices/subgrafos.

  • El problema del conjunto dominante es un caso especial del problema de cobertura de conjuntos donde los conjuntos son los vecindarios cerrados .
  • El problema de cobertura de vértices es un caso especial del problema de cobertura de conjuntos, donde los conjuntos a cubrir son todas las aristas.
  • El problema original de la cobertura de conjuntos, también llamado conjunto de colisión, se puede describir como una cobertura de vértices en un hipergrafo.

Problemas de descomposición

La descomposición, definida como la partición del conjunto de aristas de un grafo (con tantos vértices como sean necesarios para cada arista de la partición), plantea una amplia variedad de problemas. A menudo, el problema consiste en descomponer un grafo en subgrafos isomorfos a un grafo fijo; por ejemplo, descomponer un grafo completo en ciclos hamiltonianos. Otros problemas especifican una familia de grafos en la que se debe descomponer un grafo dado, por ejemplo, una familia de ciclos, o descomponer un grafo completo K n en n − 1 árboles específicos que tengan, respectivamente, 1, 2, 3, ..., n − 1 aristas.

Algunos problemas de descomposición específicos y problemas similares que se han estudiado incluyen:

Clases de grafos

Muchos problemas implican caracterizar los miembros de diversas clases de grafos. A continuación se muestran algunos ejemplos de este tipo de preguntas:

  • Enumerar los miembros de una clase
  • Caracterización de una clase en términos de subestructuras prohibidas
  • Determinar las relaciones entre clases (por ejemplo, ¿una propiedad de los grafos implica otra?).
  • Encontrar algoritmos eficientes para decidir la pertenencia a una clase.
  • Encontrar representaciones para los miembros de una clase

Véase también

Notas

  1. ↑ Mohar y Thomassen (2001) .
  2. ↑ Sylvester (1878) .
  3. ↑ Ore (1962) , pág. 1 . 
  4. ↑ Ore (1962) , pág. 2 . 
  5. ↑ Ore (1962) , pág. 3 . 
  6. ↑ Bollobás (2013) , pág. 7 . 
  7. ↑ Biggs, Lloyd y Wilson (1986) , págs. 2–3 . 
  8. ↑ Biggs, Lloyd y Wilson (1986) , págs. 21–22 . 
  9. ↑
  10. ↑ Richeson (2008) , pág. 63.
  11. 1 2 Cayley (1875) .
  12. ↑ Tutte (2001) , pág. 30 . 
  13. ↑ Gardner (1992) , pág. 203.
  14. ↑ Sociedad de Matemáticas Industriales y Aplicadas (2002) , pág. 26.
  15. ↑ Heinrich Heesch: Untersuchungen zum Vierfarbenproblem. Mannheim: Bibliographisches Institut 1969.
  16. ↑ Appel, K.; Haken, W. (1977), "Every planar map is four colorable. Part I. Discharge" (PDF) , Illinois J. Math. , 21 (3): 429–490 , doi : 10.1215/ijm/1256049011 .
  17. ↑ Appel, K.; Haken, W. (1977), "Every planar map is four-colorable. Part II. Reducibility", Illinois J. Math. , 21 (3): 491– 567, doi : 10.1215/ijm/1256049012 .
  18. ↑ Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R. (1997), "El teorema de los cuatro colores", Journal of Combinatorial Theory, Serie B , 70 : 2–44 , doi : 10.1006/jctb.1997.1750 .
  19. 1 2 Bollobás (2001) , pág. xi . 
  20. ↑ Gross y Tucker (2012) , pág. 1 . 
  21. ↑
  22. 1 2 Lovász (2006) , pág. 76.
  23. ↑ Persinger (1966) .
  24. ↑ Lovász (2006) , pág. 77.
  25. ↑ Lovász (2006) , pág. 78, Teorema 4.
  26. ↑ Foulds (1992) , pág. 71 . 
  27. ↑ Gross y Tucker (2012) , pág. 215 . 
  28. ↑ Gross y Tucker (2012) , pág. 57 . 
  29. ↑ Gross y Tucker (2012) , pág. 72 . 
  30. ↑
  31. ↑ Biggs (1993) , Capítulo 15: Automorfismos de grafos .
  32. ^ Godsil y Royle (2001) , págs. xii-ixi . 
  33. ↑ Gross y Tucker (2012) , pág. 70 . 
  34. ↑ Biggs (1993) , pág. 64 . 
  35. ↑ Biggs (1993) , pág. 98 . 
  36. ↑ Pach (2018) , pág. 257 . 
  37. ^ Bounceur , Bezoui y Euler (2019) , págs . 
  38. ↑
  39. 1 2 McKee y McMorris (1999) , pág. 1 – 2 . 
  40. 1 2 Grünbaum (2006) , pág. 181 . 
  41. ↑ Everett y Corneil (1995) .
  42. ↑ Ziegler (2007) , págs. 628–642.
  43. ↑
  44. ↑ Chalopin y Gonçalves (2009) .
  45. ^ Di Battista y otros. (1994) , pág. viii.
  46. ^ Di Battista y otros. (1994) , pág. 14.
  47. ^ Di Battista y otros. (1994) , pág. 16.
  48. 1 2 Pach y Sharir (2009) .
  49. ↑ Malitz y Papakostas (1994) .
  50. ^ Chartrand y col. (2024) , pág. 221 . Error de sfnp: sin destino: CITEREFChartrandJordonVatterZhang2024 ( ayuda ) 
  51. ↑ Bollobás (2013) , pág. 104 . 
  52. ↑ Bollobás (2013) , pág. 123 . 
  53. ↑
  54. ↑ Wilson (1996) .
  55. ↑ Sedgewick y Flajolet (2013) , pág. 286.
  56. ↑ Morin (2004) . sfnp error: no target: CITEREFMorin2004 ( ayuda )
  57. ↑ McDiarmid, Johnson y Stone (1997) .
  58. ↑ Hale, Scott A. (2014). «Multilingües y edición de Wikipedia». Actas de la conferencia ACM de 2014 sobre ciencia web . págs. 99–108 . arXiv : 1312.0976 . Bibcode : 2013arXiv1312.0976H . doi : 10.1145/2615569.2615684 . ISBN  978-1-4503-2622-3. S2CID 14027025 . 
  59. ↑ Mashaghi, A.; et al. (2004). "Investigación de una red de complejos proteicos". European Physical Journal B . 41 (1): 113– 121. arXiv : cond-mat/0304207 . Bibcode : 2004EPJB...41..113M . doi : 10.1140/epjb/e2004-00301-0 . S2CID 9233932 .  
  60. ↑ Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M; Shinohara, Russell T (2019-07-01). "Caracterización del papel del conectoma estructural en la dinámica de las crisis epilépticas" . Brain . 142 ( 7): 1955– 1972. doi : 10.1093/brain/awz125 . ISSN 0006-8950 . PMC 6598625. PMID 31099821 .   
  61. ↑ Adali, Tulay; Ortega, Antonio (mayo de 2018). "Aplicaciones de la teoría de grafos [Análisis del tema]". Actas del IEEE . 106 (5): 784– 786. doi : 10.1109/JPROC.2018.2820300 . ISSN 0018-9219 . 
  62. ↑ Grandjean, Martin (2016). "Análisis de redes sociales de Twitter: mapeo de la comunidad de humanidades digitales" (PDF) . Cogent Arts & Humanities . 3 (1) 1171458. doi : 10.1080/23311983.2016.1171458 . S2CID 114999767 . 
  63. ↑ Vecchio, F (2017). "Arquitectura de "mundo pequeño" en la conectividad cerebral y el volumen del hipocampo en la enfermedad de Alzheimer: un estudio mediante teoría de grafos a partir de datos de EEG". Brain Imaging and Behavior . 11 (2): 473– 485. doi : 10.1007/s11682-016-9528-3 . PMID 26960946. S2CID 3987492 .  
  64. ↑ Vecchio, F (2013). "Conectividad de la red cerebral evaluada mediante la teoría de grafos en la demencia frontotemporal". Neurology . 81 (2): 134– 143. doi : 10.1212/WNL.0b013e31829a33f8 . PMID 23719145 . S2CID 28334693 .  
  65. ↑ Bjorken, JD; Drell, SD (1965). Campos cuánticos relativistas . Nueva York: McGraw-Hill. p. viii. 
  66. ↑ Kumar, Ankush; Kulkarni, GU (2016-01-04). "Evaluación de electrodos transparentes basados ​​en redes conductoras desde consideraciones geométricas". Journal of Applied Physics . 119 (1): 015102. Bibcode : 2016JAP...119a5102K . doi : 10.1063/1.4939280 . ISSN 0021-8979 . 
  67. ↑ Newman, Mark (2010). Redes: Una introducción (PDF) . Oxford University Press. Archivado del original (PDF) el 28 de julio de 2020. Recuperado el 30 de octubre de 2019 .
  68. ↑ Grandjean, Martin (2015). "Análisis y visualización de redes sociales: los sociogramas de Moreno revisitados" . Red rediseñada basada estrictamente en Moreno (1934), ¿Quién sobrevivirá ?
  69. ↑ Rosen, Kenneth H. (14 de junio de 2011). Matemáticas discretas y sus aplicaciones (7.ª ed.). Nueva York: McGraw-Hill. ISBN  978-0-07-338309-5.
  70. ↑ Kelly, S.; Black, Michael (2020-07-09). "graphsim: Un paquete de R para simular datos de expresión genética a partir de estructuras gráficas de vías biológicas" (PDF) . Journal of Open Source Software . 5 (51). The Open Journal: 2161. Bibcode : 2020JOSS....5.2161K . bioRxiv 10.1101/2020.03.02.972471 . doi : 10.21105/joss.02161 . ISSN 2475-9066 . S2CID 214722561 .   
  71. ↑ Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M; Shinohara, Russell T (2019-07-01). "Caracterización del papel del conectoma estructural en la dinámica de las crisis epilépticas" . Brain . 142 ( 7): 1955– 1972. doi : 10.1093/brain/awz125 . ISSN 0006-8950 . PMC 6598625. PMID 31099821 .   
  72. ↑ Kepner, Jeremy; Gilbert, John (2011). Algoritmos de grafos en el lenguaje del álgebra lineal . SIAM. p. 1171458. ISBN  978-0-898719-90-1.

Referencias

  • Lowell W. Beineke ; Bjarne Toft; y Robin J. Wilson : Hitos en la teoría de grafos: Un siglo de progreso , AMS/MAA, (SPECTRUM, v.108), ISBN 978-1-4704-6431-8 (2025).
  • Beineke, Lowell W.; Wilson, Robin J. (2009). Temas de teoría topológica de grafos . Cambridge University Press. ISBN 978-1-139-64368-9.
  • Bender, Edward A.; Williamson, S. Gill (2010). Listas, decisiones y gráficos. Con una introducción a la probabilidad .
  • Bergé, Claude (1958). Teoría de los gráficos y sus aplicaciones . París: Dunod.Edición en inglés, Wiley 1961; Methuen & Co, Nueva York 1962; edición en ruso, Moscú 1961; edición en español, México 1962; edición en rumano, Bucarest 1969; edición en chino, Shanghái 1963; segunda reimpresión de la primera edición en inglés de 1962, Dover, Nueva York 2001.
  • Biggs, Norman (1993). Teoría algebraica de grafos (2.ª  ed.). Cambridge University Press.
  • Biggs, N.; Lloyd, E.; Wilson, R. (1986). Teoría de grafos, 1736-1936 . Oxford University Press.
  • Bollobás, Béla (2013). Teoría de grafos moderna . Saltador. ISBN 978-1-4612-0619-4.
  • Bollobás, Béla; Riordan, OM (2003). Resultados matemáticos sobre grafos aleatorios libres de escala en "Handbook of Graphs and Networks" (S. Bornholdt y HG Schuster (eds)) (1.ª  ed.). Weinheim: Wiley VCH.
  • Bollobás, B. (2001). Grafos aleatorios (2.ª  ed.). Cambridge University Press. ISBN 0-521-79722-5.
  • Bondy, JA; Murty, USR (2008). Teoría de grafos . Springer. ISBN 978-1-84628-969-9.
  • Borgs, Christian; Chayes, Jennifer T.; Lovász, László ; Sós, Vera T ; Vestergombi, Katalin (2008). "Secuencias convergentes de grafos densos. I. Frecuencias de subgrafos, propiedades métricas y pruebas" . Advances in Mathematics . 219 (6): 1801– 1851. arXiv : math/0702004 . doi : 10.1016/j.aim.2008.07.008 .
  • Bounceur, Ahcene; Bezoui, Madani; Euler, Reinhardt (2019). Fronteras y envolventes de grafos euclidianos: De la teoría a la práctica . CRC Press. ISBN 978-1-351-69028-7.
  • A. Bretto, A. Faisant y F. Hennecart. Elementos de la teoría de grafos: desde los conceptos básicos hasta los desarrollos modernos. Ems Textbooks in Mathematics, 25, 2022.
  • Brightwell, Graham R. ; Scheinerman, Edward R. (1993). "Representaciones de grafos planares". SIAM Journal on Discrete Mathematics . 6 (2): 214– 229. doi : 10.1137/0406017 .
  • Cauchy, AL (1813). "Recherche sur les polyèdres - premier mémoire". Revista de la Escuela Politécnica . 9 (Cajero 16): 66–86 .
  • Cayley, A. (1875). "Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen" . Berichte der Deutschen Chemischen Gesellschaft . 8 (2): 1056– 1059. doi : 10.1002/cber.18750080252 .
  • Cayley, A. (2009) [1890]. «Sobre la teoría de las formas analíticas llamadas árboles». The Collected Mathematical Papers . Vol.  3. pp. 242–246 . doi : 10.1017/CBO9780511703690.046 . ISBN  978-0-511-70369-0.
  • Chalopin, J.; Gonçalves, D. (2009). «Todo grafo planar es el grafo de intersección de segmentos en el plano: Resumen extendido». Actas del cuadragésimo primer simposio anual de la ACM sobre Teoría de la Computación . págs. 631–638 . doi : 10.1145/1536414.1536500 . ISBN  978-1-60558-506-2.
  • Chartrand, Gary (1985). Introducción a la teoría de grafos . Dover. ISBN 0-486-24775-9.
  • Chartrand, Gary ; Jordan, Heather; Vatter, Vincent; Zhang, Ping (2024), Graphs & Digraphs (7.ª  ed.), CRC Press, pág.  73, ISBN 978-1-032-13340-9.
  • Cvetković, Dragoš M.; Rowlinson, Peter (2004). «Teoría espectral de grafos». En Beineke, Lowell W.; Wilson, Robin J. (eds.). Temas de teoría algebraica de grafos . Cambridge University Press. ISBN 978-0-521-80197-3.
  • Deo, Narsingh (1974). Teoría de grafos con aplicaciones a la ingeniería y la informática (PDF) . Englewood, Nueva Jersey: Prentice-Hall. ISBN 0-13-363473-6Archivado (PDF) del original el 17 de mayo de 2019 .
  • Di Battista, Giuseppe; Eades, Peter ; Tamassia, Roberto ; Tollis, Ioannis G. (1994). "Algoritmos para dibujar grafos: una bibliografía anotada" . Geometría computacional: teoría y aplicaciones . 4 (5): 235– 282. doi : 10.1016/0925-7721(94)00014-x .
  • Everett, Hazel; Corneil, Derek (1995). "Resultados negativos sobre la caracterización de grafos de visibilidad". Geometría Computacional: Teoría y Aplicaciones . 5 (2): 51– 63. doi : 10.1016/0925-7721(95)00021-Z . MR 1353288 . 
  • Foulds, LR (1992). Aplicaciones de la teoría de grafos . Universitext. Springer. ISBN 978-1-4612-0933-1.
  • Gardner, Martin (1992), Música fractal, hipertarjetas y más… Recreaciones matemáticas de Scientific American , WH Freeman and Company, pág.  203
  • Gibbons, Alan (1985). Teoría algorítmica de grafos . Cambridge University Press .
  • Godsil, Chris; Royle, Gordon F. (2001). Teoría algebraica de grafos . Springer. ISBN 978-1-4613-0163-9.
  • Golumbic, Martin (1980). Teoría algorítmica de grafos y grafos perfectos . Academic Press .
  • Gross, JL; Tucker, TW (2012) [1987]. Teoría topológica de grafos . Dover Publications. ISBN 978-0-486-41741-7.
  • Grünbaum, Branko (2006). "Configuraciones de puntos y líneas". El legado de Coxeter . Providence, RI: American Mathematical Society. pp. 179–225 . MR 2209028 .  
  • Hahn, Geňa; Tardif, Claude (1997). «Homomorfismos de grafos: estructura y simetría». En Hahn, Geňa; Sabidussi, Gert (eds.). Simetría de grafos: métodos algebraicos y aplicaciones . Kluwer Academic Publisher. ISBN 978-0-7923-4668-5.
  • Harary, Frank (1969). Teoría de grafos . Reading, Massachusetts: Addison-Wesley.
  • Harary, Frank; Palmer, Edgar M. (1973). Enumeración gráfica . Nueva York, Nueva York: Academic Press.
  • Kaveh, A. (2013). Análisis óptimo de estructuras mediante conceptos de simetría y regularidad . Springer. ISBN 978-3-7091-1565-7.
  • Kepner, Jeremy; Gilbert, John (2011). Algoritmos de grafos en el lenguaje del álgebra lineal . Filadelfia, Pensilvania: SIAM. ISBN 978-0-89871-990-1.
  • L'Huillier, SAJ (1812–1813). "Mémoire sur la polyèdrométrie". Anales de Matemáticas . 3 : 169-189 .
  • Lovász, László (2006). "Teoría del gráfico menor" . Boletín de la Sociedad Matemática Estadounidense . 43 (1): 75– 86. doi : 10.1090/S0273-0979-05-01088-8 .
  • Mahadev, NVR; Peled, Uri N. (1995). Gráficos de umbral y temas relacionados . North-Holland .
  • Malitz, Seth; Papakostas, Achilleas (1994). "Sobre la resolución angular de grafos planares". SIAM Journal on Discrete Mathematics . 7 (2): 172– 183. doi : 10.1137/S0895480193242931 . MR 1271989 . 
  • McDiarmid, Colin; Johnson, Theodore; Stone, Harold S. (1997). "Sobre cómo encontrar un árbol de expansión mínima en una red con pesos aleatorios" ( PDF) . Random Structures & Algorithms . 10 ( 1–2 ): 187–204 . doi : 10.1002/(SICI)1098-2418(199701/03)10:1/2 < 187 ::AID-RSA10 > 3.3.CO ; 2- Y.MR1611522 . 
  • McKee, Terry A.; McMorris, FR (1999). Temas en teoría de grafos de intersección . Sociedad de Matemáticas Industriales y Aplicadas . ISBN 978-0-89871-430-2.
  • Mohar, Bojan ; Thomassen, Carsten (2001). Grafos en superficies . Johns Hopkins University Press. ISBN 978-0-8018-6689-0OCLC 45102952​​ 
  • Morin, Pat (22 de marzo de 2014). "Capítulo 7: Árboles de búsqueda binaria aleatorios". Estructuras de datos abiertas (en pseudocódigo) (PDF) (  ed. 0,1 GB). págs. 145–164 . 
  • Newman, Mark (2010). Redes: Una introducción . Oxford University Press.
  • Ore, Øystein (1962). Teoría de grafos . Sociedad Matemática Americana.
  • Pach, János (2018). "Teoría geométrica de grafos". En Toth, Csaba D.; O'Rourke, Joseph; Goodman, Jacob E. (eds.). Manual de geometría discreta y computacional (3.ª  ed.). CRC Press.
  • Pach, János ; Sharir, Micha (2009). "5.5 Resolución angular y pendientes". Geometría combinatoria y sus aplicaciones algorítmicas: las conferencias de Alcalá . Mathematical Surveys and Monographs. Vol.  152. American Mathematical Society . pp. 126–127 . 
  • Persinger, CA (1966). "Subconjuntos denorte{\displaystyle n}-libros enmi3{\displaystyle E^{3}}" . Pacific Journal of Mathematics . 18 : 169– 173. doi : 10.2140/pjm.1966.18.169 . MR 0195077 . 
  • Richeson, D. (2008). La gema de Euler: La fórmula del poliedro y el nacimiento de la topología . Princeton University Press.
  • Sedgewick, Robert ; Flajolet, Philippe (2013). «Capítulo 6: Árboles». Introducción al análisis de algoritmos (2.ª  ed.). Addison-Wesley. ISBN 9780133373486.
  • «El Premio George Polya». Mirando hacia atrás, mirando hacia adelante: una historia de SIAM (PDF) . Sociedad de Matemáticas Industriales y Aplicadas . 2002. pág.  26. Archivado del original (PDF) el 5 de marzo de 2016. Consultado el 14 de marzo de 2016 .
  • Sylvester, James Joseph (1878). "Química y álgebra" . Nature . 17 (432): 284. Bibcode : 1878Natur..17..284S . doi : 10.1038/017284a0 .
  • Thurston, William (marzo de 2002). «§13.6, Teorema de Andreev y generalizaciones, y §13.7, Construcción de patrones de círculos». Geometría y topología de 3-variedades . Publicaciones MSRI. págs. 330–346 . Versión electrónica 1.1 . Consultado el 9 de diciembre de 2025 . 
  • Tutte, WT (2001). Teoría de grafos . Cambridge University Press. ISBN 978-0-521-79489-3.
  • Wilson, David Bruce (1996). «Generación de árboles de expansión aleatorios más rápidamente que el tiempo de cobertura». Actas del Vigésimo Octavo Simposio Anual de la ACM sobre Teoría de la Computación (STOC 1996) . págs. 296–303 . doi : 10.1145/237814.237880 . ISBN  0-89791-785-5MR 1427525 .​ 
  • Zhao, Yufei (2023). Teoría de grafos y combinatoria aditiva: explorando la estructura y la aleatoriedad . Cambridge University Press. ISBN 978-1-009-31094-9.
  • Ziegler, Günter M. (2007). "Politopos convexos: construcciones extremales yF{\displaystyle f}-formas vectoriales. Sección 1.3: El teorema de Steinitz mediante empaquetamientos de círculos". En Miller, Ezra; Reiner, Victor; Sturmfels, Bernd (eds.). Combinatoria geométrica . Serie de matemáticas IAS/Park City. Vol.  13. Sociedad Matemática Americana . págs. 628–642 . ISBN  978-0-8218-3736-8.
  • "Teoría de grafos" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
  • Tutorial de teoría de grafos archivado el 16/01/2012 en Wayback Machine.
  • Una base de datos consultable de pequeños grafos conectados.
  • House of Graphs : base de datos de gráficos con función de búsqueda basada en dibujos.
  • Galería de imágenes: gráficos en Wayback Machine (archivados el 6 de febrero de 2006)
  • Lista concisa y comentada de recursos sobre teoría de grafos para investigadores
  • rocs — un IDE de teoría de grafos
  • La vida social de los enrutadores : artículo no técnico que analiza gráficos de personas y computadoras.
  • Software de teoría de grafos : herramientas para enseñar y aprender teoría de grafos.
  • Libros en línea y recursos bibliotecarios en su biblioteca y en otras bibliotecas sobre teoría de grafos.
  • Lista de algoritmos de grafos archivada el 13 de julio de 2019 en Wayback Machine con referencias y enlaces a implementaciones de bibliotecas de grafos.

Libros de texto en línea

  • Hartmann, Alexander K.; Weigt, Martin (2005). «Introducción a los grafos». Transiciones de fase en problemas de optimización combinatoria: fundamentos, algoritmos y mecánica estadística . Wiley. pp. 25–66 . arXiv : cond-mat/0602129 . doi : 10.1002/3527606734.ch3 . ISBN  978-3-527-60673-3.
  • Digrafos: Teoría, algoritmos y aplicaciones 2007 por Jorgen Bang-Jensen y Gregory Gutin
  • Teoría de grafos, por Reinhard Diestel
Lecturas relacionadas
6 articulos
MatemáticasMatemáticasLas matemáticas son un campo de estudio que descubre y organiza métodos, teorías y teoremas que se desarrollan y prueban para las necesidades de la...Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...Gráfica (matemática discreta)Gráfica (matemática discreta)En matemáticas discretas , particularmente en teoría de grafos , un grafo es una estructura que consiste en un conjunto de objetos donde algunos pa...Estructura matemáticaEstructura matemáticaEn matemáticas, una estructura en un conjunto (o en algunos conjuntos) se refiere a proporcionarle (o proporcionarles) ciertas características adic...Vertex (graph theory)Vertex (graph theory)In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are form...Glosario de teoría de grafosGlosario de teoría de grafosEste es un glosario de teoría de grafos . La teoría de grafos es el estudio de los grafos , sistemas de nodos o vértices conectados en pares por lí...