Teoría de grafos

La teoría de grafos es la disciplina matemática e informática que estudia los grafos , que son modelos abstractos de dibujos de redes que conectan objetos. Estos modelos se componen de los datos de vértices (también llamados nodos o puntos , con referencia a poliedros ) y aristas (también llamados enlaces o líneas ) entre estos vértices; estas aristas a veces no son simétricas (entonces se dice que los gráficos están orientados ) y se denominan flechas o arcos .

Los algoritmos desarrollados para resolver problemas relacionados con los objetos de esta teoría tienen numerosas aplicaciones en todas las áreas relacionadas con la noción de red ( red social , red informática , telecomunicaciones , etc.) y en muchas otras áreas (por ejemplo, genética ) como el concepto de gráfico. , aproximadamente equivalente al de la relación binaria (que no debe confundirse con el gráfico de una función ), es general. Teoremas grandes y difíciles, como el teorema de los cuatro colores , el teorema del gráfico perfecto o el teorema de Robertson-Seymour , han ayudado a establecer este tema con los matemáticos, y las cuestiones que deja abiertas, como la conjetura de Hadwiger , lo hacen una rama viva de las matemáticas discretas .

Definiciones

Existen varias variaciones en la definición de gráficos en la teoría de grafos. Las definiciones más comunes son las siguientes.

Grafico

En un sentido restringido pero muy extendido del término, un gráfico es un par G = ( V , E ) que comprende

Para evitar dudas, este tipo de objeto se puede llamar precisamente un gráfico simple no dirigido .

En borde { x , Y } , los vértices x y y son llamados los extremos o vértices extremos del borde. Decimos que el borde se une a X y Y y es incidente en x y en y . Un vértice puede existir en un gráfico sin un borde incidente. Las aristas múltiples son dos o más aristas que unen los mismos dos vértices; no pueden existir en un simple gráfico no dirigido.

En un sentido más general del término que permite múltiples aristas, un gráfico es un triplete G = ( V , E , ϕ ) que comprende

Para evitar dudas, 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 como se definen en las dos definiciones anteriores no pueden tener bucles, porque un bucle que une un vértice x es el borde (para un gráfico simple no orientado) o es incidente (para un multigrafo no orientado) { x , x } = { x } que es no en {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} . Entonces, para permitir bucles, las definiciones deben ampliarse. Para gráficos simples no dirigidos, E ⊆ {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} debe convertirse en E ⊆ {{ x , y } | ( x , y ) ∈ V 2 } . Para multigrafos no dirigidos, ϕ : E → {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} debe convertirse en ϕ : E → {{ x , y } | ( x , y ) ∈ V 2 } . Para evitar dudas, estos tipos de objetos se pueden denominar precisamente un gráfico simple no dirigido con bucles y un multigraph no dirigido con bucles respectivamente.

Generalmente se supone que V y E son finitos, y muchos resultados dejan de ser verdaderos (o tienen declaraciones diferentes) para gráficas infinitas porque algunos argumentos de prueba no se traducen al caso infinito. Además, a menudo se supone que V no está vacío, pero E puede ser el conjunto vacío. El orden de un gráfico | V | es 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 incidentes a ese vértice, donde un bucle cuenta el doble.

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

Los bordes E de un grafo no dirigido G inducir una relación binaria simétrica en ~ V llama la relación de adyacencia de G . Específicamente, para cada arista { x , y } , sus vértices extremos x y y se dice que son adyacentes a la otra, que se denota x ~ y .

Gráfico orientado

Un gráfico dirigido es un gráfico en el que los bordes tienen una orientación.

En un sentido restringido pero muy extendido del término, un gráfico dirigido es un par G = ( V , A ) (a veces G = ( V , E ) ) que comprende

Para evitar dudas, este tipo de objeto se puede llamar precisamente un gráfico simple dirigido .

En la flecha ( x , y ) orientado de x a y , x se llama la cola de la flecha y y la cabeza de la flecha. La flecha ( y , x ) se llama flecha inversa de ( x , y ) .

En un sentido más general del término que permite múltiples flechas, un gráfico dirigido es un triplete G = ( V , A , ϕ ) (a veces G = ( V , E , ϕ ) ) que incluye

Para evitar dudas, este tipo de objeto puede denominarse precisamente un multigrafo orientado .

