Teoría de grafos

Área de matemáticas discretas

Un dibujo de un gráfico con 6 vértices y 7 aristas.

En matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares entre objetos. Un grafo en este contexto está formado por vértices (también llamados nodos o puntos ) que están conectados por aristas (también llamadas arcos , enlaces o líneas ). Se hace una distinción 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 .

Definiciones

Las definiciones en teoría de grafos varían. A continuación se presentan algunas de las formas más básicas de definir grafos y estructuras matemáticas relacionadas .

Gráfico

Un gráfico con tres vértices y tres aristas.

En un sentido restringido pero muy común del término, ^{[1] [2]} un gráfico es un par ordenado que comprende: ${\displaystyle G=(V,E)}$

• ${\displaystyle V}$, un conjunto de vértices (también llamados nodos o puntos );
• ${\displaystyle E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}}$, un conjunto de aristas (también llamadas enlaces o líneas ), que son pares de vértices no ordenados (es decir, una arista está asociada a dos vértices distintos).

Para evitar ambigüedades, este tipo de objeto puede llamarse precisamente un gráfico simple no dirigido .

En la arista , los vértices y se denominan puntos finales de la arista. Se dice que la arista une a y y que es incidente sobre y sobre . Un vértice puede existir en un grafo y no pertenecer a una arista. Según esta definición, no se permiten aristas múltiples , en las que dos o más aristas conectan los mismos vértices. ${\displaystyle \{x,y\}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

Ejemplo de grafo simple no dirigido con 3 vértices, 3 aristas y 4 bucles.

Ejemplos de búsqueda del grado de vértices.

En un sentido más general del término que permite múltiples aristas, ^{[3] [4]} un gráfico es una tripleta ordenada que comprende: ${\displaystyle G=(V,E,\phi )}$

• ${\displaystyle V}$, un conjunto de vértices (también llamados nodos o puntos );
• ${\displaystyle E}$, un conjunto de aristas (también llamadas enlaces o líneas );
• ${\displaystyle \phi :E\to \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}}$, una función de incidencia que asigna cada arista a un par de vértices no ordenados (es decir, una arista está asociada con dos vértices distintos).

Para evitar ambigüedades, este tipo de objeto puede llamarse precisamente un multigrafo no dirigido .

Un bucle es una arista que une un vértice consigo mismo. Los grafos definidos en las dos definiciones anteriores no pueden tener bucles, porque un bucle que une un vértice consigo mismo es la arista (para un grafo simple no dirigido) o es incidente en (para un multigrafo no dirigido) que no está en . Para permitir bucles, las definiciones deben expandirse. Para grafos simples no dirigidos, la definición de debe modificarse a . Para multigrafos no dirigidos, la definición de debe modificarse a . Para evitar ambigüedades, estos tipos de objetos pueden llamarse grafo simple no dirigido que permite bucles y multigrafo no dirigido que permite bucles (a veces también pseudografo no dirigido ), respectivamente. ${\displaystyle x}$ ${\displaystyle \{x,x\}=\{x\}}$ ${\displaystyle \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}}$ ${\displaystyle E}$ ${\displaystyle E\subseteq \{\{x,y\}\mid x,y\in V\}}$ ${\displaystyle \phi }$ ${\displaystyle \phi :E\to \{\{x,y\}\mid x,y\in V\}}$

${\displaystyle V}$y se toman generalmente como finitos, y muchos de los resultados bien conocidos no son verdaderos (o son más bien diferentes) para grafos infinitos porque muchos de los argumentos fallan en el caso infinito . Además, a menudo se supone que no está vacío, pero se permite que sea el conjunto vacío. El orden de un grafo es , su número de vértices. El tamaño de un grafo es , su número de aristas. El grado o valencia de un vértice es el número de aristas que le inciden, donde un bucle se cuenta dos veces. El grado de un grafo es el máximo de los grados de sus vértices. ${\displaystyle E}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle |V|}$ ${\displaystyle |E|}$

En un grafo simple no dirigido de orden n , el grado máximo de cada vértice es n − 1 y el tamaño máximo del grafo es ⁠n ( n - 1)/2⁠ .

Las aristas de un grafo simple no dirigido que permite bucles inducen una relación homogénea simétrica en los vértices de que se denomina relación de adyacencia de . Específicamente, para cada arista , se dice que sus puntos finales y son adyacentes entre sí, lo que se denota como . ${\displaystyle G}$ ${\displaystyle \sim }$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\sim y}$

Grafo dirigido

Un gráfico dirigido con tres vértices y cuatro aristas dirigidas (la flecha doble representa una arista en cada dirección).

