Teoría de grafos

Este artículo trata sobre conjuntos de vértices conectados por aristas. Para obtener gráficos de funciones matemáticas, consulte Gráfico de una función . Para otros usos, consulte Graph (desambiguación) .

Área de matemáticas discretas

Un dibujo de un gráfico.

En matemáticas , la teoría de grafos es el estudio de grafos , que son estructuras matemáticas que se utilizan 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 bordes (también llamados enlaces o líneas ). Se hace una distinción entre los gráficos no dirigidos , donde los bordes enlazan dos vértices simétricamente, y los gráficos dirigidos , donde los bordes enlazan dos vértices asimétricamente. Los gráficos son uno de los principales objetos de estudio de las matemáticas discretas .

Definiciones

Más información: Glosario de teoría de grafos

Las definiciones en la teoría de grafos varían. Las siguientes son algunas de las formas más básicas de definir gráficos 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 desordenados (es decir, una arista está asociada con dos vértices distintos).

Para evitar la ambigüedad, este tipo de objeto puede denominarse precisamente un gráfico simple no dirigido .

En el borde , los vértices y se denominan puntos finales del borde. El borde se dice que se unen y ya sea incidente en y en . Un vértice puede existir en un gráfico y no pertenecer a una arista. Las aristas múltiples , no permitidas bajo la definición anterior, son dos o más aristas que unen los mismos dos 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 bordes (también llamados 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 borde a un par de vértices desordenado (es decir, un borde está asociado con dos vértices distintos).

Para evitar la ambigüedad, este tipo de objeto puede denominarse precisamente un multigraph no dirigido .

Un bucle es una arista que une un vértice consigo mismo. Los gráficos, tal 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 es incidente (para un multigraph no dirigido) que no está dentro . Entonces, para permitir bucles, las definiciones deben expandirse. 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 la ambigüedad, estos tipos de objetos pueden denominarse bucles de permiso de gráfico simple no dirigido y bucles de permiso de gráfico múltiple 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 generalmente se toman como finitos, y muchos de los resultados conocidos no son verdaderos (o son bastante 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 el 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 le inciden, donde un bucle se cuenta dos veces. El grado de una gráfica 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 es n ( n - 1) / 2 .

Los bordes de un grafo simple no dirigido que permiten bucles inducen una relación simétrica homogénea en los vértices de eso se llama relación de adyacencia de . Específicamente, para cada borde , se dice que sus extremos 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}$

Gráfico dirigido

Artículo principal: Gráfico dirigido

Un gráfico dirigido con tres vértices y cuatro bordes dirigidos (la flecha doble representa un borde 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 con dos vértices distintos).

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

En el borde dirigido de a , los vértices y se denominan los puntos finales del borde, la cola del borde y la cabeza del borde. El borde se dice que se unen y ya sea incidente en y en . Un vértice puede existir en un gráfico y no pertenecer a una arista. El borde se llama borde invertido de . Los bordes múltiples , no permitidos bajo la definición anterior, son dos o más bordes 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 bordes (también llamados bordes dirigidos , 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 borde a un par ordenado de vértices (es decir, un borde está asociado con dos vértices distintos).

Para evitar ambigüedades, este tipo de objeto puede denominarse precisamente multigraph 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 es incidente (para un multigraph dirigido) que no está dentro . Entonces, para permitir bucles, las definiciones deben expandirse. Para gráficos simples dirigidos, la definición de debe modificarse a . Para multigrafos dirigidos, la definición de debe modificarse a . Para evitar la ambigüedad, estos tipos de objetos pueden denominarse precisamente un gráfico simple dirigido que permite bucles y un multigraph 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 grafo simple dirigido que permiten bucles es 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 extremos 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 editores de Wikipedia (bordes) que contribuyen 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. Haciendo hincapié en su aplicación a los 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 los bordes, y el sujeto que expresa y comprende los sistemas del mundo real como una red es llamada ciencia de redes .

Ciencias de la computación

En informática , los gráficos se utilizan para representar redes de comunicación, organización de datos, dispositivos computacionales, el flujo de cálculo, etc. Por ejemplo, la estructura de enlaces de un sitio web se puede representar mediante un gráfico 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] viajes, biología, diseño de chips de computadora, mapeo de la progresión de enfermedades neurodegenerativas, ^{[11] [12]} y muchos otros campos. El desarrollo de algoritmos para manejar gráficos es, por tanto, de gran interés en informática. La transformación de gráficosa 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 y consulta persistentes y seguros de transacciones de datos estructurados en gráficos .

Lingüística

Los métodos de 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 arbóreas, 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 dirigida por 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 cuando se aplica a las computadoras, modelar el significado de las palabras es más fácil cuando una palabra dada se entiende en términos de palabras relacionadas; Por tanto, las redes semánticas son importantes en la lingüística computacional . Aún así, otros métodos en fonología (por ejemplo , teoría de la optimalidad , que usa gráficos de celosía ) y morfología (por ejemplo, morfología de estado finito , usando transductores de estado finito ) son comunes en el análisis del lenguaje como un gráfico. De hecho, la utilidad de esta área de las matemáticas para la lingüística ha surgido de organizaciones como TextGraphs , así como de 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 la 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 teóricas de gráficos 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 en una forma en estrecho contacto con los números experimentales que uno quiere entender". ^[13] En química, una gráfica crea un modelo natural para una molécula, donde los vértices representan átomos y enlaces de aristas.. 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 las partes que interactúan de un sistema, así como la dinámica de un proceso físico en dichos sistemas. Del mismo modo, en neurociencia computacionalLos gráficos se pueden utilizar para representar conexiones funcionales entre áreas del cerebro 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 la red. ^{[14] Los} gráficos también se utilizan para representar los canales de 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 molecularcomo un 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 que se estudia como una transición de fase. Esta ruptura se estudia mediante la teoría de la percolación. ^{[15] [16]}

Ciencias sociales

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

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. ^{[18] 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 los esfuerzos de biología y conservación donde un vértice puede representar regiones donde ciertas especies existen (o habitan) y los bordes representan rutas de migración o movimiento entre las regiones. Esta información es importante al observar patrones de reproducción o rastrear 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 de transcriptoma de una sola célula . Otro uso es modelar genes o proteínas en una ruta y estudiar las relaciones entre ellos, como las rutas metabólicas y las redes reguladoras de genes. ^[19]Los árboles evolutivos, las redes ecológicas y la agrupación jerárquica de patrones de expresión génica también se representan como estructuras gráficas. Los métodos basados ​​en gráficos son omnipresentes para los investigadores en algunos campos de la biología y estos solo se generalizarán mucho más a medida que se desarrolle la tecnología para aprovechar este tipo de datos multidimensionales de gran alcance.

La teoría de grafos también se utiliza en conectómica ; ^{[20] Los} sistemas nerviosos pueden verse como un gráfico, donde los nodos son neuronas y los bordes son las conexiones entre ellos.

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

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 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. ^[21] Este artículo, así como el escrito por Vandermonde sobre el problema de los caballeros , continúa 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 ^[22] y L'Huilier , ^[23] 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 estaba introduciendo el concepto de topología, Cayley se interesó por las formas analíticas particulares que surgen del cálculo diferencial para estudiar una clase particular de gráficos, los árboles . ^[24] 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 enumerativos 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 Bruijnen 1959. Cayley vinculó sus resultados sobre árboles con estudios contemporáneos de composición química. ^[25] 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ánticos" y "covariantes" de álgebra y diagramas moleculares: ^[26]

"[…] Cada invariante y covariante se vuelve así expresable mediante un gráfico exactamente idéntico a un diagrama o químicograma 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. ^[27] Otro libro de Frank Harary , publicado en 1969, fue "considerado en todo el mundo como el libro de texto definitivo sobre el tema", ^[28] y permitió a matemáticos, químicos, ingenieros eléctricos y científicos sociales hablar entre ellos. Harary donó todas las regalías para financiar el Premio Pólya . ^[29]

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 Hadwigercondujo al estudio de los colores 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 fueron el origen de otra rama de la teoría de grafos, la teoría de grafos extremos .

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. ^[30] 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. ^{[31] [32]} La prueba involucró la verificación de 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 considerando solo 633 configuraciones . ^[33]

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

Dibujo gráfico

Artículo principal: 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 un borde. Si el gráfico está dirigido, la dirección se indica dibujando una flecha.

Un dibujo gráfico no debe confundirse con el gráfico en sí (la estructura abstracta, no visual) ya que hay varias formas de estructurar el dibujo gráfico. Todo lo que importa es qué vértices están conectados a qué otros por cuántos bordes y no el diseño exacto. En la práctica, a menudo es 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 gráfico. 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 engloba problemas que tratan con el número de cruce y sus diversas generalizaciones. El número de cruce de un gráfico es el número mínimo de intersecciones entre los bordes 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 en superficies distintas al plano.

Estructuras de datos de teoría de grafos

Artículo principal: Gráfico (tipo de datos abstracto)

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. En teoría, se puede distinguir entre estructuras de listas y matrices, pero en aplicaciones concretas, la mejor estructura suele ser una combinación de ambas. Las estructuras de lista a menudo se prefieren para gráficos dispersos, ya que tienen requisitos de memoria más pequeños. Las estructuras matriciales , por otro lado, brindan un acceso más rápido para algunas aplicaciones, pero pueden consumir grandes cantidades de memoria. Las implementaciones de estructuras matriciales dispersas que son eficientes en arquitecturas de computadoras paralelas modernas son un objeto de investigación actual. ^[34]

Las estructuras de lista incluyen la lista de bordes , 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 bordes, cada vértice tiene una lista de los vértices a los que está adyacente.

Las estructuras matriciales incluyen la matriz de incidencia , una matriz de ceros y unos cuyas filas representan vértices y cuyas columnas representan bordes, 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 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 distancias, 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 una ruta más corta entre dos vértices.

Problemas

Enumeración

Existe una gran cantidad de 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 subgrafo , 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 subgráficos, lo que significa que un gráfico tiene la propiedad si y solo si todos los subgráficos también la tienen. Desafortunadamente, encontrar subgrafos máximos de cierto tipo es a menudo un problema NP-completo . Por ejemplo:

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

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

Un problema similar es encontrar subgrafos inducidos en un gráfico dado. De nuevo, 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 más grande o el conjunto independiente se denomina problema de conjunto independiente (NP-completo).

Otro problema de este tipo, el problema menor de contención, es encontrar un gráfico fijo como menor de un gráfico dado. Una menor o subcontracción de un gráfico es cualquier gráfico obtenido al tomar un subgráfico y contraer algunos (o ninguno) bordes. Muchas propiedades de los gráficos son hereditarias para los menores, lo que significa que un gráfico tiene una propiedad si y solo 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 la contención de subdivisiones, es encontrar un gráfico fijo como subdivisión de un gráfico dado. Una subdivisión u homeomorfismo de un gráfico es cualquier gráfico obtenido al subdividir algunos (o ningún) bordes. La contención de la subdivisión está relacionada con las propiedades del gráfico, como la planitud . Por ejemplo, el teorema de Kuratowski establece:

• Un gráfico es plano si no contiene como subdivisión ni el gráfico bipartito completo K _3,3 ni el gráfico completo K ₅ .

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

• Cada gráfico de 5 vértices conectado 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 la medida 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

Artículo principal: 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 del 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 grafo perfecto fuerte
• Conjetura de Erdős-Faber-Lovász (sin resolver)
• Conjetura de coloración total , también llamada conjetura de Behzad (sin resolver)
• Lista de conjetura de coloración (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 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 lo tanto, contienen una mayor cantidad de información, están subsumidos por 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 los 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 tal gráfico existe; Se conocen algoritmos de unificación eficientes.

Para los marcos de restricciones que son estrictamente composicionales , la unificación de gráficos es la función de combinación y satisfacibilidad suficiente. Las aplicaciones más 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-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 de la guardia del museo

Cubriendo problemas

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 de los conjuntos dominantes es el caso especial del problema de cobertura de conjuntos donde los conjuntos son los barrios cerrados .
• El problema de la cubierta del vértice es el caso especial del problema de la cubierta del conjunto donde los conjuntos a cubrir son todos los bordes.
• El problema de la cobertura del conjunto original, también llamado conjunto de impacto, puede describirse como una cobertura de vértice en un hipergráfico.

Problemas de descomposición

La descomposición, definida como la división del conjunto de bordes de un gráfico (con tantos vértices como sea necesario acompañando los bordes de cada parte de la partición), tiene una amplia variedad de preguntas. A menudo, el problema consiste en descomponer un gráfico en subgráficos isomórficos 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 dado, 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, ... , n - 1 aristas.

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

• Arboricidad , una descomposición en la menor cantidad de bosques posible
• 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 posible de combinaciones
• Factorización de gráficos , una descomposición de un gráfico regular en subgráficos regulares de grados determinados

Clases de gráficos

Muchos problemas involucran la caracterización de los miembros de varias clases de gráficos. A continuación se muestran algunos ejemplos de tales preguntas:

• Enumerar los miembros de una clase
• Caracterizar una clase en términos de subestructuras prohibidas
• Determinar las relaciones entre las clases (por ejemplo, ¿una propiedad de los gráficos implica otra)
• Encontrar algoritmos eficientes para decidir la pertenencia a 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
• Gráfico 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 gráfica
• Base de datos de gráficos
• Estructura de datos gráficos
• 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 de caballeros
• Gráfico lógico
• Círculo
• Teoría de redes
• Gráfico nulo
• Problemas de movimiento de guijarros
• Filtración
• Gráfico perfecto
• Gráfico cuántico
• Gráficos regulares aleatorios
• Redes semánticas
• Teoría de grafos espectrales
• Gráficos muy 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 primero
• Búsqueda en profundidad primero
• Algoritmo de Dijkstra
• Algoritmo de Edmonds-Karp
• Algoritmo de Floyd-Warshall
• Algoritmo de Ford-Fulkerson
• Algoritmo Hopcroft-Karp
• Algoritmo húngaro
• El algoritmo de Kosaraju
• Algoritmo de Kruskal
• Algoritmo del vecino más cercano
• 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
• Clasificación topológica

Subáreas

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

Áreas de matemáticas relacionadas

• Combinatoria
• Teoría de grupos
• Teoría del nudo
• Teoría de Ramsey

Generalizaciones

• Hypergraph
• Complejo simplicial abstracto

Teóricos de grafos destacados

• Alon, Noga
• Berge, Claude
• Bollobás, Béla
• Bondy, Adrian John
• Brightwell, Graham
• Chudnovsky, María
• Chung, fan
• Dirac, Gabriel Andrew
• Erdős, Paul
• Euler, Leonhard
• Faudree, Ralph
• Fleischner, Herbert
• Golumbic, Martín
• Graham, Ronald
• Harary, Frank
• Heawood, Percy John
• Kotzig, Anton
• Kőnig, Dénes
• Lovász, László
• Murty, USR
• Nešetřil, Jaroslav
• Rényi, Alfréd
• Ringel, Gerhard
• Robertson, Neil
• Seymour, Paul
• Sudakov, Benny
• Szemerédi, Endre
• Thomas, Robin
• Thomassen, Carsten
• Turán, Pál
• Tutte, WT
• Whitney, Hassler

Notas

1. Bender y Williamson , 2010 , p. 148.
2. Ver, por ejemplo, Iyanaga y Kawada, 69 J , p. 234 o Biggs, pág. 4.
3. Bender y Williamson , 2010 , p. 149.
4. Ver, por ejemplo, Graham et al., P. 5.
5. Bender y Williamson , 2010 , p. 161.
6. Hale, Scott A. (2013). "Multilingües y edición de Wikipedia". Actas de la Conferencia ACM 2014 sobre ciencia web - WebSci '14 : 99–108. arXiv : 1312.0976 . Código bibliográfico : 2013arXiv1312.0976H . doi : 10.1145 / 2615569.2615684 . ISBN 9781450326223. S2CID  14027025 .
7. Mashaghi, A .; et al. (2004). "Investigación de una red de complejos de proteínas". Diario Europea de Física 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 / cerebro / awz125 . ISSN 0006-8950 . PMC 6598625 . PMID 31099821 .   
9. Adali, Tulay; Ortega, Antonio (mayo de 2018). "Aplicaciones de la teoría de gráficos [análisis del problema]" . Actas del IEEE . 106 (5): 784–786. doi : 10.1109 / JPROC.2018.2820300 . ISSN 0018-9219 . 
10. Grandjean, Martin (2016). "Un análisis de redes sociales de 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 de " Small World "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". Imágenes cerebrales y comportamiento . 11 (2): 473–485. doi : 10.1007 / s11682-016-9528-3 . PMID 26960946 . S2CID 3987492 .  
12. Vecchio, F (2013). "Conectividad de 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. 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, Mark (2010). Redes: una introducción (PDF) . Prensa de la Universidad de Oxford.
16. Reuven Cohen, Shlomo Havlin (2010). Redes complejas: estructura, robustez y función Cambridge University Press.
17. 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 .
18. 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.
19. Kelly, S Thomas; Black, Michael A (2 de marzo de 2020). "graphsim: un paquete de R para simular datos de expresión génica a partir de estructuras gráficas de vías biológicas" . bioRxiv . 2020.03.02.972471. doi : 10.1101 / 2020.03.02.972471 . S2CID 214722561 . Consultado el 27 de mayo de 2020 . 
20. 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 / cerebro / awz125 . ISSN 0006-8950 . PMC 6598625 . PMID 31099821 .   
21. Biggs, N .; Lloyd, E .; Wilson, R. (1986), teoría de grafos, 1736-1936 , Oxford University Press
22. Cauchy, AL (1813), "Recherche sur les polyèdres - premier mémoire", Journal de l'École Polytechnique , 9 (Cahier 16): 66–86.
23. L'Huillier, S.-A.-J. (1812-1813), "Mémoire sur la polyèdrométrie", Annales de Mathématiques , 3 : 169-189.
24. 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
25. 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 .
26. Sylvester, James Joseph (1878). "Química y Álgebra" . Naturaleza . 17 (432): 284. Bibcode : 1878Natur..17..284S . doi : 10.1038 / 017284a0 .
27. Tutte, WT (2001), Teoría de grafos , Cambridge University Press, p. 30, ISBN 978-0-521-79489-3, consultado el 14 de marzo de 2016
28. Gardner, Martin (1992), Fractal Music, Hypercards y más… Recreaciones matemáticas de Scientific American , WH Freeman and Company, p. 203
29. 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 , consultado el 14 de marzo de 2016
30. Heinrich Heesch: Untersuchungen zum Vierfarbenproblem. Mannheim: Bibliographisches Institut 1969.
31. Appel, K .; Haken, W. (1977), "Cada mapa plano tiene cuatro colores. Parte I. Descarga", Illinois J. Math. , 21 (3): 429–490, doi : 10.1215 / ijm / 1256049011 .
32. Appel, K .; Haken, W. (1977), "Cada mapa plano tiene cuatro colores. Parte II. Reducibilidad", Illinois J. Math. , 21 (3): 491–567, doi : 10.1215 / ijm / 1256049012 .
33. 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 .
34. Kepner, Jeremy; Gilbert, John (2011). Algoritmos de 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 .
• Claude, Claude (1958). Théorie des graphes et ses aplicaciones . París: Dunod.Edición en inglés, Wiley 1961; Methuen & Co, Nueva York 1962; Rusia, Moscú 1961; Español, México 1962; Rumano, Bucarest 1969; Chino, Shanghai 1963; Segunda edició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.
• Gibbons, Alan (1985). Teoría algorítmica de grafos . Prensa de la Universidad de Cambridge .
• Reuven Cohen, Shlomo Havlin (2010). Redes complejas: estructura, robustez y función . Prensa de la Universidad de Cambridge. ISBN 9781139489270.
• 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 umbral y temas relacionados . Holanda Septentrional .
• Newman, Mark (2010). Redes: una introducción . Prensa de la Universidad de Oxford.
• Kepner, Jeremy; Gilbert, John (2011). Algoritmos de gráficos en el lenguaje del álgebra lineal . Filadelfia, Pensilvania: SIAM. ISBN 978-0-898719-90-1.

Enlaces externos

Wikimedia Commons tiene medios relacionados con la teoría de grafos .

• "Teoría de grafos" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Tutorial de teoría de grafos
• Una base de datos con capacidad de búsqueda de pequeños gráficos conectados
• Galería de imágenes: gráficos en la Wayback Machine (archivado el 6 de febrero de 2006)
• Lista concisa y anotada de recursos de teoría de grafos para investigadores
• rocs - un IDE de teoría de grafos
• La vida social de los enrutadores : documento no técnico que analiza gráficos de personas y computadoras
• Software de teoría de grafos : herramientas para enseñar y aprender la teoría de grafos
• Libros en línea y recursos de la biblioteca 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
• Digraphs: Theory Algorithms and Applications 2007 por Jorgen Bang-Jensen y Gregory Gutin
• Teoría de grafos, de Reinhard Diestel