Teoría de grafos

Área de matemáticas discretas

Un dibujo de un gráfico.

En matemáticas , la teoría de grafos es el estudio de los gráficos , que son estructuras matemáticas utilizadas para modelar relaciones por pares entre objetos. Un gráfico en este contexto está formado por vértices (también llamados nodos o puntos ) que están conectados por aristas (también llamadas enlaces o líneas ). Se hace una distinción entre gráficos no dirigidos , donde las aristas unen dos vértices simétricamente, y gráficos dirigidos , donde las aristas unen dos vértices asimétricamente. Los gráficos son uno de los principales objetos de estudio en matemáticas discretas .

Definiciones

Las definiciones en teoría de grafos varían. Las siguientes son algunas de las formas más básicas de definir gráficas y estructuras matemáticas relacionadas .

Grafico

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 desordenados (es decir, una arista está asociada con dos vértices distintos).

Para evitar ambigüedades, este tipo de objeto puede denominarse precisamente grafo simple no dirigido .

En la arista , los vértices y se denominan puntos finales de la arista. Se dice que el borde se une y y incidente una y otra vez . Un vértice puede existir en un gráfico 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}$

En un sentido más general del término que permite múltiples aristas, ^{[3] [4]} un gráfico 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 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 desordenados (es decir, una arista está asociada con dos vértices distintos).

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

Un bucle es una arista que une un vértice consigo mismo. Los gráficos como se definen en las dos definiciones anteriores no pueden tener bucles, porque un bucle que une un vértice consigo mismo es el borde (para un gráfico simple no dirigido) o incide en (para un multigrafo no dirigido) que no está en . Para permitir bucles, se deben ampliar las definiciones. Para gráficos 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 denominarse gráficos simples no dirigidos que permiten bucles y multigrafos no dirigidos que permiten bucles (a veces también pseudografos no dirigidos ), 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 generalmente se consideran finitos, y muchos de los resultados conocidos no son ciertos (o son más bien diferentes) para gráficos 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 un conjunto vacío. El orden de una gráfica es su número de vértices. El tamaño de un gráfico es su número de aristas. El grado o valencia de un vértice es el número de aristas que inciden en él, donde un bucle se cuenta dos veces. El grado de un gráfico es el máximo de los grados de sus vértices. ${\displaystyle E}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle |V|}$ ${\displaystyle |E|}$

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

Los bordes de un gráfico simple no dirigido que permite bucles inducen una relación simétrica homogénea en los vértices de que se llama relación de adyacencia de . Específicamente, para cada borde , se dice que sus puntos finales y son adyacentes entre sí, lo que se denota . ${\displaystyle G}$ ${\displaystyle \sim }$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\sim y}$

Gráfico dirigido

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

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

En un sentido restringido pero muy común del término, ^[5] un grafo 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 con dos vértices distintos).

Para evitar ambigüedades, este tipo de objeto puede denominarse 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 el borde se une y y incidente una y otra vez . Un vértice puede existir en un gráfico y no pertenecer a una arista. La arista se llama arista invertida de . 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 denominarse precisamente multigrafo dirigido .

Un bucle es una arista que une un vértice consigo mismo. Los gráficos dirigidos, como se definen en las dos definiciones anteriores, no pueden tener bucles, porque un bucle que une un vértice consigo mismo es el borde (para un gráfico simple dirigido) o incide en (para un multigrafo dirigido) que no está en . Entonces, para permitir bucles, se deben ampliar las definiciones. Para gráficos simples dirigidos, la definición de debe modificarse a . Para multigrafos dirigidos, la definición de debe modificarse a . Para evitar ambigüedades, este tipo de objetos pueden denominarse precisamente un gráfico simple dirigido que permite bucles y un multigrafo dirigido que permite bucles (o un carcaj ), 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\}}$

Los bordes de un gráfico simple dirigido que permiten bucles son una relación homogénea ~ en los vértices de eso se llama relación de adyacencia de . Específicamente, para cada borde , se dice que sus puntos finales y 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 (bordes) que contribuyeron a diferentes versiones de idiomas de Wikipedia (vértices) durante un mes en el verano de 2013. ^[6]