Un gráfico dirigido o dígrafo es un gráfico en el que los bordes tienen orientaciones.

En un sentido restringido pero muy común del término, ^[5] un gráfico dirigido es un par ordenado que comprende: ${\displaystyle G=(V,E)}$

• ${\displaystyle V}$, un conjunto de vértices (también llamados nodos o puntos );
• ${\displaystyle E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}}$, un conjunto de aristas (también llamadas aristas dirigidas , enlaces dirigidos , líneas dirigidas , flechas o arcos ) que son pares ordenados de vértices (es decir, una arista está asociada a dos vértices distintos).

Para evitar ambigüedades, este tipo de objeto puede llamarse precisamente grafo simple dirigido . En teoría de conjuntos y teoría de grafos, denota el conjunto de n - tuplas de elementos, es decir, secuencias ordenadas de elementos que no son necesariamente distintos. ${\displaystyle V^{n}}$ ${\displaystyle V,}$ ${\displaystyle n}$

En la arista dirigida desde a , los vértices y se denominan puntos finales de la arista, cola de la arista y cabeza de la arista . Se dice que la arista une a y e incide sobre y sobre . Un vértice puede existir en un grafo y no pertenecer a una arista. La arista se denomina arista invertida de . Las aristas múltiples , no permitidas según la definición anterior, son dos o más aristas con la misma cola y la misma cabeza. ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (y,x)}$ ${\displaystyle (x,y)}$

En un sentido más general del término que permite múltiples aristas, ^[5] un gráfico dirigido es un triple ordenado que comprende: ${\displaystyle G=(V,E,\phi )}$

• ${\displaystyle V}$, un conjunto de vértices (también llamados nodos o puntos );
• ${\displaystyle E}$, un conjunto de aristas (también llamadas aristas dirigidas , enlaces dirigidos , líneas dirigidas , flechas o arcos );
• ${\displaystyle \phi :E\to \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}}$, una función de incidencia que asigna cada arista a un par ordenado de vértices (es decir, una arista está asociada con dos vértices distintos).

Para evitar ambigüedades, este tipo de objeto puede llamarse precisamente un multigrafo dirigido .

Un bucle es una arista que une un vértice consigo mismo. Los grafos dirigidos, tal como se definen en las dos definiciones anteriores, no pueden tener bucles, porque un bucle que une un vértice consigo mismo es la arista (para un grafo simple dirigido) o es incidente en (para un multigrafo dirigido) que no está en . Por lo tanto, para permitir bucles, las definiciones deben expandirse. Para grafos simples dirigidos, la definición de debe modificarse a . Para multigrafos dirigidos, la definición de debe modificarse a . Para evitar ambigüedades, estos tipos de objetos pueden llamarse precisamente un grafo simple dirigido que permite bucles y un multigrafo dirigido que permite bucles (o un quiver ) respectivamente. ${\displaystyle x}$ ${\displaystyle (x,x)}$ ${\displaystyle \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}}$ ${\displaystyle E}$ ${\displaystyle E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\right\}}$ ${\displaystyle \phi }$ ${\displaystyle \phi :E\to \left\{(x,y)\mid (x,y)\in V^{2}\right\}}$

Las aristas de un grafo simple dirigido que permite bucles es una relación homogénea ~ en los vértices de que se llama relación de adyacencia de . Específicamente, para cada arista , sus puntos finales y se dice que son adyacentes entre sí, lo que se denota ~ . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

Aplicaciones

El gráfico de red formado por los editores de Wikipedia (aristas) que contribuyeron a diferentes versiones de idioma de Wikipedia (vértices) durante un mes en el verano de 2013. ^[6]

Los grafos se pueden utilizar para modelar muchos tipos de relaciones y procesos en sistemas físicos, biológicos, ^{[7] [8] sociales y de información. [9]} Muchos problemas prácticos se pueden representar mediante grafos. Haciendo hincapié en su aplicación a sistemas del mundo real, el término red a veces se define para significar un grafo en el que los atributos (por ejemplo, nombres) están asociados con los vértices y los bordes, y el tema que expresa y entiende los sistemas del mundo real como una red se llama ciencia de redes .

Ciencias de la Computación

