En matemáticas discretas , particularmente en teoría de grafos , un grafo es una estructura que consiste en un conjunto de objetos donde algunos pares de objetos están en algún sentido "relacionados". Los objetos están representados por abstracciones llamadas vértices (también llamados nodos o puntos ) y cada uno de los pares de vértices relacionados se llama arista (también llamado enlace o línea ). [1] Normalmente, un grafo se representa en forma diagramática como un conjunto de puntos o círculos para los vértices, unidos por líneas o curvas para las aristas.
Las aristas pueden ser dirigidas o no dirigidas. Por ejemplo, si los vértices representan a personas en una fiesta y hay una arista entre dos personas si se dan la mano, entonces este grafo no es dirigido porque cualquier persona A puede estrecharle la mano a una persona B solo si B también le estrecha la mano a A. Por el contrario, si una arista de una persona A a una persona B significa que A le debe dinero a B , entonces este grafo es dirigido, porque deber dinero no es necesariamente recíproco.
Los grafos son el objeto de estudio básico de la teoría de grafos. La palabra "grafo" fue utilizada por primera vez en este sentido por JJ Sylvester en 1878 debido a la relación directa entre las matemáticas y la estructura química (lo que él llamó una imagen químico-gráfica). [2] [3]
Las definiciones en teoría de grafos varían. A continuación se presentan algunas de las formas más básicas de definir grafos y estructuras matemáticas relacionadas .
Un grafo (a veces llamado grafo no dirigido para distinguirlo de un grafo dirigido, o grafo simple para distinguirlo de un multigrafo ) [4] [5] es un par G = ( V , E ) , donde V es un conjunto cuyos elementos se llaman vértices (singular: vértice), y E es un conjunto de pares de vértices no ordenados, cuyos elementos se llaman aristas (a veces enlaces o líneas ).
Los vértices u y v de una arista { u , v } se denominan extremos de la arista . Se dice que la arista une u y v e incide sobre ellos. Un vértice puede no pertenecer a ninguna arista, en cuyo caso no está unido a ningún otro vértice y se denomina aislado . Cuando existe una arista , los vértices u y v se denominan adyacentes .
Un multigrafo es una generalización que permite que múltiples aristas tengan el mismo par de puntos finales. En algunos textos, los multigrafos se denominan simplemente grafos. [6] [7]
A veces, se permite que los grafos contengan bucles , que son aristas que unen un vértice consigo mismo. Para permitir bucles, se debe permitir que los pares de vértices en E tengan el mismo nodo dos veces. Estos grafos generalizados se denominan grafos con bucles o simplemente grafos cuando el contexto deja claro que se permiten los bucles.
En general, se considera que el conjunto de vértices V es finito (lo que implica que el conjunto de aristas E también es finito). A veces se consideran grafos infinitos , pero normalmente se los considera como un tipo especial de relación binaria , porque la mayoría de los resultados sobre grafos finitos no se extienden al caso infinito o necesitan una prueba bastante diferente.
Un grafo vacío es un grafo que tiene un conjunto vacío de vértices (y por lo tanto un conjunto vacío de aristas). El orden de un grafo es su número | V | de vértices, normalmente denotado por n . El tamaño de un grafo es su número | E | de aristas, normalmente denotado por m . Sin embargo, en algunos contextos, como para expresar la complejidad computacional de algoritmos, el término tamaño se utiliza para la cantidad | V | + | E | (de lo contrario, un grafo no vacío podría tener tamaño 0). El grado o valencia de un vértice es el número de aristas que le inciden; para grafos con bucles, un bucle se cuenta dos veces.
En un gráfico de orden n , el grado máximo de cada vértice es n − 1 (o n + 1 si se permiten bucles, porque un bucle contribuye con 2 al grado), y el número máximo de aristas es n ( n − 1)/2 (o n ( n + 1)/2 si se permiten bucles).
Las aristas de un grafo definen una relación simétrica en los vértices, llamada relación de adyacencia . Específicamente, dos vértices x e y son adyacentes si { x , y } es una arista. Un grafo está completamente determinado por su matriz de adyacencia A , que es una matriz cuadrada n × n , donde A ij especifica el número de conexiones del vértice i al vértice j . Para un grafo simple, A ij es 0, lo que indica desconexión, o 1, lo que indica conexión; además A ii = 0 porque una arista en un grafo simple no puede comenzar y terminar en el mismo vértice. Los grafos con bucles propios se caracterizarán por que algunos o todos los A ii sean iguales a un entero positivo, y los multigrafos (con múltiples aristas entre vértices) se caracterizarán por que algunos o todos los A ij sean iguales a un entero positivo. Los grafos no dirigidos tendrán una matriz de adyacencia simétrica (lo que significa que A ij = A ji ).
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, [8] un gráfico dirigido es un par G = ( V , E ) que comprende:
Para evitar ambigüedades, este tipo de objeto puede llamarse precisamente un gráfico simple dirigido .
En la arista ( x , y ) dirigida de x a y , los vértices x e y se denominan puntos finales de la arista, x la cola de la arista e y la cabeza de la arista. Se dice que la arista une x e y y que es incidente en x y en y . Un vértice puede existir en un grafo y no pertenecer a una arista. La arista ( y , x ) se denomina arista invertida de ( x , y ) . 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.
En un sentido más general del término que permite múltiples aristas, [8] un gráfico dirigido a veces se define como un triple ordenado G = ( V , E , ϕ ) que comprende:
Para evitar ambigüedades, este tipo de objeto puede llamarse precisamente un multigrafo dirigido .
Un bucle es una arista que une un vértice consigo mismo. Los grafos dirigidos, tal como se definen en las dos definiciones anteriores, no pueden tener bucles, porque un bucle que une un vértice consigo mismo es la arista (para un grafo simple dirigido) o es incidente en (para un multigrafo dirigido) que no está en . Por lo tanto, para permitir bucles, las definiciones deben expandirse. Para grafos simples dirigidos, la definición de debe modificarse a . Para multigrafos dirigidos, la definición de debe modificarse a . Para evitar ambigüedades, estos tipos de objetos pueden llamarse precisamente un grafo simple dirigido que permite bucles y un multigrafo dirigido que permite bucles (o un quiver ) respectivamente.
Las aristas de un grafo simple dirigido que permite bucles G es una relación homogénea ~ en los vértices de G que se llama relación de adyacencia de G . Específicamente, para cada arista ( x , y ) , se dice que sus puntos finales x e y son adyacentes entre sí, lo que se denota x ~ y .
Un grafo mixto es un grafo en el que algunas aristas pueden ser dirigidas y otras no. Es un triple ordenado G = ( V , E , A ) para un grafo simple mixto y G = ( V , E , A , ϕ E , ϕ A ) para un multigrafo mixto con V , E (las aristas no dirigidas), A (las aristas dirigidas), ϕ E y ϕ A definidas como se indicó anteriormente. Los grafos dirigidos y no dirigidos son casos especiales.
Un gráfico ponderado o una red [9] [10] es un gráfico en el que se asigna un número (el peso) a cada arista. [11] Dichos pesos pueden representar, por ejemplo, costos, longitudes o capacidades, dependiendo del problema en cuestión. Dichos gráficos surgen en muchos contextos, por ejemplo, en problemas de ruta más corta , como el problema del viajante de comercio .
Una definición de un grafo orientado es que es un grafo dirigido en el que como máximo uno de ( x , y ) y ( y , x ) pueden ser aristas del grafo. Es decir, es un grafo dirigido que se puede formar como una orientación de un grafo no dirigido (simple).
Algunos autores utilizan el término "grafo orientado" para referirse a lo mismo que "grafo dirigido". Algunos autores utilizan el término "grafo orientado" para referirse a cualquier orientación de un grafo no dirigido o multigrafo determinado.
Un grafo regular es un grafo en el que cada vértice tiene el mismo número de vecinos, es decir, cada vértice tiene el mismo grado. Un grafo regular con vértices de grado k se denomina grafo k -regular o grafo regular de grado k .
Un grafo completo es un grafo en el que cada par de vértices está unido por una arista. Un grafo completo contiene todas las aristas posibles.
Un grafo finito es un grafo en el que el conjunto de vértices y el conjunto de aristas son conjuntos finitos . De lo contrario, se denomina grafo infinito .
En teoría de grafos, lo más común es que se dé por sentado que los grafos analizados son finitos. Si los grafos son infinitos, esto suele indicarse específicamente.
En un grafo no dirigido, un par de vértices no ordenados { x , y } se denomina conexo si un camino conduce de x a y . De lo contrario, el par no ordenado se denomina desconectado .
Un grafo conexo es un grafo no dirigido en el que cada par de vértices no ordenados del grafo está conexo. De lo contrario, se denomina grafo desconectado .
En un grafo dirigido, un par ordenado de vértices ( x , y ) se denomina fuertemente conectado si un camino dirigido conduce de x a y . De lo contrario, el par ordenado se denomina débilmente conectado si un camino no dirigido conduce de x a y después de reemplazar todas sus aristas dirigidas por aristas no dirigidas. De lo contrario, el par ordenado se denomina desconectado .
Un grafo fuertemente conexo es un grafo dirigido en el que cada par ordenado de vértices en el grafo está fuertemente conexo. De lo contrario, se denomina grafo débilmente conexo si cada par ordenado de vértices en el grafo está débilmente conexo. De lo contrario, se denomina grafo desconectado .
Un grafo conexo por k vértices o conexo por k aristas es un grafo en el que no existe ningún conjunto de k − 1 vértices (respectivamente, aristas) que, al eliminarse, desconecte el grafo. Un grafo conexo por k vértices suele denominarse simplemente grafo conexo por k .
Un grafo bipartito es un grafo simple en el que el conjunto de vértices se puede dividir en dos conjuntos, W y X , de modo que ningún par de vértices en W comparta una arista común y ningún par de vértices en X comparta una arista común. Alternativamente, es un grafo con un número cromático de 2.
En un gráfico bipartito completo , el conjunto de vértices es la unión de dos conjuntos disjuntos, W y X , de modo que cada vértice en W es adyacente a cada vértice en X pero no hay aristas dentro de W o X.
Un grafo de trayectoria o grafo lineal de orden n ≥ 2 es un grafo en el que los vértices se pueden enumerar en un orden v 1 , v 2 , …, v n tal que las aristas son { v i , v i +1 } donde i = 1, 2, …, n − 1. Los grafos de trayectoria se pueden caracterizar como grafos conexos en los que el grado de todos los vértices menos dos es 2 y el grado de los dos vértices restantes es 1. Si un grafo de trayectoria ocurre como un subgrafo de otro grafo, es una trayectoria en ese grafo.
Un gráfico plano es un gráfico cuyos vértices y aristas se pueden dibujar en un plano de manera que ninguna de las aristas se cruce.
Un grafo de ciclo o grafo circular de orden n ≥ 3 es un grafo en el que los vértices se pueden enumerar en un orden v 1 , v 2 , …, v n tal que las aristas son { v i , v i +1 } donde i = 1, 2, …, n − 1, más la arista { v n , v 1 } . Los grafos de ciclo se pueden caracterizar como grafos conexos en los que el grado de todos los vértices es 2. Si un grafo de ciclo ocurre como un subgrafo de otro grafo, es un ciclo o circuito en ese grafo.
Un árbol es un gráfico no dirigido en el que dos vértices están conectados exactamente por un camino , o equivalentemente, un gráfico no dirigido acíclico conectado .
Un bosque es un gráfico no dirigido en el que dos vértices están conectados como máximo por un camino, o equivalentemente un gráfico no dirigido acíclico, o equivalentemente una unión disjunta de árboles.
Un poliárbol (o árbol dirigido o árbol orientado o red simplemente conectada ) es un gráfico acíclico dirigido (DAG) cuyo gráfico no dirigido subyacente es un árbol.
Un polibosque (o bosque dirigido o bosque orientado ) es un gráfico acíclico dirigido cuyo gráfico no dirigido subyacente es un bosque.
Los tipos de gráficos más avanzados son:
Dos aristas de un grafo se denominan adyacentes si comparten un vértice común. Dos aristas de un grafo dirigido se denominan consecutivas si la cabeza de la primera es la cola de la segunda. De manera similar, dos vértices se denominan adyacentes si comparten una arista común ( consecutivas si la primera es la cola y la segunda es la cabeza de una arista), en cuyo caso se dice que la arista común une los dos vértices. Una arista y un vértice sobre esa arista se denominan incidentes .
El grafo con un solo vértice y sin aristas se denomina grafo trivial . Un grafo con solo vértices y sin aristas se conoce como grafo sin aristas . El grafo sin vértices ni aristas a veces se denomina grafo nulo o grafo vacío , pero la terminología no es uniforme y no todos los matemáticos admiten este objeto.
Normalmente, los vértices de un grafo, por su naturaleza como elementos de un conjunto, son distinguibles. Este tipo de grafo puede llamarse vértice-labeled . Sin embargo, para muchas preguntas es mejor tratar los vértices como indistinguibles. (Por supuesto, los vértices pueden ser distinguibles por las propiedades del propio grafo, por ejemplo, por el número de aristas incidentes). Las mismas observaciones se aplican a las aristas, por lo que los grafos con aristas etiquetadas se denominan edge-labeled . Los grafos con etiquetas adjuntas a aristas o vértices se designan más generalmente como labeled . En consecuencia, los grafos en los que los vértices son indistinguibles y las aristas son indistinguibles se denominan unlabeled . (En la literatura, el término labeled puede aplicarse a otros tipos de etiquetado, además de aquel que sirve solo para distinguir diferentes vértices o aristas).
La categoría de todos los gráficos es la categoría de coma Conjunto ↓ D donde D : Conjunto → Conjunto es el funtor que toma un conjunto s en s × s .
Existen varias operaciones que producen nuevos gráficos a partir de los iniciales, que podrían clasificarse en las siguientes categorías:
En un hipergrafo , una arista puede unir cualquier número positivo de vértices.
Un grafo no dirigido puede verse como un complejo simplicial que consta de 1- símplices (las aristas) y 0-símplices (los vértices). Como tales, los complejos son generalizaciones de grafos, ya que permiten la existencia de símplices de dimensiones superiores.
Cada gráfico da lugar a un matroide .
En la teoría de modelos , un grafo es simplemente una estructura . Pero en ese caso, no hay límite en cuanto al número de aristas: puede ser cualquier número cardinal , véase grafo continuo .
En biología computacional , el análisis de gráficos de potencia introduce los gráficos de potencia como una representación alternativa de gráficos no dirigidos.
En los sistemas de información geográfica , las redes geométricas se modelan de cerca a partir de gráficos y toman prestados muchos conceptos de la teoría de grafos para realizar análisis espaciales en redes de carreteras o redes de servicios públicos.
Un grafo es un objeto que consta de dos conjuntos llamados su conjunto de vértices y su conjunto de aristas .
gráfico ponderado
es un gráfico en el que se asigna un número w ( e ), llamado su peso , a cada arista e .
Medios relacionados con Grafo (matemáticas discretas) en Wikimedia Commons
