La investigación sobre la teoría matemática y los métodos de gráficos compuestos por nodos y aristas es una rama de la investigación de operaciones. Los elementos básicos de la teoría de grafos son los nodos y los bordes (también llamados líneas, arcos y ramas). Los nodos se usan para representar el objeto en estudio y los bordes se usan para representar una relación específica entre los objetos en estudio.

Por lo tanto, la teoría de grafos puede usar gráficos compuestos de nodos y aristas y teorías y métodos relacionados para describir, analizar y resolver varios problemas prácticos, como problemas relacionados en los campos de la física, química, biología, ciencias de la administración, métodos de computación y tecnología de ingeniería.

La teoría de grafos está estrechamente relacionada con las ramas de las matemáticas como la combinatoria, la programación lineal, la teoría de grupos, la teoría de matrices, la teoría de probabilidades y el análisis numérico.

En 1736, el matemático suizo L. Euler publicó el primer artículo sobre teoría de grafos, que resolvió el famoso problema de los siete puentes de Königsberg, por lo que se suele considerar a Euler como el fundador de la teoría de grafos. Hay siete puentes en el río Plegel que atraviesa Königsberg en Prusia Oriental, conectando las islas y las orillas del río (Figura 1).

Durante mucho tiempo, la gente ha estado discutiendo si es posible comenzar desde cualquiera de los cuatro terrenos, A, B, C y D, atravesar todos los puentes una vez y solo una vez, y finalmente regresar al original. tierra. En ese momento, Euler reemplazó cada pedazo de tierra con un punto, y reemplazó cada puente con un borde que conecta los dos puntos correspondientes, obteniendo así un “mapa” (Figura 2).

Euler propuso una regla general de juicio para gráficos generales: para comenzar desde un punto en el gráfico, atravesar todos los bordes una vez y solo una vez, y regresar al punto de partida original, el gráfico debe estar conectado y todos los puntos deben estar conectados.

Debe estar asociado con un número par de aristas. Obviamente, cada punto de la Figura 2 está conectado, pero cada punto no está conectado con un número par de aristas, por lo que el problema de los siete puentes no se puede resolver. En 1845, el físico alemán GR Kirchhoff creó la teoría del “árbol” para resolver una clase de ecuaciones lineales simultáneas.

Extrajo la red eléctrica y su resistencia, capacitancia e inductancia, y reemplazó la red eléctrica con una estructura combinada que consta solo de puntos y bordes, sin especificar el tipo de componentes eléctricos representados por cada borde, de modo que las ecuaciones se puedan comparar fácilmente.

El grupo está resuelto. La Figura 3 muestra una red eléctrica (
N ) y su diagrama básico (G ) y su árbol de expansión (T ). En 1852, F. Guthrie descubrió que no importa cuán complicado sea el mapa, solo cuatro colores pueden distinguir áreas adyacentes. Esta es la llamada “conjetura de los cuatro colores”.

Después de más de cien años de arduo trabajo, no fue hasta 1976 que K. Appel y W. Heken probaron el teorema de los cuatro colores con la ayuda de computadoras electrónicas. En 1856, WR Hamilton propuso un juego en una carta a RL Graves: usar 20 vértices en un dodecaedro regular para representar 20 ciudades, requiriendo que el jugador camine a lo largo de cada lado, camine por cada ciudad una vez y solo una vez, y finalmente regrese a la ciudad de salida original.

Este juego incita a las personas a estudiar cómo juzgar la naturaleza de una imagen y, de ser así, cómo determinar ese camino. Este es un problema que aún no se ha resuelto por completo (Figura 4).

En 1962, el matemático chino Guan Meigu planteó un llamado “problema postal chino”: el cartero tomó el correo de la oficina de correos, recorrió todas las calles bajo su jurisdicción y finalmente regresó a la oficina de correos. ruta y hacer que la distancia recorrida sea la más corta. En 1967, Edmunds dio una buena solución al problema postal chino. En 1936, D. König publicó su primer libro sobre teoría de grafos.

Desde la década de 1960, la teoría de grafos se ha utilizado ampliamente en diversas disciplinas. La teoría de grafos también ha recibido nuevos desarrollos en la teoría, por ejemplo, W. Tout y otros desarrollaron la teoría matroide, C. Berger y otros desarrollaron la teoría del hipergráfico y P. Erdsch y otros desarrollaron la teoría de grafos extremos.

El gráfico estudiado en la teoría de grafos es el conjunto de nodos y aristas, denotado como
G = ( V, E ), donde V representa el conjunto de nodos no vacíos y E representa el conjunto de aristas. En la Figura 5,