En informática , las estructuras vinculadas causales y no causales son grafos que se utilizan para representar redes de comunicación, organización de datos, dispositivos computacionales, el flujo de computación, etc. Por ejemplo, la estructura de enlaces de un sitio web se puede representar mediante un grafo dirigido, en el que los vértices representan páginas web y los bordes dirigidos representan enlaces de una página a otra. Se puede adoptar un enfoque similar para los problemas en las redes sociales, ^[10] los viajes, la biología, el diseño de chips de computadora, el mapeo de la progresión de enfermedades neurodegenerativas, ^{[11] [12]} 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 se representa mediante sistemas de reescritura de grafos . Como complemento a los sistemas de transformación de grafos que se centran en la manipulación en memoria basada en reglas de grafos, se encuentran las bases de datos de grafos orientadas al almacenamiento y consulta persistentes y seguros para transacciones de datos estructurados en grafos .

Lingüística

Los métodos de teoría de grafos, en varias 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 compositiva siguen estructuras basadas en árboles, cuyo poder expresivo reside en el principio de composicionalidad , modelado en un grafo jerárquico. Los enfoques más contemporáneos, como la gramática de estructura de frase impulsada por la cabeza, modelan la sintaxis del lenguaje natural utilizando estructuras de características tipificadas , que son grafos acíclicos dirigidos . Dentro de la semántica léxica , especialmente en su aplicación 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 . Aún 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 "Net", 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 complicadas se puede estudiar cuantitativamente mediante la recopilación de estadísticas sobre propiedades grafo-teóricas relacionadas con la topología de los átomos. Además, "los gráficos de Feynman y las reglas de cálculo resumen la teoría cuántica de campos en una forma en estrecho contacto con los números experimentales que uno quiere entender". ^[13] En química, un grafo constituye un modelo natural para una molécula, donde los vértices representan átomos y los bordes enlaces . Este enfoque se utiliza especialmente en el procesamiento informático de estructuras moleculares, que van 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 varios procesos cognitivos, donde los vértices representan diferentes áreas del cerebro y los bordes representan las conexiones entre esas áreas. La teoría de grafos juega un papel importante en el modelado eléctrico de redes eléctricas, aquí, los pesos se asocian con la resistencia de los segmentos de cable para obtener propiedades eléctricas de las estructuras de red. ^[14] Los grafos también se utilizan para representar los canales a microescala de medios porosos , en los que los vértices representan los poros y los bordes representan los canales más pequeños que conectan los poros. La teoría de grafos químicos utiliza el grafo molecular como un medio para modelar moléculas. Los grafos y las redes son modelos excelentes para estudiar y comprender las transiciones de fase y los fenómenos críticos. La eliminación de nodos o bordes conduce a una transición crítica donde la red se divide en pequeños grupos que se estudian como una transición de fase. Esta ruptura se estudia a través de la teoría de la percolación . ^[15]

Ciencias sociales

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

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 , en particular mediante el uso de software de análisis de redes sociales . Bajo el paraguas de las redes sociales hay muchos tipos diferentes de grafos. ^[17] Los grafos de amistad y conocimiento 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

De la misma manera, la teoría de grafos es útil en biología y en iniciativas de conservación, donde un vértice puede representar regiones donde existen (o habitan) ciertas especies y los bordes representan rutas de migración o movimiento entre las regiones. Esta información es importante cuando se observan patrones de reproducción o se rastrea la propagación de enfermedades, parásitos o cómo los cambios en el movimiento pueden afectar a otras especies.

Los gráficos 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 gráficos se utilizan a menudo para "agrupar" células en tipos celulares en el análisis del transcriptoma de una sola célula . Otro uso es modelar genes o proteínas en una vía y estudiar las relaciones entre ellos, como las vías metabólicas y las redes reguladoras de genes. ^[18] Los árboles evolutivos, las redes ecológicas y la agrupación jerárquica de patrones de expresión genética también se representan como estructuras gráficas.

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

Matemáticas

En matemáticas, los grafos son útiles en geometría y en ciertas partes de la topología, como la teoría de nudos . La teoría de grafos algebraicos tiene vínculos estrechos con la teoría de grupos . La teoría de grafos algebraicos se ha aplicado a muchas áreas, incluidos los sistemas dinámicos y la complejidad.

Otros temas

Una estructura gráfica se puede ampliar asignando un peso a cada borde del gráfico. Los gráficos con pesos, o gráficos ponderados , se utilizan para representar estructuras en las que las conexiones por pares tienen algunos valores numéricos. Por ejemplo, si un gráfico representa una red de carreteras, los pesos podrían representar la longitud de cada carretera. Puede haber varios pesos asociados con cada borde, incluida la distancia (como en el ejemplo anterior), el tiempo de viaje o el costo monetario. Dichos gráficos ponderados se utilizan comúnmente para programar GPS y motores de búsqueda de planificación de viajes que comparan tiempos y costos de vuelo.