Los gráficos 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 gráficos. Al enfatizar su aplicación a sistemas del mundo real, el término red a veces se define como un gráfico en el que los atributos (por ejemplo, nombres) están asociados con los vértices y aristas, y el tema que expresa y entiende los sistemas del mundo real como una red se llama ciencia de la red .

Ciencias de la Computación

Dentro de la informática , las estructuras vinculadas causales y no causales son gráficos 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 vínculos de un sitio web se puede representar mediante un enlace dirigido. gráfico, 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 de 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 tanto, el desarrollo de algoritmos para manejar gráficos es de gran interés en la informática. La transformación de gráficos a menudo se formaliza y representa mediante sistemas de reescritura de gráficos . Como complemento a los sistemas de transformación de gráficos que se centran en la manipulación de gráficos en memoria basada en reglas, se encuentran las bases de datos de gráficos orientadas al almacenamiento persistente y seguro para transacciones y a la consulta de datos estructurados de gráficos .

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 estructuras discretas. 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 gráfico jerárquico. Los enfoques más contemporáneos, como la gramática de estructura de frases basada en la cabeza, modelan la sintaxis del lenguaje natural utilizando estructuras de características escritas , que son gráficos acíclicos dirigidos . Dentro de la semántica léxica , especialmente aplicada a las computadoras, modelar el significado de las palabras es más fácil cuando una palabra determinada se entiende en términos de palabras relacionadas; Por 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 optimización , que utiliza gráficos 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 gráfico. De hecho, la utilidad de esta área de las matemáticas para la lingüística ha dado origen 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 complicadas estructuras atómicas simuladas se puede estudiar cuantitativamente recopilando estadísticas sobre propiedades teóricas de grafos relacionadas con la topología de los átomos. Además, "los gráficos y las reglas de cálculo de Feynman resumen la teoría cuántica de campos de una forma que está en estrecho contacto con los números experimentales que uno quiere comprender". ^[13] En química, un gráfico constituye un modelo natural para una molécula, donde los vértices representan átomos y los bordes son 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 gráficos pueden representar conexiones locales entre partes interactivas de un sistema, así como la dinámica de un proceso físico en dichos sistemas. De manera similar, en neurociencia computacional los gráficos se pueden usar para representar conexiones funcionales entre áreas del cerebro que interactúan para dar lugar a diversos 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 alambre para obtener las propiedades eléctricas de las estructuras de la red. ^[14] Los gráficos 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 gráfico molecular como medio para modelar moléculas. Los gráficos 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 en la que la red se divide en pequeños grupos, lo que se estudia como una transición de fase. Esta descomposición se estudia mediante la teoría de la percolación . ^[15]

Ciencias Sociales

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

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 difusió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 gráficos. ^[17] Los gráficos de conocimiento y amistad describen si las personas se conocen entre sí. Los gráficos de influencia modelan si determinadas personas pueden influir en el comportamiento de otras. Finalmente, los gráficos de colaboración modelan si dos personas trabajan juntas de una manera particular, como actuar juntas en una película.

Biología

Asimismo, la teoría de grafos es útil en biología y esfuerzos 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 de células en el análisis del transcriptoma unicelular . 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 se pueden ver como un gráfico, donde los nodos son neuronas y los bordes son las conexiones entre ellas.

Matemáticas

En matemáticas, los gráficos son útiles en geometría y ciertas partes de la topología como la teoría de nudos . La teoría de grafos algebraica tiene estrechos vínculos 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

La estructura de un gráfico 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. Estos 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 vuelos.

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 caballero , continuó 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 inicio 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 gráficos, 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 gráficos con propiedades particulares. La teoría de grafos enumerativa surgió entonces a partir de los resultados de Cayley y los resultados fundamentales publicados por Pólya entre 1935 y 1937. Estos fueron generalizados por De Bruijn en 1959. Cayley vinculó sus resultados sobre á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 "gráfico" fue introducido por Sylvester en un artículo publicado en 1878 en Nature , donde establece una analogía entre "invariantes cuánticas" y "covariantes" del álgebra y los diagramas moleculares: ^[25]