Los conceptos comúnmente utilizados en la investigación de gráficos son: Número de nodos y número de aristas:el número de elementos delconjunto V se denominanúmero de nodos delgráfico G ;el número de elementos delconjunto E se denomina númerode bordes en elgráfico G. Puntos finales y aristas asociadas: sie = [v i , v j ]E , llamado punto V I V J son los extremos e , y dicho e es elborde asociadodel puntoV I V J. Puntos adyacentes y bordes adyacentes: si v i v j están relacionados con el mismo borde, entonces v i v j son puntos adyacentes; si e i e j tienen un punto final común, entonces si e i ye j Es el lado adyacente.

Anillo y aristas múltiples: si los dos extremos de una arista pertenecen al mismo nodo, entonces la arista se llama anillo; si hay más de una arista entre los dos puntos finales, se llama arista múltiple. Gráficos múltiples y gráficos simples: los gráficos con múltiples aristas se denominan multigrafos; los gráficos sin bucles y sin aristas múltiples se denominan gráficos simples. Veces: El número de aristas con el punto
v como punto final se denomina orden de este punto, denotado como
d (v ).

En la Figura 5,d (v2 ) = 4. Punto de suspensión y borde de suspensión: El punto de segundo orden se denomina punto de suspensión; el borde conectado con el punto de suspensión es el borde de suspensión. Punto singular y punto par: el punto impar es el punto singular, en caso contrario es el punto par. FIG vacío : FIG si G enE = [Phi] (conjunto nulo), entonces
G está vacío FIG. Punto aislado: el punto del gráfico vacío o el punto con grado cero se denomina punto aislado.

Gráfico conectadoSi dos puntos cualesquiera del gráfico G tienen al menos una ruta conectada, entonces el gráfico G se llama gráfico conectado; de lo contrario, se llama gráfico desconectado (Figura 6). Los gráficos conectados también tienen algunos conceptos de uso común: Cadena: si la secuencia de nodos en el gráfico G P = { v 1 , v 2 , …, v k }, dos nodos consecutivos son adyacentes en el gráfico, entonces P es Una cadena que conecta v 1 y v k .

Gráfico conectado dirigido y gráfico conectado no dirigido: especifique una dirección para cada borde, es decir, cuando cada nodo está conectado por un borde con flechas, se denomina gráfico conectado dirigido; de lo contrario, es un gráfico conectado no dirigido (Figura 7). Gráfico fuertemente conectado: cuando hay bordes interconectados entre todos los vértices en un gráfico conectado dirigido, este tipo de gráfico conectado dirigido se llama gráfico fuertemente conectado (Figura 8).

Subgrafoen el estudio de la estructura local y descripción de las figuras y la naturaleza, el concepto de subgrafo ocupa un lugar importante. Para un gráfico G 1 = ( V 1 , E 1 ), G 2 = ( V 2 , E 2 ), si V 1 V 2 , E 1 E 2 , entonces G 1 se llama un subgrafo de G 2 . Si V 1 V 2 , E 1 E 2 , es decir, G 1 no contiene todos los nodos y aristas en G 2 , entonces se llama G 1 esel verdadero subgrafode G 2 , y la imagen de la derecha en la Figura 9 es el verdadero subgrafo de la imagen de la izquierda. Si V 1 = V 2 , E 1 E 2 , entonces G 1 sellamael subgrafodeapoyode G 2 . Si V 1 V 2 , E 1 = {[ u, v ] E 2 | u V 1 , v V 1 }, entonces G 1 esun subgrafo derivado de G 2 por V 1 , denotado como G ( V 1 ).

Árbol Elárbol es un concepto importante en la teoría de grafos. Un gráfico sin un ciclo que consta de nodos y aristas se denomina gráfico acíclico. Un árbol es un gráfico acíclico conectado. La Figura 10 muestra un árbol diferente con 6 nodos. Si el subgrafo de apoyo T = ( V, E T ) del gráfico conectado G = ( V, E ) es un árbol, entonces T se denomina árbol de apoyo de G (Figura 11). Si T = ( V, E T ) es el árbol de apoyo, entonces T = ( V, E E T ) se llama co-árbol de G (Figura 12).

Representación matricial degráficos: un gráfico está completamente determinado por su adyacencia y relevancia, y este tipo de información se puede representar mediante una matriz. Los más utilizados son la matriz de adyacencia y la matriz de incidencia. Matriz de adyacencia A : una matriz utilizada para representar el estado conectado entre los nodos en el gráfico. Un elemento A ij de definido como

La matriz de adyacencia A del gráfico G en la Figura 13 es

Matriz de incidencia S : una matriz que se utiliza para describir la relación entre los nodos y los bordes. El elemento s ij de S se puede definir como

La matriz de incidencia S del gráfico G en la Figura 13 es

También hay matrices de conjuntos de cortes y matrices de ciclos que se pueden usar para describir el teorema de la corriente y el teorema del voltaje de Kirchhoff.