Historia

El problema del puente de Königsberg

El artículo escrito por Leonhard Euler sobre los Siete Puentes de Königsberg y publicado en 1736 se considera el primer artículo en la historia de la teoría de grafos. ^[20] Este artículo, así como el escrito por Vandermonde sobre el problema del caballo , continuaron con el análisis situs iniciado por Leibniz . La fórmula de Euler que relaciona el número de aristas, vértices y caras de un poliedro convexo fue estudiada y generalizada por Cauchy ^[21] y L'Huilier ^[22] y representa el comienzo de la rama de las matemáticas conocida como topología .

Más de un siglo después del artículo de Euler sobre los puentes de Königsberg y mientras Listing introducía el concepto de topología, Cayley se vio impulsado por un interés en formas analíticas particulares que surgían del cálculo diferencial para estudiar una clase particular de grafos, los árboles . ^[23] Este estudio tuvo muchas implicaciones para la química teórica . Las técnicas que utilizó se refieren principalmente a 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 De Bruijn en 1959. Cayley vinculó sus resultados sobre los árboles con estudios contemporáneos de composición química. ^[24] La fusión de ideas de las matemáticas con las de la química inició lo que se ha convertido en parte de la terminología estándar de la teoría de grafos.

En particular, el término "grafo" fue introducido por Sylvester en un artículo publicado en 1878 en Nature , donde establece una analogía entre "invariantes cuánticos" y "covariantes" del álgebra y los diagramas moleculares: ^[25]

"[…] Todo invariante y covariante se vuelve así expresable mediante un gráfico exactamente idéntico a un diagrama o quimicograma de Kekulé . […] Doy una regla para la multiplicación geométrica de gráficos, es decir , para construir un gráfico a partir del producto de invariantes o covariantes cuyos gráficos separados están dados. […]" (cursiva como en el original).

El primer libro de texto sobre teoría de grafos fue escrito por Dénes Kőnig y publicado en 1936. ^[26] Otro libro de Frank Harary , publicado en 1969, fue "considerado en todo el mundo como el libro de texto definitivo sobre el tema", ^[27] y permitió que matemáticos, químicos, ingenieros eléctricos y científicos sociales hablaran entre sí. Harary donó todas las regalías para financiar el Premio Pólya . ^[28]

Uno de los problemas más famosos y estimulantes en 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 que tengan un borde común tengan colores diferentes?" Este problema fue planteado por primera vez por Francis Guthrie en 1852 y su primer registro escrito está en una carta de De Morgan dirigida a Hamilton el mismo año. Se han propuesto muchas demostraciones incorrectas, incluidas las de Cayley, Kempe y otros. El estudio y la generalización de este problema por Tait , Heawood , 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 , particularmente estudiados por Petersen y Kőnig . Los trabajos de Ramsey sobre coloraciones y más especialmente los resultados obtenidos por Turán en 1941 estuvieron en el origen de otra rama de la teoría de grafos, la teoría de grafos extremales .

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. ^[29] Una prueba asistida por computadora producida en 1976 por Kenneth Appel y Wolfgang Haken hace un uso fundamental de la noción de "descarga" desarrollada por Heesch. ^{[30] [31] La prueba implicaba verificar las propiedades de 1.936 configuraciones por computadora, y no fue completamente aceptada en ese momento debido a su complejidad. Veinte años después,} Robertson , Seymour , Sanders y Thomas dieron una prueba más simple que consideraba solo 633 configuraciones . ^[32]

El desarrollo autónomo de la topología a partir de 1860 y 1930 fertilizó la teoría de grafos a través de los trabajos de Jordan , Kuratowski y Whitney . Otro factor importante del 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 tal 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 .

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

Representación

Un grafo es una abstracción de relaciones que surgen en la naturaleza; por lo tanto, no se puede asociar a una determinada representación. La forma en que se representa depende del grado de conveniencia que dicha representación proporcione para una determinada aplicación. Las representaciones más comunes son la visual, en la que, por lo general, se dibujan 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 dentro del grafo.

Visual: Dibujo gráfico

Los gráficos se representan visualmente dibujando un punto o círculo para cada vértice y dibujando una línea entre dos vértices si están conectados por una arista. Si el gráfico es dirigido, la dirección se indica dibujando una flecha. Si el gráfico es ponderado, el peso se agrega a la flecha.