"[…] Cada 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 al producto de in- o covariantes cuyos gráficos separados se dan. […]" (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ó a matemáticos, químicos, ingenieros eléctricos y científicos sociales hablar entre sí. Harary donó todas las regalías para financiar el Premio Pólya . ^[28]

Uno de los problemas más famosos y estimulantes 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 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 se encuentra en una carta de De Morgan dirigida a Hamilton el mismo año. Se han propuesto muchas pruebas incorrectas, incluidas las de Cayley, Kempe y otros. El estudio y la generalización de este problema por Tait , Heawood , Ramsey y Hadwiger llevaron al estudio de las coloraciones de los gráficos 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 ordenadores. ^[29] Una prueba asistida por ordenador realizada en 1976 por Kenneth Appel y Wolfgang Haken hace uso fundamental del concepto de "descarga" desarrollado por Heesch. ^{[30] [31]} La prueba implicó verificar las propiedades de 1.936 configuraciones por computadora y no fue completamente aceptada en ese momento debido a su complejidad. Veinte años más tarde, Robertson , Seymour , Sanders y Thomas dieron una prueba más sencilla considerando sólo 633 configuraciones . ^[32]

El desarrollo autónomo de la topología entre 1860 y 1930 fecundó 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 más, conocida como teoría de grafos aleatoria , que ha sido una fuente fructífera de resultados de la teoría de grafos.

Representación

Un gráfico es una abstracción de las relaciones que surgen en la naturaleza; por tanto, no puede acoplarse 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, normalmente, los vértices se dibujan y 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 gráfico.

Visual: dibujo gráfico

Los gráficos generalmente 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 un borde. Si la gráfica está dirigida, la dirección se indica dibujando una flecha. Si el gráfico está ponderado, el peso se agrega en la flecha.

Un dibujo de gráfico no debe confundirse con el gráfico en sí (la estructura abstracta y no visual), ya que hay varias formas de estructurar el dibujo de gráfico. Lo único que importa es qué vértices están conectados a otros mediante cuántas aristas y no el diseño exacto. En la práctica, suele ser difícil decidir si dos dibujos representan el mismo gráfico. Dependiendo del dominio del problema, algunos diseños pueden ser más adecuados y más fáciles de entender que otros.

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

También se puede decir que el dibujo de gráficos abarca problemas que tienen que ver con el número de cruce y sus diversas generalizaciones. El número de cruces de un gráfico es el número mínimo de intersecciones entre aristas que debe contener un dibujo del gráfico en el plano. Para un gráfico plano , el número de cruce es cero por definición. También se estudian dibujos sobre superficies distintas al plano.

Existen otras técnicas para visualizar un gráfico alejado de los vértices y aristas, incluidos los empaquetamientos circulares , el gráfico de intersección y otras visualizaciones de la matriz de adyacencia .

Tabular: estructuras de datos gráficos

La representación tabular se presta bien a aplicaciones computacionales. Hay 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 manipular el gráfico. Teóricamente se puede distinguir entre estructuras de listas y matriciales, 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. Por otro lado, las estructuras matriciales proporcionan un acceso más rápido para algunas aplicaciones, pero pueden consumir enormes cantidades de memoria. Las implementaciones de estructuras matriciales dispersas que son eficientes en arquitecturas informáticas paralelas modernas son 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 a qué vértices 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 gráfico. 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 del camino más corto entre dos vértices.

Problemas

Enumeración

Existe una gran literatura sobre 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 gráfico fijo como subgrafo en un gráfico dado. Una razón para estar interesado en esta pregunta es que muchas propiedades de los gráficos son hereditarias para los subgrafos, lo que significa que un gráfico tiene la propiedad si y sólo si todos los subgrafos también la tienen. Desafortunadamente, encontrar subgrafos máximos de un determinado tipo suele ser un problema NP-completo . Por ejemplo:

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

Un caso especial de isomorfismo de subgrafos es el problema de isomorfismo de grafos . Pregunta si dos gráficos son isomorfos. No se sabe si este problema es NP-completo ni si puede resolverse en tiempo polinomial.

Un problema similar es encontrar subgrafos inducidos en un gráfico determinado. Nuevamente, algunas propiedades importantes de los gráficos son hereditarias con respecto a los subgrafos inducidos, lo que significa que un gráfico 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 o el conjunto independiente más grande se denomina problema de conjunto independiente (NP-completo).

Otro problema más, el problema de contención menor, es encontrar un gráfico fijo como menor de un gráfico dado. Una subcontracción o menor de un gráfico es cualquier gráfico obtenido tomando un subgrafo y contrayendo algunos (o ninguno) de los bordes. Muchas propiedades de los grafos son hereditarias para los menores, lo que significa que un grafo tiene una propiedad si y sólo si todos los menores también la tienen. Por ejemplo, el teorema de Wagner establece:

• Un gráfico es plano si no contiene como menor ni el gráfico bipartito completo K _3,3 (ver el problema de las tres cabañas ) ni el gráfico completo K ₅ .

Un problema similar, el problema de contención de subdivisión, consiste en encontrar un gráfico fijo como subdivisión de un gráfico determinado. Una subdivisión u homeomorfismo de un gráfico es cualquier gráfico obtenido subdividiendo algunos (o ninguno) de los bordes. La contención de subdivisión está relacionada con propiedades del gráfico como la planaridad . Por ejemplo, el teorema de Kuratowski establece:

• Un grafo es plano 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 por subdivisión es la conjetura de Kelmans-Seymour :

• Cada gráfico conectado con 5 vértices que no es 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 varias especies y generalizaciones de gráficos están determinadas por sus subgrafos con puntos eliminados . 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 gráficos. Normalmente, a uno le interesa colorear un gráfico de modo que no haya dos vértices adyacentes que tengan el mismo color o con otras restricciones similares. También se puede considerar colorear los bordes (posiblemente para que no haya dos bordes coincidentes del mismo color) u otras variaciones. Entre los famosos resultados y conjeturas sobre la coloración de gráficos se encuentran los siguientes:

• Teorema de los cuatro colores
• Teorema del gráfico perfecto fuerte
• Conjetura de Erdős-Faber-Lovász
• Conjetura de coloración total , también llamada conjetura de Behzad (sin resolver)
• Lista de conjeturas para colorear (sin resolver)
• Conjetura de Hadwiger (teoría de grafos) (sin resolver)

Subsunción y unificación

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

Para marcos de restricciones que son estrictamente compositivos , la unificación de gráficos es la función de combinación y satisfacibilidad suficiente. Las aplicaciones conocidas incluyen la demostración automática de teoremas y el modelado de la elaboración de estructuras lingüísticas .

Problemas de ruta

• Problema del camino hamiltoniano
• Árbol de expansión mínimo
• Problema de inspección de ruta (también llamado "problema del cartero chino")
• Siete puentes de Königsberg
• Problema del camino más corto
• árbol steiner
• Problema de las tres cabañas
• Problema del vendedor ambulante (NP-difícil)

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 de guardia 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/subgrafos.

• El problema de conjuntos dominantes es el caso especial del problema de cobertura de conjuntos donde los conjuntos son las vecindades cerradas .
• El problema de cobertura de vértices es el caso especial del problema de cobertura de conjuntos donde los conjuntos a cubrir son todos los bordes.
• El problema de cobertura de conjunto original, también llamado conjunto de aciertos, se puede describir como una cobertura de vértice en un hipergráfico.

Problemas de descomposición

La descomposición, definida como dividir el conjunto de aristas de un gráfico (con tantos vértices como sea necesario acompañando a las aristas de cada parte de la partición), plantea una amplia variedad de preguntas. A menudo, el problema es descomponer un gráfico en subgrafos isomorfos a un gráfico fijo; por ejemplo, descomponer un gráfico completo en ciclos hamiltonianos. Otros problemas especifican una familia de gráficos en los que se debe descomponer un gráfico determinado, por ejemplo, una familia de ciclos, o descomponer un gráfico completo K _n en n − 1 árboles específicos que tienen, respectivamente, 1, 2, 3, ... , norte - 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 borde exactamente dos veces
• Coloración de bordes , una descomposición en la menor cantidad de coincidencias posible
• Factorización de gráficos , una descomposición de un gráfico regular en subgrafos regulares de grados dados

Clases de grafos

Muchos problemas implican caracterizar los miembros de varias clases de gráficos. A continuación se muestran algunos ejemplos de este tipo de preguntas:

• Enumerar los miembros de una clase.
• Caracterizar 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 membresía en una clase
• Encontrar representaciones para miembros de una clase.

Ver 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
• grafico conceptual
• Estructura de datos
• Estructura de datos de conjuntos disjuntos
• Evolución de doble fase
• Gráfico entitativo
• Gráfico existencial
• Álgebra gráfica
• Automorfismo gráfico
• Coloración de gráficos
• Base de datos de gráficos
• Estructura de datos del gráfico
• dibujo gráfico
• Ecuación gráfica
• Reescritura de gráficos
• Problema de sándwich gráfico
• Propiedad gráfica
• Gráfico de intersección
• Tour 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
• grafico perfecto
• Gráfico cuántico
• Gráficos regulares aleatorios
• Redes semánticas
• Teoría de grafos espectrales
• Gráficos fuertemente regulares
• Graficos simetricos
• 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 cercano
• Algoritmo simplex de red
• Algoritmos de prueba de planaridad
• algoritmo de primi
• Algoritmo de flujo máximo push-reetiqueta
• Algoritmo de componentes fuertemente conectados de Tarjan
• clasificación topológica

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 de las matemáticas

• combinatoria
• teoría de grupos
• teoría de nudos
• teoría de ramsey

Generalizaciones

• hipergrafo
• Complejo simple abstracto

Destacados teóricos de grafos

• Alón, Noga
• Bergé, Claude
• Bollobás, Béla
• Bondy, Adrián John
• Brightwell, Graham
• Chudnovsky, María
• Chung, ventilador
• Dirac, Gabriel Andrés
• 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
• Kőnig, Dénes
• Lovász, László
• Murty, USR
• Nešetřil, Jaroslav
• Rényi, Alfredo
• Ringel, Gerhard
• Robertson, Neil
• Seymour, Pablo
• Sudakov, Benny
• Szemerédi, Endre
• Tomás, Robin
• Thomassen, Carsten
• Turán, Pál
• Tutte, peso
• Whitney, Hassler

Notas

1. Bender y Williamson 2010, pág. 148.
2. Véase, por ejemplo, Iyanaga y Kawada, 69 J , p. 234 o Biggs, pág. 4.
3. Bender y Williamson 2010, pág. 149.
4. Véase, por ejemplo, Graham et al., p. 5.
5. Bender y Williamson 2010, pág. 161.
6. Hale, Scott A. (2014). "Edición multilingüe y Wikipedia". Actas de la conferencia ACM de 2014 sobre ciencia web . págs. 99-108. arXiv : 1312.0976 . Código Bib : 2013arXiv1312.0976H. doi :10.1145/2615569.2615684. ISBN 9781450326223. S2CID  14027025.
7. Mashaghi, A.; et al. (2004). "Investigación de una red de complejos proteicos". Revista física europea B. 41 (1): 113–121. arXiv : cond-mat/0304207 . Código Bib : 2004EPJB...41..113M. doi :10.1140/epjb/e2004-00301-0. S2CID  9233932.
8. Shah, Preya; Ashourvan, Arian; Mijaíl, Fadi; Pinos, Adán; 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/cerebro/awz125. ISSN  0006-8950. PMC 6598625 . PMID  31099821. 
9. Adali, Tulay; Ortega, Antonio (mayo de 2018). "Aplicaciones de la teoría de grafos [analizando el problema]" . Actas del IEEE . 106 (5): 784–786. doi :10.1109/JPROC.2018.2820300. ISSN  0018-9219.
10. Grandjean, Martín (2016). "Un análisis de la red social Twitter: mapeo de la comunidad de humanidades digitales" (PDF) . Artes y humanidades convincentes . 3 (1): 1171458. doi : 10.1080/23311983.2016.1171458 . S2CID  114999767.
11. Vecchio, F (2017). "Arquitectura del "mundo pequeño" en la conectividad cerebral y el volumen del hipocampo en la enfermedad de Alzheimer: un estudio mediante 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 teoría de grafos en la demencia frontotemporal". Neurología . 81 (2): 134-143. doi :10.1212/WNL.0b013e31829a33f8. PMID  23719145. S2CID  28334693.
13. Björken, JD; Drell, SD (1965). Campos cuánticos relativistas . Nueva York: McGraw-Hill. pag. 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". Revista de Física Aplicada . 119 (1): 015102. Código bibliográfico : 2016JAP...119a5102K. doi : 10.1063/1.4939280. ISSN  0021-8979.
15. Newman, Marcos (2010). Redes: una introducción (PDF) . Prensa de la Universidad de Oxford. Archivado desde el original (PDF) el 28 de julio de 2020 . Consultado el 30 de octubre de 2019 .
16. Grandjean, Martín (2015). "Análisis y visualización de redes sociales: los sociogramas de Moreno revisitados". Red rediseñada basándose estrictamente 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.; Negro, 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) . Revista de software de código abierto . La revista abierta. 5 (51): 2161. Código bibliográfico : 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; Mijaíl, Fadi; Pinos, Adán; 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/cerebro/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" , Revista Filosófica , 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". Naturaleza . 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, Hypercards y más… Recreaciones matemáticas de Scientific American , WH Freeman and Company, p. 203
28. Sociedad de Matemáticas Industriales y Aplicadas (2002), "Premio George Polya", Mirando hacia atrás, mirando hacia el futuro: una historia de SIAM (PDF) , p. 26, archivado desde el original (PDF) el 5 de marzo de 2016 , consultado el 14 de marzo de 2016
29. Heinrich Heesch: Untersuchungen zum Vierfarbenproblem. Mannheim: Bibliographisches Institut 1969.
30. Appel, K.; Haken, W. (1977), "Cada mapa plano tiene cuatro colores. Parte I. Descarga" (PDF) , Illinois J. Math. , 21 (3): 429–490, doi : 10.1215/ijm/1256049011 .
31. Appel, K.; Haken, W. (1977), "Cada mapa plano se puede colorear en cuatro colores. Parte II. Reducibilidad", Illinois J. Math. , 21 (3): 491–567, doi : 10.1215/ijm/1256049012 .
32. Robertson, N.; Lijadoras, 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, Juan (2011). Algoritmos gráficos en el lenguaje del álgebra lineal. SIAM. pag. 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, Shanghái 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 . Prensa de la Universidad de Oxford.
• Bondy, JA; Murty, USR (2008). Teoría de grafos . Saltador. ISBN 978-1-84628-969-9.
• Bollobás, Béla; Riordan, OM (2003). Resultados matemáticos en gráficos 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) desde el original el 17 de mayo de 2019.
• Gibbons, Alan (1985). Teoría algorítmica de grafos . Prensa de la Universidad de Cambridge .
• Golumbic, Martín (1980). Teoría algorítmica de grafos y grafos perfectos . Prensa académica .
• 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 umbrales y temas relacionados . Holanda del Norte .
• Newman, Marcos (2010). Redes: una introducción . Prensa de la Universidad de Oxford.
• Kepner, Jeremy; Gilbert, Juan (2011). Algoritmos gráficos 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 con capacidad de búsqueda de pequeños gráficos conectados.
• Galería de imágenes: gráficos en Wayback Machine (archivado 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
• The Social Life of 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 bibliotecarios en su biblioteca y en otras bibliotecas sobre teoría de grafos
• Una lista de algoritmos de gráficos 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) por Hartmann y Weigt
• Digrafos: teoría de algoritmos y aplicaciones 2007 por Jorgen Bang-Jensen y Gregory Gutin
• Teoría de grafos, de Reinhard Diestel