Teoría de grafos

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

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

Definiciones

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.

Grafico

En un sentido restringido pero muy común del término, un gráfico es un par ordenado $G=(V,E)$ que comprende:

$V$ , un conjunto de vértices (también llamados nodos o puntos);
${displaystyle Esubseteq {{x,y}mid x,yin V;{textrm {and}};xneq y}}$ , un conjunto de aristas (también llamados enlaces o líneas), que son pares de vértices no ordenados (es decir, una arista está asociada con dos vértices distintos).

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

En la arista ${x,y}$ , los vértices $X$ y $y$ se denominan extremos de la arista. Se dice que el borde se une $X$ y $y$ y es incidente una y $X$ otra vez $y$ . Un vértice puede existir en un gráfico y no pertenecer a un borde. Las aristas múltiples, no permitidas según la definición anterior, son dos o más aristas que unen los mismos dos vértices.

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

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

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

Un bucle es una arista que une un vértice consigo mismo. Los gráficos definidos en las dos definiciones anteriores no pueden tener bucles, porque un bucle $X$ que une un vértice consigo mismo es el borde (para un gráfico simple no dirigido) o incide sobre (para un multigrafo no dirigido) ${ estilo de visualización {x, x } = {x }}$ que no está en ${displaystyle {{x,y}mid x,yin V;{textrm {y}};xneq y}}$ . Entonces, para permitir bucles, las definiciones deben expandirse. Para gráficos simples no dirigidos, la definición de $mi$ debe modificarse a ${displaystyle Esubseteq {{x,y}mid x,yin V}}$ . Para multigrafos no dirigidos, la definición de $fi$ debe modificarse a ${displaystyle phi:Eto {{x,y}mid x,yin V}}$ . Para evitar la ambigüedad, estos tipos de objetos pueden denominarse bucles que permiten gráficos simples no dirigidos y bucles que permiten multigráficos no dirigidos (a veces también seudógrafos no dirigidos).), respectivamente.

$V$ y $mi$ generalmente se consideran 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, $V$ a menudo se supone que no es vacío, pero $mi$ se permite que sea el conjunto vacío. El orden de un grafo es $|V|$ , su número de vértices. El tamaño de un gráfico es $|E|$ , su número de aristas. El grado o valencia de un vértice es el número de aristas que le inciden, donde un lazo se cuenta dos veces. El grado de un grafo es el máximo de los grados de sus vértices.

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 gráfico simple no dirigido que permite bucles $GRAMO$ inducen una relación homogénea simétrica ~ en los vértices de $GRAMO$ lo que se denomina relación de adyacencia de $GRAMO$ . Específicamente, para cada borde $(x, y)$ , se dice que sus extremos $X$ y $y$ son adyacentes entre sí, lo que se denota $X$ ~ $y$ .

Gráfico dirigido

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, un gráfico dirigido es un par ordenado $G=(V,E)$ que comprende:

$V$ , un conjunto de vértices (también llamados nodos o puntos);
${displaystyle Esubseteq left{(x,y)mid (x,y)in V^{2};{textrm {y}};xneq yright}}$ , 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 la arista $(x, y)$ dirigida de $X$ a $y$ , los vértices $X$ y $y$ se llaman extremos $X$ de la arista, cola de la arista y cabeza $y$ de la arista. Se dice que el borde se une y y es incidente una y otra vez. Un vértice puede existir en un gráfico y no pertenecer a un borde. La arista se llama arista invertida de. Las aristas múltiples, no permitidas según la definición anterior, son dos o más aristas con la misma cola y la misma cabeza. $X$ $y$ $X$ $y$ $(y,x)$ $(x, y)$

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