Los gráficos dirigidos como se definen en las dos definiciones anteriores no pueden tener bucles, porque un bucle que une un vértice x es la flecha (para un gráfico dirigido simple) o es incidente en (para un multigraph dirigido) ( x , x ) que no está en { ( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} . Entonces, para permitir bucles, las definiciones deben extenderse. Para gráficos orientados simples, A ⊆ {( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} debe convertirse en A ⊆ V 2 . Para multigrafos orientados, ϕ : A → {( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} debe convertirse en ϕ : A → V 2 . Para evitar dudas, estos tipos de objetos pueden denominarse precisamente un gráfico dirigido simple con bucles y un multigraph dirigido con bucles (o un carcaj ) respectivamente.

Un gráfico dirigido simple con bucles es una relación homogénea (una relación binaria entre un conjunto y él mismo). Un simple gráfico dirigido con bucles G = ( V , A ) se denomina simétrica si para cada flecha A , la correspondiente inversa flecha también en A .

Topologías

Hay tres familias principales de gráficos y cinco categorías en total:

Orígenes

Un artículo del matemático suizo Leonhard Euler , presentado a la Academia de San Petersburgo en 1735 y luego publicado en 1741, trata el problema de los siete puentes de Königsberg , como se muestra esquemáticamente a continuación. El problema era encontrar un paseo desde un punto dado que regresara a ese punto pasando una vez y solo una vez por cada uno de los siete puentes de la ciudad de Königsberg. Un camino que pasa a través de cualquier cresta exactamente una vez se llama camino euleriano , o circuito euleriano si termina donde comenzó. Por extensión, un gráfico que admite un circuito euleriano se denomina gráfico euleriano , que por lo tanto constituye el primer caso de propiedad de un gráfico. Euler había formulado que una gráfica es euleriana solo si cada vértice tiene un número par de aristas. La costumbre es referirse a él como el teorema de Euler , aunque la prueba no fue proporcionada hasta 130 años después por el matemático alemán Carl Hierholzer . Un problema similar es pasar por cada vértice exactamente una vez, y fue resuelto primero con el caso especial de un caballo que tenía que visitar cada casilla de un tablero de ajedrez por el teórico árabe del ajedrez Al-Adli en su trabajo Kitab ash -shatranj publicado alrededor de 840 y perdido desde entonces. Recorrido del caballo fue estudiada con más detalle en la XVIII ª  siglo por el matemático francés Alexandre-Théophile Vandermonde , Pierre Rémond de Montmort y Abraham de Moivre ; El matemático británico Thomas Kirkman estudió el problema más general de la ruta en la que solo se puede pasar un vértice una vez, pero tal ruta finalmente tomó el nombre de camino hamiltoniano en honor al matemático irlandés William Rowan Hamilton , y aunque este último estudió solo un caso particular. Por tanto, concedemos a Euler el origen de la teoría de grafos porque fue el primero en proponer un tratamiento matemático de la cuestión, seguido de Vandermonde.


Puentes Konigsberg.png7 puentes.svgKönigsberg graph.svg

En medio de la XIX ª  siglo, los británicos matemático Arthur Cayley estaba interesado en los árboles , que son un tipo especial de gráfico con ningún ciclo, es decir, en la que es imposible volver a un punto de partida sin hacer el camino inverso. En particular, estudió el número de árboles con n vértices y demostró que hay algunos . Esto constituyó "una de las fórmulas más bellas de la combinatoria enumerativa", un campo que consistía en contar el número de elementos en un conjunto finito, y también abrió el camino a la enumeración de gráficas con ciertas propiedades. Este campo de investigación fue realmente iniciado por el matemático húngaro George Pólya , quien publicó en 1937 el teorema de conteo que lleva su nombre , y el matemático holandés Nicolaas Govert de Bruijn . El trabajo de Cayley, como el de Polya, tenía aplicaciones a la química, y el matemático inglés James Joseph Sylvester , coautor de Cayley, introdujo en 1878 el término "grafo" basado en la química:

“Puede que no carezca del todo de interés para los lectores de Nature el darse cuenta de una analogía que recientemente me impresionó mucho entre ramas del conocimiento humano aparentemente tan diferentes como la química y el álgebra moderna. […] Cada invariante y covariante por lo tanto se vuelve expresable por un gráfico exactamente idéntico a un diagrama o químicograma de Kékuléan. "

Uno de los problemas más conocidos en la teoría de grafos proviene de la coloración de grafos , donde el objetivo es determinar cuántos colores diferentes son suficientes para colorear completamente un gráfico de modo que ningún vértice tenga el mismo color que sus vecinos. En 1852, el matemático sudafricano Francis Guthrie planteó el problema de los cuatro colores en una discusión con su hermano, quien le preguntó a su maestro Auguste De Morgan si se podía colorear algún mapa con cuatro colores para que los países vecinos tuvieran colores diferentes. De Morgan primero envió una carta al matemático irlandés William Rowan Hamilton , que no estaba interesado, y luego el matemático inglés Alfred Kempe publicó pruebas erróneas en el American Journal of Mathematics , que acababa de ser fundado por Sylvester. El estudio de este problema condujo a muchos desarrollos en la teoría de grafos, por Peter Guthrie Tait , Percy John Heawood , Frank Ramsey y Hugo Hadwiger .

Los problemas de la factorización de las gráficas de este modo surgieron a finales del XIX e  siglo por estar interesado en los subgrafos que abarca, es decir, en los gráficos que contienen todos los vértices, pero sólo una parte de los bordes. Un subgrafo de expansión se llama factor k si cada uno de sus vértices tiene k aristas y los primeros teoremas fueron dados por Julius Petersen  ; por ejemplo, mostró que un gráfico se puede dividir en 2 factores si y solo si todos los vértices tienen un número par de aristas (pero Bäbler tardó 50 años en lidiar con el caso impar). El trabajo de Ramsey sobre la coloración, y en particular los resultados del matemático húngaro Pal Turan , permitieron el desarrollo de la teoría de grafos extremos centrándose en grafos que alcanzan el máximo de una cantidad particular (por ejemplo, el número de aristas) con restricciones dadas, como la ausencia de ciertos subgrafos.

En la segunda mitad del XX °  siglo, el matemático francés Claude Berge contribuye al desarrollo de la teoría de grafos por sus contribuciones en los gráficos perfectos y la introducción del término de hypergraph (tras la intervención de Jean-Marie Pla el que han utilizado en una seminario) con una monografía sobre el tema. Su libro de introducción a la teoría de grafos también ofreció una alternativa original, que consistía más en un paseo personal que en una descripción completa. También marcará la investigación francesa en este campo, mediante la creación conjunta con Marcel-Paul Schützenberger de un seminario semanal en el Instituto Henri Poincaré, reuniones los lunes en la Maison des Sciences de l'Homme, y la dirección del equipo combinatorio de París.

Flujos en redes

Los alemanes Franz Ernst Neumann y Jacobi , físico y matemático respectivamente, fundaron una serie de seminarios en 1834. El físico alemán Gustav Kirchhoff fue uno de los estudiantes que asistieron al seminario entre 1843 y 1846, y extendió el trabajo de Georg Ohm para establecer en 1845 las leyes de Kirchhoff que expresan la conservación de energía y carga en un circuito eléctrico . En particular, su ley de los nodos establece que la suma de las intensidades de las corrientes que entran en un nodo es igual a la que sale de él. Un circuito eléctrico puede verse como un gráfico, en el que los vértices son los nodos del circuito y los bordes corresponden a las conexiones físicas entre estos nodos. Para modelar las corrientes que fluyen por el circuito, se considera que cada borde puede ser atravesado por un flujo . Esto ofrece muchas analogías, por ejemplo, con el flujo de un líquido como el agua a través de una red de canales o la circulación en una red de carreteras. Según lo estipulado por la ley de los nodos, el flujo en un vértice se conserva, o es idéntico en la entrada que en la salida; por ejemplo, el agua que entra en un canal no desaparece y el canal no produce nada, por lo que hay tanta agua que sale como que entra. Además, un borde tiene un límite de capacidad, al igual que un canal puede transportar una cierta cantidad máxima de agua. Si agregamos que el flujo comienza en un cierto vértice (la fuente ) y que termina en otro (el sumidero ), entonces obtenemos los principios fundamentales del estudio de flujos en un gráfico.

Si consideramos que la fuente es un campo petrolero y que el pozo es la refinería donde se drena, entonces queremos ajustar las válvulas para tener el mejor flujo posible de la fuente al pozo. Es decir, se busca tener un uso lo más eficiente posible de la capacidad de cada uno de los bordes, que es el problema de máximo caudal . Supongamos que “cortamos” el gráfico en dos partes, de modo que la fuente esté en una y el sumidero en la otra. Cada flujo debe pasar entre las dos partes y, por lo tanto, está limitado por la capacidad máxima que una parte puede enviar a la otra. Encontrar el corte con menor capacidad indica por tanto el lugar donde la red es más limitada, lo que equivale a establecer el caudal máximo que puede atravesarla. Este teorema se llama flow-max / cut-min y se estableció en 1956.

El estudio de los flujos de red se generaliza de varias formas. La búsqueda de un máximo, aquí en el caso del flujo, es un problema de optimización , que es la rama de las matemáticas que consiste en optimizar ( es decir, encontrar un mínimo o un máximo) una función bajo ciertas restricciones. Un flujo de red está sujeto a tres restricciones: el límite de capacidad en cada borde, la creación de un flujo distinto de cero entre la fuente y el sumidero ( es decir, la fuente crea un flujo) y la igualdad del flujo de entrada / salida para cualquier vértice distinto de la fuente y los sumideros ( es decir , no consumen ni generan parte del caudal). Siendo estas restricciones lineales , el problema de un flujo de red es parte de la optimización lineal . También es posible agregar otras variables al problema para tener en cuenta más situaciones: así podemos tener varias fuentes y sumideros  (in) , una capacidad mínima  (in) en cada borde, un costo al usar un borde o una amplificación del flujo  ( pasando ) a través de un borde.

Introducción de probabilidades

Hasta mediados del XX °  siglo, la construcción de un algoritmo gráfico no fue al azar: siempre que los parámetros proporcionados al algoritmo no ha cambiado, entonces la gráfica se construyó fue el mismo. Luego se introdujo una cierta dosis de aleatoriedad y los algoritmos se volvieron probabilísticos . El matemático de origen ruso Anatol Rapoport tuvo esta idea por primera vez en 1957 pero fue propuesta de forma independiente dos años después, de forma más formal, por los matemáticos húngaros Paul Erdős y Alfréd Rényi . Se preguntaron cómo sería un gráfico “típico” con n vértices y m aristas. Querían saber qué propiedades se podían encontrar con n vértices y m aristas creadas al azar. Dado que una cantidad fija m no es práctico para responder a esta pregunta, se decidió que cada borde existiría con una probabilidad p . Este fue el comienzo de la teoría de grafos aleatorios , donde consideramos un número de vértices n lo suficientemente grande, y estamos interesados ​​en la probabilidad p suficiente para que el grafo tenga una determinada propiedad.

Erdős y Rényi descubrieron que la gráfica no evolucionaba linealmente, sino que había una probabilidad crítica p después de la cual cambiaba radicalmente. Este comportamiento es bien conocido en la física: si hay un vaso de agua que se pone en un congelador , no lo hace gradualmente se transforma en hielo en lugar abruptamente cuando la temperatura cae por debajo de 0  ° C . El agua tenía dos fases (líquido y hielo) y pasa de una a la otra por un fenómeno llamado fase de transición, la transición de ser rápido en torno a un punto crítico , que es en este caso la temperatura de 0  ° C . Para muchas propiedades observadas, los gráficos aleatorios funcionan de la misma manera: existe una probabilidad crítica por debajo de la cual están en una fase subcrítica y por encima de la cual pasan en una fase supercrítica. En el caso de un gráfico aleatorio, la probabilidad de que observemos la propiedad que nos interesa es baja en la fase subcrítica, pero se vuelve muy alta ( es decir, casi certeza) en la fase sobrecrítica; la gráfica de la probabilidad de tener la propiedad en función de p tiene por tanto un aspecto muy particular, simplificado en el diagrama de la derecha.

Más allá del vocabulario común de fases, la teoría de los gráficos aleatorios se encuentra en la física estadística en forma de teoría de la percolación . Este último originalmente tenía como objetivo estudiar el flujo de un fluido a través de un material poroso . Por ejemplo, si sumergimos una piedra pómez en un cubo lleno de agua, nos interesa cómo fluirá el agua a través de la piedra. Para modelar este problema, nos centramos en los parámetros importantes: la edad o el color de la piedra no importa, mientras que las aberturas o 'canales' por los que puede circular el agua son fundamentales. La abstracción más simple es pensar en una piedra como una cuadrícula, donde cada canal existe con una probabilidad p . Así encontramos el modelo del grafo aleatorio, pero con una restricción espacial  : un borde solo puede existir entre dos vértices si son vecinos en la cuadrícula. Sin embargo, esta restricción puede eliminarse para establecer una equivalencia entre la teoría de los gráficos y la de la percolación. Primero, una gráfica de n vértices se puede representar mediante una cuadrícula con n dimensiones; ya que nos interesa el caso donde n es suficientemente grande, es decir , esto establece una equivalencia con la percolación en dimensión infinita. Además, existe una dimensión crítica tal que el resultado ya no depende de la dimensión tan pronto como se alcanza  ; Se cree que esta dimensión crítica es 6, pero solo se pudo probar para 19.

Se han propuesto muchos modelos desde principios de la década de 2000 para encontrar fenómenos observados en gráficos como el que representa conexiones entre actores de Hollywood (obtenido por IMDb ) o partes de la Web . En 1999, Albert-László Barabási y Réka Albert explicaron que uno de estos fenómenos “es consecuencia de dos mecanismos: la red crece continuamente con la adición de nuevos picos, y los nuevos picos se unen con ciertas preferencias a otros que ya están bien en su lugar ". Una cierta confusión se instaló en torno a su modelo: si realmente permite obtener el fenómeno deseado, no es el único modelo que llega a este resultado y, por lo tanto, no podemos concluir viendo el fenómeno que resulta de un proceso de apego preferencial. Los fenómenos de mundo pequeño y libertad de escala , para los que se han propuesto muchos modelos, se pueden lograr simplemente mediante gráficos aleatorios: la técnica de Michael Molloy y Bruce Reed permite obtener el efecto de libre de escala, mientras que la de Li , Leonard y Loguinov conduce al mundo pequeño.

Representaciones e invariantes

Etiquetado y morfismos

Formalmente, un gráfico está etiquetado  : cada vértice o borde pertenece a un conjunto, por lo tanto lleva una etiqueta . Normalmente, los gráficos se etiquetan con números enteros, pero una etiqueta puede pertenecer a cualquier conjunto: conjunto de colores, conjunto de palabras, conjunto de números reales. Los ejemplos de al lado muestran gráficos etiquetados con números enteros y letras. El etiquetado de un gráfico se puede diseñar para proporcionar información útil para problemas como el enrutamiento  : partiendo de un vértice , queremos llegar a un vértice , es decir, queremos enrutar información de a . Dependiendo de cómo estén etiquetados los vértices, las etiquetas que llevan y pueden permitirnos encontrar fácilmente un camino. Por ejemplo, en el gráfico de Kautz (in) donde está la distancia máxima entre dos vértices , imagine que estamos en un vértice etiquetado y al que queremos ir  : simplemente cambie la etiqueta ingresando el destino, lo que da la forma 

Esta ruta dice lo siguiente: si estás en la parte superior etiquetada, entonces vas al vecino con la etiqueta , y así sucesivamente.

Sin embargo, nos enfrentamos a un problema: si miramos por encima de la ilustración de la lista de árboles con 2, 3 y 4 vértices, muchos de ellos tienen exactamente la misma estructura pero un etiquetado diferente (dado aquí por colores). Para estudiar solo la estructura, necesitamos, por tanto, una herramienta que permita ignorar el etiquetado, es decir, dar una equivalencia estructural. Para ello, introducimos la noción de morfismo. Un morfismo de gráfico , u homomorfismo de gráfico , es una aplicación entre dos gráficos que respeta la estructura de los gráficos. En otras palabras, la imagen de la gráfica en debe respetar la relaciones de adyacencia presente en . Más precisamente, si y son dos grafos, una aplicación es un morfismo de grafos si donde transforma los vértices de G en los de H, y las aristas de G en las de H respetando la siguiente restricción: si hay una arista entre dos vértices de entonces debe haber una arista entre los dos vértices correspondientes de . Decimos del homomorfismo que es una inyección (respectivamente sobreyección ) si sus dos funciones y son inyectivas (respectivamente sobreyectiva); si son tanto inyectivos como sobreyectivos, es decir , biyectivos , entonces es un isomorfismo gráfico . Si dos gráficos son isomórficos, entonces tienen la misma estructura: no importa cómo se dibujen o etiqueten, es posible mover los vértices o cambiar las etiquetas para que uno sea una copia al carbón del otro, como se ilustra a continuación. Luego denotamos mediante un gráfico sin etiquetar la clase de equivalencia de un gráfico para la relación de isomorfismo. Entonces, dos gráficos isomórficos se considerarán iguales si los consideramos gráficos sin etiquetar.

Gráfico G Gráfico H Isomorfismo
entre G y H
Graficar isomorfismo a.svg Graficar isomorfismo b.svg






El gráfico de palabras puede designar, según el contexto, un gráfico etiquetado o no etiquetado. Cuando hablamos del gráfico web, las etiquetas son URL y tienen un significado. La palabra se usa para denotar un gráfico etiquetado. Por el contrario, el gráfico de Petersen siempre se considera hasta el isomorfismo, por lo tanto, sin etiquetar, solo sus propiedades estructurales son de interés.

Gráficos y álgebra lineal

Cualquier gráfico se puede representar mediante una matriz . Las relaciones entre aristas y vértices, llamadas relaciones de incidencia, están todas representadas por la matriz de incidencia del gráfico. Las relaciones de adyacencia (si dos vértices están conectados por un borde, son adyacentes) están representados por su matriz de adyacencia . Está definido por


Grafico Representación mediante una matriz de adyacencia Representación mediante una matriz laplaciana (no normalizada)
6n-graf.svg

Una gran cantidad de información en un gráfico se puede representar mediante una matriz. Por ejemplo, la matriz de grados es una matriz diagonal donde los elementos corresponden al número de conexiones del vértice , es decir a su grado . Utilizando esta matriz y la anterior, también podemos definir la matriz laplaciana  ; obtenemos su forma normalizada por , donde denota la matriz identidad , o también podemos obtenerla directamente por cada uno de sus elementos:

Estas representaciones dependen de cómo se etiqueten los vértices del gráfico. Imaginemos que mantenemos la misma estructura que en el ejemplo anterior y que invertimos las etiquetas 1 y 6  : luego invertimos las columnas 1 y 6 de la matriz de adyacencia. Sin embargo, hay cantidades que no dependen de cómo etiquetemos los vértices, como el grado mínimo / máximo / promedio del gráfico. Estas cantidades son invariantes del gráfico: no cambian según la numeración. Mientras que una adyacencia o matriz laplaciana varía, su espectro , es decir, el conjunto de sus valores propios , es invariante. El estudio de la relación entre los espectros y las propiedades de un gráfico es el tema de la teoría de los gráficos espectrales  ; entre las razones interesantes, el espectro da información sobre el número cromático , el número de componentes conectados y los ciclos del gráfico.

Descomposiciones de árboles y ramas

Dado que los gráficos pueden representar muchas situaciones, existen muchos algoritmos ( es decir, programas) que los utilizan. La complejidad de un algoritmo consiste esencialmente en saber, para un problema dado, cuánto tiempo es necesario para resolverlo y cuál es el espacio de la máquina que utilizará. Algunas representaciones gráficas proporcionan un mejor rendimiento, es decir, el problema se resuelve más rápido o ocupan menos espacio. En algunos casos, un problema NP-completo (clase más difícil) en una representación de un gráfico se puede resolver en tiempo polinomial (clase simple) con otra representación; la idea no es que basta con mirar el gráfico de otra manera para resolver el problema más rápido, sino que uno "paga" para transformarlo y que luego "ahorra" para resolver el problema. Una de esas transformaciones es la descomposición de árboles propuesta por los matemáticos Robertson y Seymour en su serie Graph Minors . Intuitivamente, una descomposición de árbol representa el gráfico original por un árbol, donde cada vértice corresponde a un subconjunto de los vértices de G, con algunas restricciones. Formalmente, para un gráfico dado , su descomposición de árbol es donde está un árbol y una función que asocia con cada vértice un conjunto de vértices . Deben cumplirse tres restricciones:

El ancho del árbol de una descomposición de un gráfico es , es decir, el tamaño del conjunto más grande representado por un vértice menos 1; podemos verlo como la máxima abstracción: para una parte superior del árbol, ¿hasta cuántos vértices del gráfico representamos? Construir la descomposición del árbol de cualquier gráfico con el menor ancho de árbol es un problema NP-difícil. Sin embargo, esto se puede hacer rápidamente para algunos gráficos, o aproximarse para otros, como gráficos planos ( es decir, se puede dibujar sin cruzar dos bordes).

Robertson y Seymour también desarrollaron el concepto de ramificación . Para entenderlo, debes introducir más vocabulario en un árbol. En las gráficas se dibuja un árbol "al revés": partimos de la raíz en la parte superior, y descendemos hasta llegar a las hojas en la parte inferior; cualquier vértice que no sea una hoja se denomina "nodo interno". La descomposición en ramas da como resultado un árbol en el que cada nodo interno tiene exactamente tres vecinos (como en el ejemplo de al lado), y donde cada hoja representa un borde del gráfico original. Se anota la profundidad mínima de descomposición de un gráfico y tenemos la relación . En cuanto a la descomposición de árboles, es NP-difícil construir una descomposición de ramas con un mínimo para cualquier gráfico; en este caso, esta construcción es factible para un gráfico plano .

Estas representaciones se utilizan en problemas NP-completos mediante técnicas de programación dinámica , que generalmente toman un tiempo exponencial en o . Tal problema es, por ejemplo, el conjunto dominante  : queremos saber si hay un subconjunto de vértices de tamaño como máximo tal que un vértice que no esté en y esté conectado por una arista. Si la gráfica es plana, esta técnica permite resolver el problema a tiempo .

Aspecto algorítmico

Estructuras de datos

La forma en que se representa el gráfico como un objeto matemático se discutió en la sección anterior. En el aspecto algorítmico de la teoría de grafos, buscamos diseñar un proceso eficiente para lidiar con un problema que involucra un grafo. Los principales criterios para la eficiencia de un proceso son el tiempo necesario para obtener la respuesta y el espacio que consume el proceso en su trabajo. La forma en que representamos el gráfico influye en el rendimiento en el tiempo y el espacio: por ejemplo, si queremos saber la existencia de una arista entre dos vértices, la matriz de adyacencia permitirá obtener un resultado de forma inmediata, a esto que llamamos en . Por otro lado, una operación básica como encontrar el vecino de un vértice está en una matriz de adyacencia: en el peor de los casos, será necesario escanear toda la columna para encontrar que no hay ningún vecino. Otra estructura de datos es la lista de adyacencia , que consiste en una matriz cuya entrada da la lista de vecinos del vértice  : en tal estructura, la búsqueda de un vecino se realiza mientras la existencia de un borde está adentro . Así, en términos de tiempo, la elección de la estructura depende de las operaciones básicas que se desee optimizar.

Representación por lista de adyacencia del gráfico opuesto:
0 adyacente a 0,1,2,3
1 adyacente a 0
2 adyacente a 0.3.4
3 adyacente a 0,2
4 adyacente a 2

Asimismo, el espacio que consume una estructura depende del tipo de gráfico considerado: un atajo abusivo consiste en decir que una lista de adyacencias consume menos espacio que una matriz porque esta última será escasa , pero que toma por ejemplo más espacio para almacenar una matriz. gráfico aleatorio con las listas que con una matriz; en el caso general, una matriz usa espacio y, por lo tanto, las listas usan si el gráfico es denso, entonces puede ser lo suficientemente grande como para que una matriz consuma menos espacio, y si el gráfico es escaso, las listas consumirán menos espacio. Las modificaciones simples de una estructura de datos pueden permitir tener una ganancia apreciable: por ejemplo, en una representación parcialmente complementada de una lista, un bit especial indica si la lista es la de los vecinos presentes o ausentes; esta técnica permite tener algoritmos lineales sobre el complemento de un gráfico.

Si bien estas estructuras son locales, también existen estructuras de datos distribuidos . El principio de estas estructuras es diseñar un esquema de etiquetado tal que, para dos vértices y , se pueda responder una pregunta como "cuál es la distancia entre y  " solo usando las etiquetas de estos nodos; tal uso de etiquetas se vio en la sección “  Etiquetado y morfismos  ” con el gráfico de Kautz donde podemos deducir el camino entre dos vértices solo gracias a su etiqueta, y la longitud de este camino nos da la distancia. El etiquetado es efectivo si permite que una pregunta determinada se responda solo mediante el uso de dos etiquetas, al tiempo que minimiza el número máximo de bits para una etiqueta. Además de la distancia, una pregunta típica puede ser probar la adyacencia, es decir saber si dos vértices están cerca; tenga en cuenta que esto también se reduce al caso especial de una distancia 1. El primer ejemplo de etiquetado eficiente para probar la adyacencia se propuso en el caso de árboles, y cada etiqueta consta de dos partes de bits: la primera parte identifica el vértice y un número hasta requiere la codificación de bits , mientras que la segunda parte identifica al padre de ese vértice; para probar la adyacencia, usamos el hecho de que dos vértices son vecinos en un árbol si y solo si uno es el padre del otro.

Subgrafos útiles: separadores, llaves inglesas y árboles Steiner

La efectividad de un esquema de etiquetado está relacionada con el tamaño de los separadores en el gráfico.

Definición  :  un separador es un subconjunto de vértices que "divide" los vértices del gráfico en dos componentes y de tal manera que y no hay bordes entre los vértices de y .

Si un gráfico tiene separadores de tamaño , entonces podemos, por ejemplo, diseñar etiquetas de bits para la distancia; esto permite deducir directamente el etiquetado para gráficos para los que se conoce el tamaño de los separadores, como un gráfico plano donde el separador es de tamaño . Finalmente, no solo debemos considerar el tamaño del etiquetado sino también el tiempo requerido, dadas dos etiquetas, para realizar la decodificación respondiendo a la pregunta ( es decir, ¿cuál es la distancia? ¿Son vecinos?).

Reducción de datos

Muchos problemas de gráficos son NP-completos, es decir, difíciles de resolver. Sin embargo, esta dureza es desigual: algunas partes del problema pueden ser particularmente duras y, por lo tanto, constituyen su núcleo, mientras que otras son bastante fáciles de abordar. Entonces, antes de ejecutar un algoritmo en un problema que puede ser difícil, es mejor dedicar un tiempo a reducir ese problema para que solo tenga que considerar su núcleo.

Conceptos relacionados

Notas

  1. Hay otros objetos matemáticos con el mismo nombre, por ejemplo gráficos de funciones , pero estos tienen poco que ver con los gráficos aquí estudiados.
  2. (en) Edward A. Bender y S. Gill Williamson , Listas, decisiones y gráficos: con una introducción a la probabilidad ,2010, 251  p. ( leer en línea ) , pág.  148
  3. Por ejemplo ( Iyanaga y Kawada 1977 , p.  234) o ( Biggs 1993 , p.  4).
  4. (en) Edward A. Bender y S. Gill Williamson , Listas, Decisiones y gráficos: Con una Introducción a la probabilidad ,2010, 251  p. ( leer en línea ) , pág.  149
  5. Por ejemplo ( Graham et. Al. 1995 , p.  5).
  6. (en) Edward A. Bender y S. Gill Williamson , Listas, decisiones y gráficos: con una introducción a la probabilidad ,2010, 251  p. ( leer en línea ) , pág.  161
  7. Con respecto a las matemáticas modernas, la formulación de Euler es una conjetura ya que el resultado se establece sin prueba. Sin embargo, la matemática de su época no presentaba el mismo rigor: si bien ahora conjeturar un resultado significa que uno renuncia a probarlo, para Euler la ausencia de una prueba puede significar que ésta no se considerara útil.

Referencias

Orígenes

  1. (La) Leonhard Euler - Solutio problematis ad geometriam situs relatedis , Commentarii academiae scientiarum Petropolitanae 8 , 1741, páginas 128-140.
  2. (De) Carl Hierholzer, "  Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren  ", en Mathematische Annalen , vol. 6, 1873, pág.  30-32
  3. (en) Martin G. - El papel árabe en el desarrollo del Ajedrez , Al Shindagah 45, marzo-abril de 2002
  4. Alexandre-Théophile Vandermonde , "Observaciones sobre problemas de situación", en Mémoires de l'Académie Royale des Sciences , 1771, p.  566-574 . Referencias de (ru) LJ.Rossia.org
  5. (en) William Tutte - Teoría de grafos como la he conocido, Publicaciones científicas de Oxford , Clarendon Press, 1998 ( ISBN  978-0-19-850251-7 ) . Capítulo 2: Caballero Errante .
  6. (en) Arthur Cayley , "  Sobre la teoría de las formas analíticas llamadas árboles caducados  " en Phil. revista , 1857, pág.  172-176
  7. Martin Aigner y Günter M. Ziegler, "  La fórmula del Cayley para el número de árboles  " en pruebas , 2 ª ed., 2006
  8. (en) James Joseph Sylvester , "  Química y álgebra  ", en la naturaleza , n o  17 de 7 de febrero de 1878, p. 284
  9. (en) Alfred Bray Kempe, "  Sobre el problema de los cuatro colores geográficos  " en American Journal of Mathematics , vol. 2, n o  3, septiembre 1879, p.  193-200
  10. (De) Julius Petersen, “  Die Theorie der regulären Graphen  ”, en Acta Mathematica , vol. 15, 1891, pág.  193-220
  11. (de) F. Bäbler, “Über die Zerlegung regulärer Streckencomplexe ungerader Ordnung”, en el comentario. Matemáticas. Helv. , Vuelo. 10, 1938, pág.  275–287
  12. (en) Béla Bollobás, Teoría de grafos extremos , Dover, 2004
  13. (en) Claude Berge , "Algunas clases de gráficos perfectos" en "Seis artículos eran teoría de gráficos" indio. Instituto de Estadística , Calcuta, 1969, pág.  1-21
  14. Claude Berge, Graphs et hypergraphes , Dunod, 1970
  15. Claude Berge, Teoría de los gráficos y sus aplicaciones , Dunod, 1958

Ondas

  1. (in) VV Ostapenko y AP Yakovleva, "Problemas matemáticos de modelado y control en problemas de distribución de agua" en Control Cybern. , Vuelo. 20, n o  4, 1991, p.  99-111
  2. (en) Kevin Wayne, Presentación de diapositivas con equivalencia entre la sección de flujo mínimo y máximo. Soporte de estudio para el libro Algorithm Design de Jon Kleinberg y Éva Tardos, Addison Wesley, 2005.
  3. (en) John W. Chinneck, Optimización práctica: una introducción suave , 2001, c. 10

Probabilidades

  1. (in) Anatol Rapoport, "Contribución a la teoría de la red aleatoria y sesgada" en el Bulletin of Mathematical Biology , vol. 19, n o  4, 1957
  2. (en) Paul Erdős y Alfréd Rényi, "Sobre gráficos aleatorios" en Publicationes Mathematicae , vol. 6, 1959. Véase también por los mismos autores: "Sobre la evolución de los gráficos aleatorios", en Publicaciones del Instituto de Matemáticas de la Academia de Ciencias de Hungría , vol. 5 de 1960.
  3. (en) Rick Durrett, Random Graph Dynamics , Cambridge Series in Statistical and Probabilistic Mathematics, 2006, c. 1
  4. (in) AV Lapshin, "La propiedad de las transiciones de fase en gráficos aleatorios" en Métodos probabilísticos en matemáticas discretas: Actas de la Tercera Conferencia Internacional Petrozavodsk , Petrozavodsk, Rusia, 12-15 de mayo de 1992
  5. (in) Béla Bollobás y Oliver Riordan, percolation , Cambridge University Press, 2006. Este libro presenta la teoría de la percolación con un enfoque basado en la teoría de grafos.
  6. (en) Harry Kesten, "¿Qué se está gestando? », En Avisos Amer. Matemáticas. Soc. , Vuelo. 53, n o  5, 2006
  7. (en) Takashi Hara y Gordon Slade , "Comportamiento crítico de campo medio para la percolación en grandes dimensiones", en Common. Matemáticas. Phys. , Vuelo. 128, 1990
  8. (in) Albert-László Barabási y Reka Albert, "Emergencia del escalado en redes aleatorias", en Science , n o  286 1999
  9. (en) Philippe Giabbanelli, Políticas de inmunización de mejora personal para epidemias en redes complejas , Tesis de maestría, Universidad Simon Fraser , 2009, bajo la dirección de Joseph G. Peters
  10. (en) Michael Molloy y Bruce A. Reed, "  Un elemento crítico para gráficos aleatorios con una secuencia dada de grado  " en Random Struct. Algoritmos , vol. 6, n o  2/3, 1995, p.  161–180
  11. (en) Xiafeng Li, Derek Leonard y Dmitry Loginov, "  Sobre la remodelación de los coeficientes de agrupamiento en generadores de topología basados ​​en grados  " en Algoritmos y modelos para Web-Graph , Berlín, Springer, 2004, p.  68-79

Representaciones

  1. JC. Bermond y col. , Comunicaciones en redes de procesadores , Masson, 1994 ( ISBN  978-2-225-84410-2 ) . Publicado bajo el seudónimo de Jean de Rumeur .
  2. (en) Pavol Hell y Jaroslav Nesetril, Gráficos y homomorfismos , Oxford University Press, 2004 ( ISBN  978-0-19-852817-3 )
  3. (en) Fan RK Chung, Teoría del gráfico espectral , coll. Serie Conferencia Regional en Matemáticas, n o  92, AMS 1997.
  4. (en) Neil Robertson y Paul D. Seymour , "Graph Minors II Algorithmic Aspects of Tree-Width", en Journal of Algorithms , vol. 7, n o  3, 1983
  5. (en) S. Arnborg DG Corneil y A. Proskurowski, "Complejidad de encontrar incrustación en un árbol k" en SIAM Journal on Discrete Mathematics , vol. 8, 1987, pág.  277-284
  6. (en) Hans L. Bodlaender, "Un algoritmo de tiempo lineal para encontrar la descomposición de árboles de pequeño ancho de árbol" en SIAM Journal on Computing , vol. 25, 1996, pág.  1305-1317
  7. (en) Paul D. Seymour y R. Thomas, "Enrutamiento de llamadas y el cazador de ratas" en combinatorica , vol. 14, n o  2, 1994 p.  217-241
  8. (in) QP Gu y H. Tamaki, "Descomposición óptima de la rama de gráficos planares en el tiempo", en Actas del 32º Coloquio Internacional sobre Autómatas, Lenguajes y Programación , LNCS 3580, Springer-Verlag, 2005, p.  373-384
  9. Para notaciones y técnicas, consulte (en) Qianping Gu Tree / Branch Decompositions and Their Applications , notas del curso en la Universidad Simon Fraser .

Aspecto algorítmico

  1. [PDF] (in) Elias Dahlhaus Jens Gustedt y Ross McConnell, "  Representaciones parcialmente complementadas de dígrafos  " en Matemáticas discretas e informática teórica , vol. 5, n o  1, 2002, p.  147-168
  2. (en) Stephen Alstrup y Theis Rauhe, "Representaciones gráficas y gráficas implícitas compactas universales inducidas por pequeños", en Actas del 43º Simposio anual de IEEE sobre fundamentos de la informática , 2002, p.  53-62
  3. (en) Sampath Kannan, Moni Naor y Steven Rudich, "Representación implícita de gráficos" en SIAM J. Math Discrete it. , Vuelo. 5, 1992, pág.  596-603
  4. (en) Cyril Gavoille, David Peleg, Stéphane Pérennes y Ran Razb "etiquetado de distancia en gráficos", en Journal of Algorithms , vol. 53, 2004, pág.  85-112

Bibliografía

Ver también

Artículos relacionados

enlaces externos