No debe confundirse el dibujo de un gráfico con el gráfico en sí (la estructura abstracta, no visual), ya que existen varias formas de estructurar el dibujo del gráfico. Lo único que importa es qué vértices están conectados a otros por cuántos bordes y no la disposición exacta. En la práctica, a menudo es difícil decidir si dos dibujos representan el mismo gráfico. Según el dominio del problema, algunas disposiciones pueden ser más adecuadas y más fáciles de entender que otras.

El trabajo pionero de WT Tutte fue muy influyente en el tema del dibujo de grafos. Entre otros logros, introdujo el uso de métodos algebraicos lineales para obtener grafos.

También se puede decir que el dibujo de grafos abarca problemas que tratan 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 plano , 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 gráfico lejos de los vértices y los bordes, incluidos los empaquetamientos circulares , el gráfico de intersección y otras visualizaciones de la matriz de adyacencia .

Tabular: estructuras de datos de gráficos

La representación tabular se presta bien a las aplicaciones computacionales. Existen diferentes formas de almacenar gráficos en un sistema informático. La estructura de datos utilizada depende tanto de la estructura del gráfico como del algoritmo utilizado 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 gráficos dispersos, ya que tienen menores requisitos de memoria. Las estructuras de matriz , por otro lado, proporcionan un acceso más rápido para algunas aplicaciones, pero pueden consumir enormes cantidades de memoria. Las implementaciones de estructuras de matriz dispersa que son eficientes en las arquitecturas de computadoras paralelas modernas son un objeto de investigación actual. ^[33]

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 distancia , al igual que la matriz de adyacencia, tiene sus filas y columnas indexadas por vértices, pero en lugar de contener un 0 o un 1 en cada celda, contiene la longitud de un camino más corto entre dos vértices.

Problemas

Enumeración

Existe una gran cantidad de literatura sobre la enumeración gráfica : el problema de contar gráficos que cumplen condiciones específicas. Parte de este trabajo se encuentra en Harary y Palmer (1973).

Subgrafos, subgrafos inducidos y menores

Un problema común, llamado problema de isomorfismo de subgrafos , es 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 tiene la propiedad si y solo si todos los subgrafos también la tienen. Desafortunadamente, encontrar subgrafos máximos de un cierto tipo es a menudo un problema NP-completo . Por ejemplo:

• Encontrar el subgrafo completo más grande se llama problema de la camarilla (NP-completo).

Un caso especial de isomorfismo de subgrafos es el problema de isomorfismo de grafos . En él se plantea la cuestión de si dos grafos son isomorfos. No se sabe si este problema es NP-completo ni si se puede resolver en tiempo polinómico.

Un problema similar es el de 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 los subgrafos inducidos también la tienen. Encontrar subgrafos inducidos máximos de un cierto tipo también suele ser NP-completo. Por ejemplo:

• Encontrar el subgrafo inducido sin aristas más grande o conjunto independiente se denomina problema del conjunto independiente (NP-completo).

Otro problema similar, el problema de la 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 tomando un subgrafo y contrayendo 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 los menores también la tienen. Por ejemplo, el teorema de Wagner establece:

• Un grafo es planar si no contiene como menor ni al grafo bipartito completo K _3,3 (véase el problema de las tres cabañas ) ni al grafo completo K ₅ .

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 del grafo como la planaridad . Por ejemplo, el teorema de Kuratowski establece:

• Un grafo es planar si no contiene como subdivisión ni el grafo bipartito completo K _3,3 ni el grafo completo K ₅ .

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

• Todo gráfico conexo de 5 vértices que no sea plano contiene una subdivisión del gráfico completo de 5 vértices K ₅ .

Otra clase de problemas tiene que ver con el grado en que las distintas especies y generalizaciones de grafos están determinadas por sus subgrafos sin puntos . Por ejemplo:

• La conjetura de la reconstrucción

Coloración de gráficos

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

• Teorema de los cuatro colores
• Teorema del grafo perfecto fuerte
• Conjetura de Erdős-Faber-Lovász
• Conjetura de coloración total , también llamada conjetura de Behzad (sin resolver)
• Conjetura sobre la coloración de listas (sin resolver)
• Conjetura de Hadwiger (teoría de grafos) (sin resolver)

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 una mayor cantidad de información) son subsumidos por aquellos que son más generales. Las operaciones entre grafos incluyen la evaluación de la dirección de una relación de subsunción entre dos grafos, si la hay, y el cálculo de la unificación de grafos. La unificación de dos grafos de argumentos se define como el grafo más general (o el cálculo del mismo) que es consistente con (es decir, contiene toda la información en) las entradas, si existe tal grafo; se conocen algoritmos de unificación eficientes.