$V$ , un conjunto de vértices (también llamados nodos o puntos);
$mi$ , un conjunto de aristas (también llamadas aristas dirigidas, enlaces dirigidos, líneas dirigidas, flechas o arcos);
${displaystyle phi:Eto left{(x,y)mid (x,y)in V^{2};{textrm {y}};xneq yright }}$ , 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, tal como se definen en las dos definiciones anteriores, no pueden tener bucles, porque un bucle $X$ que une un vértice consigo mismo es el borde (para un gráfico simple dirigido) o es incidente (para un multigrafo dirigido) ${ estilo de visualización (x, x)}$ que no está en ${displaystyle left{(x,y)mid (x,y)in V^{2};{textrm {y}};xneq yright}}$ . Entonces, para permitir bucles, las definiciones deben expandirse. Para grafos simples dirigidos, la definición de $mi$ debe modificarse a ${displaystyle Esubseteq left{(x,y)mid (x,y)in V^{2}right}}$ . Para multigrafos dirigidos, la definición de $fi$ debe modificarse a ${displaystyle phi:Eto left{(x,y)mid (x,y)in V^{2}right}}$ . Para evitar ambigüedades, este tipo de objetos pueden llamarse precisamente gráfico simple dirigido que permite bucles y multigráfico dirigido que permite bucles (o carcaj) respectivamente.

Los bordes de un gráfico simple dirigido que permite bucles $GRAMO$ es una relación homogénea ~ en los vértices de $GRAMO$ que se llama la relación de adyacencia de $GRAMO$ . Específicamente, para cada borde $(x, y)$ , se dice que sus extremos $X$ y $y$ son adyacentes entre sí, lo que se denota $X$ ~ $y$ .

Aplicaciones

Los gráficos se pueden utilizar para modelar muchos tipos de relaciones y procesos en sistemas físicos, biológicos, sociales y de información. 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, los nombres) están asociados con los vértices y las aristas, y el sujeto que expresa y entiende los sistemas del mundo real como una red es llamada ciencia de redes.

Ciencias de la Computación

La rama de la informática conocida como estructuras de datos utiliza gráficos para representar redes de comunicación, organización de datos, dispositivos informáticos, el flujo de cálculo, etc. Por ejemplo, la estructura de enlaces de un sitio web puede representarse mediante un gráfico dirigido, en el que el 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, los viajes, la biología, el diseño de chips informáticos, el mapeo de la progresión de las enfermedades neurodegenerativas,y muchos otros campos. Por lo tanto, el desarrollo de algoritmos para manejar gráficos es de gran interés en 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 y la consulta persistentes y seguras para transacciones de datos estructurados por gráficos.

Lingüística

