En matemáticas discretas , y más específicamente en teoría de grafos , un gráfico es una estructura que equivale a un conjunto de objetos en el que algunos pares de objetos están en algún sentido "relacionados". Los objetos corresponden a abstracciones matemáticas 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 gráfico se representa en forma de diagrama como un conjunto de puntos o círculos para los vértices, unidos por líneas o curvas para los bordes. Los gráficos son uno de los objetos de estudio en matemáticas discretas.
Los bordes pueden estar dirigidos o no dirigidos. Por ejemplo, si los vértices representan personas en una fiesta y hay una ventaja entre dos personas si se dan la mano, entonces este gráfico no está dirigido porque cualquier persona A puede estrechar la mano de una persona B solo si B también le da la mano a A. Por el contrario, si una ventaja de una persona A a una persona B significa que A le debe dinero a B , entonces esta gráfica es dirigida, porque deber dinero no es necesariamente recíproco.
Los gráficos son el tema básico que estudia la teoría de grafos. La palabra "gráfico" fue utilizada por primera vez en este sentido por JJ Sylvester en 1878 debido a una relación directa entre las matemáticas y la estructura química (lo que él llamó imagen químico-gráfica). [2] [3]
Las definiciones en teoría de grafos varían. Las siguientes son algunas de las formas más básicas de definir gráficas y estructuras matemáticas relacionadas .
Un gráfico (a veces llamado gráfico no dirigido para distinguirlo de un gráfico dirigido, o gráfico simple para distinguirlo de un multigrafo ) [4] [5] es un par G = ( V , E ) , donde V es un conjunto cuyo los elementos se llaman vértices (singular: vértice), y E es un conjunto de pares desordenados de vértices, cuyos elementos se llaman aristas (a veces enlaces o líneas ).
Los vértices u y v de una arista { u , v } se denominan puntos finales de la arista . Se dice que el borde 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 llama aislado . Cuando existe una arista, los vértices u y v se llaman 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 gráficos. [6] [7]
A veces, se permite que los gráficos 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 gráficos generalizados se denominan gráficos con bucles o simplemente gráficos cuando del contexto queda claro que los bucles están permitidos.
Generalmente, el conjunto de vértices V se considera finito (lo que implica que el conjunto de aristas E también es finito). A veces se consideran gráficos infinitos , pero generalmente se ven como un tipo especial de relación binaria , porque la mayoría de los resultados en gráficos finitos no se extienden al caso infinito o necesitan una prueba bastante diferente.
Un gráfico vacío es un gráfico que tiene un conjunto vacío de vértices (y, por tanto, un conjunto vacío de aristas). El orden de una gráfica es su número | V | de vértices, generalmente denotados por n . El tamaño de una gráfica es su número | mi | de aristas, normalmente denotadas por m . Sin embargo, en algunos contextos, como para expresar la complejidad computacional de los algoritmos, el término tamaño se utiliza para la cantidad | V | + | mi | (de lo contrario, un gráfico 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 gráficos con bucles, un bucle se cuenta dos veces.
En una gráfica de orden n , el grado máximo de cada vértice es n − 1 (o n + 1 si se permiten bucles, porque un bucle aporta 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).
Los bordes de un gráfico definen una relación simétrica en los vértices, llamada relación de adyacencia . Específicamente , dos vértices xey son adyacentes si { x , y } es una arista . Un gráfico está completamente determinado por su matriz de adyacencia A , que es una matriz cuadrada de n × n , donde A ij especifica el número de conexiones desde el vértice i al vértice j . Para un gráfico simple, A ij es 0, que indica desconexión, o 1, que indica conexión; además A ii = 0 porque una arista en un gráfico simple no puede comenzar y terminar en el mismo vértice. Los gráficos con bucles automáticos se caracterizarán por que parte o todo A ii sea igual a un entero positivo, y los multigrafos (con múltiples aristas entre vértices) se caracterizarán por que parte o todo A ij sea igual a un entero positivo. Los gráficos no dirigidos tendrán una matriz de adyacencia simétrica (es decir, A ij = A ji ).
Un gráfico dirigido o dígrafo es un gráfico en el que las aristas 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 denominarse precisamente grafo 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 y y la cabeza de la arista. Se dice que la arista une x e y e incide sobre x y sobre y . Un vértice puede existir en un gráfico y no pertenecer a una arista. La arista ( y , x ) se llama arista invertida de ( x , y ) . 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 denominarse precisamente multigrafo dirigido .
Un bucle es una arista que une un vértice consigo mismo. Los gráficos dirigidos, como se definen en las dos definiciones anteriores, no pueden tener bucles, porque un bucle que une un vértice consigo mismo es el borde (para un gráfico simple dirigido) o incide en (para un multigrafo dirigido) que no está en . Entonces, para permitir bucles, se deben ampliar las definiciones. Para gráficos simples dirigidos, la definición de debe modificarse a . Para multigrafos dirigidos, la definición de debe modificarse a . Para evitar ambigüedades, este tipo de objetos pueden denominarse precisamente un gráfico simple dirigido que permite bucles y un multigrafo dirigido que permite bucles (o un carcaj ), respectivamente.
Las aristas de un gráfico simple dirigido que permiten bucles G son una relación homogénea ~ en los vértices de G que se llama relación de adyacencia de G. Específicamente, para cada borde ( x , y ) , se dice que sus puntos finales x e y son adyacentes entre sí, lo que se denota x ~ y .
Un gráfico mixto es un gráfico en el que algunas aristas pueden estar 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 (los bordes dirigidos), ϕ E y ϕ A definidos como anteriormente. Los gráficos 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] Estos pesos podrían representar, por ejemplo, costes, longitudes o capacidades, dependiendo del problema en cuestión. Estos gráficos surgen en muchos contextos, por ejemplo, en problemas del camino más corto , como el problema del viajante .
Una definición de gráfico orientado es que es un gráfico dirigido en el que como máximo uno de ( x , y ) y ( y , x ) pueden ser bordes del gráfico. Es decir, es un gráfico dirigido que se puede formar como una orientación de un gráfico no dirigido (simple).
Algunos autores utilizan "gráfico orientado" en el sentido de "gráfico dirigido". Algunos autores utilizan "gráfico orientado" para referirse a cualquier orientación de un gráfico o multigrafo no dirigido determinado.
Un gráfico regular es un gráfico en el que cada vértice tiene el mismo número de vecinos, es decir, cada vértice tiene el mismo grado. Una gráfica regular con vértices de grado k se llama k -gráfica regular o gráfica regular de grado k .
Un gráfico completo es un gráfico en el que cada par de vértices está unido por una arista. Un gráfico completo contiene todas las aristas posibles.
Un gráfico finito es un gráfico en el que el conjunto de vértices y el conjunto de aristas son conjuntos finitos . De lo contrario, se llama gráfico infinito .
Lo más común en teoría de grafos es que se da a entender que las gráficas analizadas son finitas. Si las gráficas son infinitas, eso generalmente se indica específicamente.
En un gráfico no dirigido, un par desordenado de vértices { x , y } se llama conectado si un camino va de x a y . De lo contrario, el par desordenado se llama desconectado .
Un gráfico conectado es un gráfico no dirigido en el que cada par desordenado de vértices del gráfico está conectado. De lo contrario, se llama gráfico desconectado .
En un gráfico dirigido, un par ordenado de vértices ( x , y ) se llama fuertemente conectado si un camino dirigido va de x a y . De lo contrario, el par ordenado se denomina débilmente conectado si un camino no dirigido va de x a y después de reemplazar todas sus aristas dirigidas con aristas no dirigidas. De lo contrario, el par ordenado se llama desconectado .
Un gráfico fuertemente conexo es un gráfico dirigido en el que cada par ordenado de vértices del gráfico está fuertemente conexo. De lo contrario, se denomina gráfico débilmente conexo si cada par ordenado de vértices del gráfico está débilmente conexo. De lo contrario se llama gráfico desconectado .
Un gráfico conectado con k-vértices o un gráfico conectado con k-bordes es un gráfico en el que no existe ningún conjunto de k - 1 vértices (respectivamente, aristas) que, cuando se elimina, desconecta el gráfico. Un gráfico k conectado a vértices a menudo se denomina simplemente gráfico k conectado .
Un gráfico bipartito es un gráfico simple en el que el conjunto de vértices se puede dividir en dos conjuntos, W y X , de modo que no haya dos vértices en W que compartan un borde común y que no haya dos vértices en X que compartan un borde común. Alternativamente, es un gráfico 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 gráfico de ruta o gráfico lineal de orden n ≥ 2 es un gráfico en el que los vértices se pueden enumerar en un orden v 1 , v 2 ,…, v n tal que las aristas sean { v i , v i +1 } donde i = 1, 2,…, n − 1. Los gráficos de ruta se pueden caracterizar como gráficos conectados en los que el grado de todos los vértices excepto dos es 2 y el grado de los dos vértices restantes es 1. Si un gráfico de ruta se presenta como un subgrafo de otro gráfico, es un camino en ese gráfico.
Un gráfico plano es un gráfico cuyos vértices y aristas se pueden dibujar en un plano de modo que no se crucen dos de las aristas.
Un gráfico de ciclo o gráfico circular de orden n ≥ 3 es un gráfico en el que los vértices se pueden enumerar en un orden v 1 , v 2 ,…, v n tal que las aristas sean { v i , v i +1 } donde i = 1, 2,…, n − 1, más la arista { v n , v 1 } . Los gráficos de ciclo se pueden caracterizar como gráficos conectados en los que el grado de todos los vértices es 2. Si un gráfico de ciclo aparece como un subgrafo de otro gráfico, es un ciclo o circuito en ese gráfico.
Un árbol es un gráfico no dirigido en el que dos vértices cualesquiera están conectados por exactamente una ruta , o equivalentemente un gráfico no dirigido acíclico conectado .
Un bosque es un gráfico no dirigido en el que dos vértices cualesquiera están conectados por como máximo un camino, o de manera equivalente, un gráfico no dirigido acíclico, o de manera equivalente, una unión disjunta de árboles.
Un poliárbol (o árbol dirigido o árbol orientado o red individualmente 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 grafo acíclico dirigido cuyo grafo no dirigido subyacente es un bosque.
Los tipos de gráficos más avanzados son:
Dos aristas de un gráfico se llaman adyacentes si comparten un vértice común. Dos aristas de un grafo dirigido se llaman consecutivas si la cabeza de la primera es la cola de la segunda. De manera similar, dos vértices se llaman adyacentes si comparten una arista común ( consecutivos si el primero es la cola y el segundo 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 en esa arista se llaman incidente .
El gráfico con un solo vértice y sin aristas se llama gráfico trivial . Un gráfico con sólo vértices y sin aristas se conoce como gráfico sin aristas . El gráfico sin vértices ni aristas a veces se denomina gráfico nulo o gráfico vacío , pero la terminología no es consistente y no todos los matemáticos permiten este objeto.
Normalmente, los vértices de un gráfico, por su naturaleza como elementos de un conjunto, son distinguibles. Este tipo de gráfico puede denominarse etiquetado con vértices . Sin embargo, para muchas preguntas es mejor tratar los vértices como indistinguibles. (Por supuesto, los vértices aún pueden distinguirse por las propiedades del gráfico mismo, por ejemplo, por el número de aristas incidentes). Las mismas observaciones se aplican a las aristas, por lo que los gráficos con aristas etiquetadas se denominan aristas etiquetadas . Los gráficos con etiquetas adjuntas a aristas o vértices generalmente se denominan etiquetados . En consecuencia, los gráficos en los que los vértices y las aristas son indistinguibles se denominan sin etiquetar . (En la literatura, el término etiquetado puede aplicarse a otros tipos de etiquetado, además del que sirve sólo 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 a s × s .
Hay 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 más de dos vértices.
Un gráfico 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 gráficos, ya que permiten simples de dimensiones superiores.
Cada gráfico da lugar a una matroide .
En la teoría de modelos , una gráfica es sólo una estructura . Pero en ese caso, no hay limitación en el número de aristas: puede ser cualquier número cardinal , ver gráfico 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 los gráficos no dirigidos.
En los sistemas de información geográfica , las redes geométricas se modelan estrechamente 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 gráfico es un objeto que consta de dos conjuntos llamados conjunto de vértices y conjunto de aristas .
Un gráfico ponderado es un gráfico en el que a cada arista e se le asigna un número w ( e ), llamado peso .
Medios relacionados con Graph (matemáticas discretas) en Wikimedia Commons