Para los marcos de restricciones que son estrictamente compositivos , la unificación de grafos es la función de satisfacibilidad y combinación suficiente. Las aplicaciones más conocidas incluyen la demostración automática de teoremas y el modelado de la elaboración de la estructura lingüística .

Problemas de ruta

• Problema de la trayectoria hamiltoniana
• Árbol de expansión mínimo
• Problema de inspección de ruta (también llamado el "problema del cartero chino")
• Los siete puentes de Königsberg
• Problema del camino más corto
• Árbol de Steiner
• Problema de las tres cabañas
• Problema del viajante de comercio (NP-hard)

Flujo de red

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

• Teorema de corte mínimo de flujo máximo

Problemas de visibilidad

• Problema con los guardias del museo

Problemas de cobertura

Los problemas de cobertura en gráficos pueden referirse a varios problemas de cobertura de conjuntos en subconjuntos de vértices/subgráficos.

• El problema del conjunto dominante es el 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 de cobertura de conjunto original, también llamado conjunto impactante, 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 sea necesario acompañando a las aristas de cada parte de la partición), plantea una amplia variedad de cuestiones. 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 los que se debe descomponer un grafo dado, por ejemplo, una familia de ciclos, o descomponer un grafo completo K _n en n − 1 árboles especificados que tienen, respectivamente, 1, 2, 3, ..., n − 1 aristas.

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

• Arboricidad , una descomposición en el menor número posible de bosques.
• Ciclo de doble cobertura , una descomposición en una colección de ciclos que cubren cada arista exactamente dos veces
• Coloración de bordes , una descomposición en la menor cantidad posible de coincidencias
• Factorización de gráficos , una descomposición de un gráfico regular en subgráficos regulares de grados dados.

Clases de gráficos

Muchos problemas implican la caracterización de los miembros de varias clases de grafos. A continuación se muestran algunos ejemplos de dichas preguntas:

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

Véase también

• Galería de gráficos con nombre
• Glosario de teoría de grafos
• Lista de temas de teoría de grafos
• Lista de problemas no resueltos en teoría de grafos
• Publicaciones en teoría de grafos

Temas relacionados

• Teoría de grafos algebraicos
• Gráfico de citas
• Gráfico conceptual
• Estructura de datos
• Estructura de datos de conjunto disjunto
• Evolución de dos fases
• Gráfico entitativo
• Gráfica existencial
• Álgebra gráfica
• Automorfismo de grafos
• Coloración de gráficos
• Base de datos de gráficos
• Estructura de datos de gráficos
• Dibujo gráfico
• Ecuación gráfica
• Reescritura de gráficos
• Problema del sándwich gráfico
• Propiedad gráfica
• Gráfica de intersección
• Gira del caballero
• Gráfico lógico
• Bucle
• Teoría de redes
• Gráfico nulo
• Problemas de movimiento de guijarros
• Teoría de la percolación
• Gráfico perfecto
• Gráfico cuántico
• Gráficos regulares aleatorios
• Redes semánticas
• Teoría de grafos espectrales
• Gráficos fuertemente regulares
• Gráficos simétricos
• Reducción transitiva
• Estructura de datos de árbol

Algoritmos

• Algoritmo de Bellman-Ford
• Algoritmo de Borůvka
• Búsqueda en amplitud
• Búsqueda en profundidad
• Algoritmo de Dijkstra
• Algoritmo de Edmonds-Karp
• Algoritmo de Floyd-Warshall
• Algoritmo de Ford-Fulkerson
• Algoritmo de Hopcroft-Karp
• Algoritmo húngaro
• Algoritmo de Kosaraju
• Algoritmo de Kruskal
• Algoritmo del vecino más próximo
• Algoritmo de red simplex
• Algoritmos de prueba de planaridad
• Algoritmo de Prim
• Algoritmo de flujo máximo push-reetiquetado
• Algoritmo de componentes fuertemente conectados de Tarjan
• Ordenamiento topológico

Subáreas

• Teoría de grafos algebraicos
• Teoría de grafos geométricos
• Teoría de grafos extremos
• Teoría de grafos probabilísticos
• Teoría de grafos topológicos

Áreas relacionadas con las matemáticas

• Combinatoria
• Teoría de grupos
• Teoría de nudos
• Teoría de Ramsey

Generalizaciones

• Hipergrafo
• Complejo simplicial abstracto

Teóricos de grafos destacados