Los métodos de teoría de grafos, en varias formas, han demostrado ser particularmente útiles en lingüística, ya que el lenguaje natural a menudo se presta bien a la estructura discreta. Tradicionalmente, la sintaxis y la semántica compositiva siguen estructuras basadas en árboles, cuyo poder expresivo reside en el principio de composicionalidad, modelado en un grafo jerárquico. Los enfoques más contemporáneos, como la gramática de estructura de frase impulsada por la cabeza, modelan la sintaxis del lenguaje natural utilizando estructuras de características tipeadas, 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 lo tanto, las redes semánticas son importantes en la lingüística computacional. Aún así, otros métodos en fonología (por ejemplo, la teoría de la optimización, que utiliza gráficos de celosía) y morfología (por ejemplo, morfología de estado finito, utilizando 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 dado lugar a organizaciones como TextGraphs, así como a varios proyectos 'Net', como WordNet, VerbNet y otros.

Física y Química

La teoría de grafos también se usa 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 de teoría 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 en una forma en estrecho contacto con los números experimentales que uno quiere entender".En química, un gráfico constituye un modelo natural para una molécula, donde los vértices representan átomos y las aristas enlaces. Este enfoque se utiliza especialmente en el procesamiento informático de estructuras moleculares, desde editores químicos hasta búsquedas en bases de datos. En física estadística, los gráficos pueden representar conexiones locales entre partes de un sistema que interactúan, así como la dinámica de un proceso físico en tales 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 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 gráficos también se utilizan para representar los canales a microescala de los 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 gráficos químicos utiliza el gráfico molecular como un medio para modelar moléculas. Los gráficos y las redes son excelentes modelos para estudiar y comprender las transiciones de fase y los fenómenos críticos. La eliminación de nodos o bordes conduce a una transición crítica en la que la red se divide en pequeños grupos que se estudian como una transición de fase. Este desglose se estudia a través de la teoría de la percolación.

Ciencias Sociales

La teoría de grafos también se usa 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. Los gráficos de conocimiento y amistad describen si las personas se conocen entre sí. Los gráficos de influencia modelan si ciertas personas pueden influir en el comportamiento de los demás. 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

Del mismo modo, 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 al observar los 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 usan 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" las células en tipos de células en el análisis del transcriptoma de una sola célula. Otro uso es modelar genes o proteínas en una vía y estudiar las relaciones entre ellos, como vías metabólicas y redes reguladoras de genes. 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.

La teoría de grafos también se usa en conectómica; Los sistemas nerviosos se pueden ver como un gráfico, donde los nodos son las 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 algebraicos tiene estrechos vínculos con la teoría de grupos. La teoría de gráficos 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. Dichos gráficos ponderados se usan comúnmente para programar GPS y motores de búsqueda de planificación de viajes que comparan tiempos y costos de vuelos.

Historia

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. Este artículo, al igual que el escrito por Vandermonde sobre el problema del caballero, 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 y L'Huilier, y representa el comienzo de la rama de las matemáticas conocida como topología.

Más de un siglo después del artículo de Euler sobre los puentes de Königsberg y mientras Listing introducía el concepto de topología, Cayley se interesó en formas analíticas particulares que surgían del cálculo diferencial para estudiar una clase particular de gráficos, los árboles. 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 Bruijn en 1959. Cayley vinculó sus resultados sobre árboles con estudios contemporáneos de composición química.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" de álgebra y diagramas moleculares:“[…] Cada invariante y covariante se vuelve así expresable mediante un gráfico exactamente idéntico a un diagrama o quimicógrafo 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 co-variantes 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. Otro libro de Frank Harary, publicado en 1969, fue "considerado en todo el mundo como el libro de texto definitivo sobre el tema", y permitió a matemáticos, químicos, electricistas ingenieros y científicos sociales para hablar entre ellos. Harary donó todas las regalías para financiar el Premio Pólya.

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 tienen ¿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 parte de 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 estudiado 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 usando computadoras. 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. La prueba consistía en verificar las propiedades de 1.936 configuraciones por computadora y no fue completamente aceptada en ese momento debido a su complejidad. Veinte años después, Robertson, Seymour, Sanders y Thomas ofrecieron una prueba más simple considerando solo 633 configuraciones.

El desarrollo autónomo de la topología entre 1860 y 1930 fertilizó la teoría de grafos a través de los trabajos de Jordan, Kuratowski y Whitney. Otro factor importante del desarrollo común de la teoría de grafos y la topología provino del uso de las técnicas del álgebra moderna. El primer ejemplo de tal uso proviene del trabajo del físico Gustav Kirchhoff, quien publicó en 1845 sus leyes de 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 conectividad de grafos, dio lugar a otra rama, conocida como teoría de grafos aleatorios, que ha sido una fuente fructífera de resultados de teoría de grafos.

Representación

Un gráfico es una abstracción de las relaciones que surgen en la naturaleza; por lo 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, por lo general, los vértices se dibujan y conectan por aristas, y la tabular, en la que las filas de una tabla brindan 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 el gráfico es dirigido, la dirección se indica dibujando una flecha. Si el gráfico está ponderado, el peso se agrega en la flecha.

El dibujo de un gráfico no debe confundirse con el gráfico en sí mismo (la estructura abstracta, no visual), ya que hay varias formas de estructurar el dibujo del 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 abarca problemas relacionados con el número de cruce y sus diversas generalizaciones. El número de cruces de una gráfica es el número mínimo de intersecciones entre aristas que debe contener un dibujo de la gráfica en el plano. Para un gráfico plano, el número de cruce es cero por definición. También se estudian los dibujos sobre superficies distintas al plano.

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

Tabular: Graficar estructuras de datos

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

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

Las estructuras de matriz incluyen la matriz de incidencia, una matriz de 0 y 1 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 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, como 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 la enumeración gráfica: el problema de contar gráficos que cumplen condiciones específicas. Parte de este trabajo se encuentra en Harary y Palmer (1973).

Subgrafos, subgrafos inducidos y menores

Un problema común, llamado problema de isomorfismo de subgrafos, es encontrar un gráfico fijo como un 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 llama el problema de la camarilla (NP-completo).

Un caso especial de isomorfismo de subgrafos es el problema de isomorfismo de grafos. Pregunta si dos grafos 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. Una vez más, algunas propiedades importantes del gráfico son hereditarias con respecto a los subgráficos inducidos, lo que significa que un gráfico tiene una propiedad si y solo si todos los subgráficos inducidos también la tienen. Encontrar subgrafos inducidos máximos de cierto tipo también suele ser NP-completo. Por ejemplo:

Encontrar el subgrafo inducido sin bordes más grande o el conjunto independiente se denomina problema del 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 menor o subcontracción de un gráfico es cualquier gráfico obtenido al tomar un subgráfico y contraer algunos (o ninguno) de los 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 grafo es plano si no contiene como menor ni el grafo bipartito completo K _3,3 (ver el Problema de las tres casas) ni el grafo completo K ₅.

Un problema similar, el problema de contención de subdivisión, es encontrar un gráfico fijo como una subdivisión de un gráfico dado. Una subdivisión u homeomorfismo de un gráfico es cualquier gráfico obtenido al subdividir algunas (o ninguna) aristas. La contención de la subdivisión está relacionada con las 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 de subdivisión es la conjetura de Kelmans-Seymour:

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

Otra clase de problemas tiene que ver con la medida en que varias especies y generalizaciones de grafos están determinadas por sus subgrafos con puntos eliminados. Por ejemplo:

La conjetura de la reconstrucción

Colorear gráfico

Muchos problemas y teoremas en la teoría de grafos tienen que ver con varias formas de colorear gráficos. Por lo general, uno está interesado en colorear un gráfico para 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 (sin resolver)
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 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, se incluyen 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 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 marcos de restricción que son estrictamente compositivos, la unificación de grafos es la función suficiente de satisfacibilidad y combinación. 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 de Steiner
Problema de las tres cabañas
Problema del viajante de comercio (NP-difícil)

Flujo de red

Son numerosos los problemas derivados sobre todo 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 del guardia del museo

Cubrir 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 vecindarios cerrados.
El problema de cobertura de vértices es el caso especial del problema de cobertura de conjunto donde los conjuntos a cubrir son todos los bordes.
El problema de cobertura del conjunto original, también llamado conjunto de aciertos, se puede describir como una cobertura de vértice en una hipergrafía.

Problemas de descomposición

La descomposición, definida como la partición del 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), tiene una amplia variedad de preguntas. A menudo, el problema es descomponer un gráfico en subgráficos isomorfos a un gráfico fijo; por ejemplo, descomponer un gráfico completo en ciclos hamiltonianos. Otros problemas especifican una familia de grafos en los que debe descomponerse un gráfico dado, por ejemplo, una familia de ciclos, o descomponer un grafo completo K _n en n − 1 árboles especificados que tienen, respectivamente, 1, 2, 3,..., n − 1 aristas.

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

Arboricidad, una descomposición en la menor cantidad de bosques posible
Cycle double cover, 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 coincidencias
Factorización de gráficos, una descomposición de un gráfico regular en subgráficos regulares de grados dados

Clases de gráficos

Muchos problemas involucran la caracterización de los miembros de varias clases de grafos. Algunos ejemplos de tales preguntas se encuentran a continuación:

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

Contenido relacionado

Más resultados...