• Alón, Noga
• Berge, Claude
• Bollobás, Bela
• Bondy, Adrián John
• Brightwell, Graham
• Chudnovski, María
• Chung, ventilador
• Dirac, Gabriel Andrew
• Dijkstra, Edsger W.
• Erdøs, Paul
• Euler, Leonhard
• Faudree, Ralph
• Fleischner, Herbert
• Golumbic, Martín
• Graham, Ronald
• Harary, Frank
• Heawood, Percy John
• Kotzig, Antón
• Rey, Dénes
• Lovász, Laszló
• Murty, URSS
• Nesetril, Jaroslav
• Renyi, Alfred
• Ringel, Gerhard
• Robertson, Neil
• Seymour, Pablo
• Sudakov, Benny
• Szemerédi, Fin
• Thomas, Robin
• Thomassen, Carsten
• Turán, Pal
• Todo, WT
• Whitney, Hassler

Notas

1. Bender y Williamson 2010, pág. 148.
2. Véase, por ejemplo, Iyanaga y Kawada, 69 J , pág. 234 o Biggs, pág. 4.
3. Bender y Williamson 2010, pág. 149.
4. Véase, por ejemplo, Graham et al., pág. 5.
5. Bender y Williamson 2010, pág. 161.
6. Hale, Scott A. (2014). "Multilingüismo 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 . 9781450326223. Número de identificación del sujeto  14027025.
7. Mashaghi, A.; et al. (2004). "Investigación de una red compleja de proteínas". European Physical Journal B . 41 (1): 113–121. arXiv : cond-mat/0304207 . Código Bibliográfico :2004EPJB...41..113M. doi :10.1140/epjb/e2004-00301-0. S2CID  9233932.
8. Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M; Shinohara, Russell T (1 de julio de 2019). "Caracterización del papel del conectoma estructural en la dinámica de las convulsiones". Cerebro . 142 (7): 1955–1972. doi :10.1093/brain/awz125. ISSN  0006-8950. PMC 6598625 . PMID  31099821. 
9. Adali, Tulay; Ortega, Antonio (mayo de 2018). "Aplicaciones de la teoría de grafos [Explorando el tema]" . Actas del IEEE . 106 (5): 784–786. doi :10.1109/JPROC.2018.2820300. ISSN  0018-9219.
10. Grandjean, Martin (2016). "Un análisis de la red social de Twitter: mapeo de la comunidad de humanidades digitales" (PDF) . Cogent Arts & Humanities . 3 (1): 1171458. doi : 10.1080/23311983.2016.1171458 . S2CID  114999767.
11. Vecchio, F (2017). "Arquitectura de "mundo pequeño" en la conectividad cerebral y el volumen del hipocampo en la enfermedad de Alzheimer: un estudio a través de la 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.
12. Vecchio, F (2013). "Conectividad de la red cerebral evaluada mediante la teoría de grafos en la demencia frontotemporal". Neurología . 81 (2): 134–143. doi :10.1212/WNL.0b013e31829a33f8. PMID  23719145. S2CID  28334693.
13. Bjorken, JD; Drell, SD (1965). Campos cuánticos relativistas . Nueva York: McGraw-Hill. pág. viii.
14. Kumar, Ankush; Kulkarni, GU (4 de enero de 2016). "Evaluación de electrodos transparentes basados ​​en redes conductoras a partir de consideraciones geométricas". Journal of Applied Physics . 119 (1): 015102. Bibcode :2016JAP...119a5102K. doi :10.1063/1.4939280. ISSN  0021-8979.
15. Newman, Mark (2010). Redes: una introducción (PDF) . Oxford University Press. Archivado desde el original (PDF) el 28 de julio de 2020. Consultado el 30 de octubre de 2019 .
16. Grandjean, Martin (2015). "Análisis y visualización de redes sociales: los sociogramas de Moreno revisitados". Red rediseñada estrictamente basada en Moreno (1934), Who Shall Survive .
17. 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.
18. Kelly, S.; Black, Michael (9 de julio de 2020). "graphsim: Un paquete R para simular datos de expresión génica 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. 
19. Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M; Shinohara, Russell T (1 de julio de 2019). "Caracterización del papel del conectoma estructural en la dinámica de las convulsiones". Cerebro . 142 (7): 1955–1972. doi :10.1093/brain/awz125. ISSN  0006-8950. PMC 6598625 . PMID  31099821. 
20. Biggs, N.; Lloyd, E.; Wilson, R. (1986), Teoría de grafos, 1736-1936 , Oxford University Press
21. Cauchy, AL (1813), "Recherche sur les polyèdres - premier mémoire", Journal de l'École Polytechnique , 9 (Cahier 16): 66–86.
22. L'Huillier, S.-A.-J. (1812–1813), "Mémoire sur la polyèdrométrie", Annales de Mathématiques , 3 : 169–189.
23. Cayley, A. (1857), "Sobre la teoría de las formas analíticas llamadas árboles" , Philosophical Magazine , Serie IV, 13 (85): 172–176, doi :10.1017/CBO9780511703690.046, ISBN 9780511703690
24. 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.
25. Sylvester, James Joseph (1878). "Química y álgebra". Nature . 17 (432): 284. Bibcode :1878Natur..17..284S. doi : 10.1038/017284a0 .
26. Tutte, WT (2001), Teoría de grafos, Cambridge University Press, pág. 30, ISBN 978-0-521-79489-3, consultado el 14 de marzo de 2016
27. Gardner, Martin (1992), Música fractal, hipertarjetas y más... Recreaciones matemáticas de Scientific American , WH Freeman and Company, pág. 203
28. Sociedad de Matemáticas Industriales y Aplicadas (2002), "El premio George Polya", Mirando hacia atrás, mirando hacia el futuro: una historia de SIAM (PDF) , p. 26, archivado desde el original (PDF) el 2016-03-05 , consultado el 2016-03-14
29. Heinrich Heesch: Untersuchungen zum Vierfarbenproblem. Mannheim: Bibliographisches Institut 1969.
30. Appel, K.; Haken, W. (1977), "Cada mapa planar es coloreable en cuatro dimensiones. Parte I. Descarga" (PDF) , Illinois J. Math. , 21 (3): 429–490, doi : 10.1215/ijm/1256049011 .
31. Appel, K.; Haken, W. (1977), "Cada mapa planar es coloreable en cuatro colores. Parte II. Reducibilidad", Illinois J. Math. , 21 (3): 491–567, doi : 10.1215/ijm/1256049012 .
32. 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 .
33. Kepner, Jeremy; Gilbert, John (2011). Algoritmos de grafos en el lenguaje del álgebra lineal. SIAM. p. 1171458. ISBN 978-0-898719-90-1.

Referencias

• 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; ruso, Moscú 1961; español, México 1962; rumano, Bucarest 1969; chino, Shanghai 1963; Segunda impresión de la primera edición en inglés de 1962, Dover, Nueva York 2001.
• Biggs, N.; Lloyd, E.; Wilson, R. (1986). Teoría de grafos, 1736-1936 . Oxford University Press.
• Bondy, JA; Murty, USR (2008). Teoría de grafos . Springer. ISBN 978-1-84628-969-9.
• Bollobás, Béla; Riordan, OM (2003). Resultados matemáticos en grafos aleatorios sin escala en "Handbook of Graphs and Networks" (S. Bornholdt y HG Schuster (eds)) (1.ª ed.). Weinheim: Wiley VCH.
• Chartrand, Gary (1985). Introducción a la teoría de grafos . Dover. ISBN 0-486-24775-9.
• 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-6. Archivado (PDF) del original el 17 de mayo de 2019.
• Gibbons, Alan (1985). Teoría algorítmica de grafos . Cambridge University Press .
• Golumbic, Martin (1980). Teoría algorítmica de grafos y grafos perfectos . Academic Press .
• 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.
• Mahadev, NVR; Peled, Uri N. (1995). Gráficos de umbral y temas relacionados . Holanda Septentrional .
• Newman, Mark (2010). Redes: una introducción . Oxford University Press.
• Kepner, Jeremy; Gilbert, John (2011). Algoritmos de grafos en el lenguaje del álgebra lineal. Filadelfia, Pensilvania: SIAM. ISBN 978-0-898719-90-1.

Enlaces externos

• "Teoría de grafos", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Tutorial de teoría de grafos Archivado el 16 de enero de 2012 en Wayback Machine
• Una base de datos de búsqueda de pequeños gráficos conectados
• Galería de imágenes: gráficos en Wayback Machine (archivados el 6 de febrero de 2006)
• Lista concisa y comentada de recursos de teoría de grafos para investigadores
• rocs — un IDE de teoría de grafos
• La vida social de los routers: 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 de biblioteca en su biblioteca y en otras bibliotecas sobre teoría de grafos
• Una lista de algoritmos de gráficos Archivado el 13 de julio de 2019 en Wayback Machine con referencias y enlaces a implementaciones de bibliotecas de gráficos

Libros de texto en línea

• Transiciones de fase en problemas de optimización combinatoria, Sección 3: Introducción a los gráficos (2006) de Hartmann y Weigt
• Dígrafos: teoría, algoritmos y aplicaciones 2007 por Jorgen Bang-Jensen y Gregory Gutin
• Teoría de grafos, por Reinhard Diestel