Gráfico (matemáticas discretas)

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 no ordenados.${\displaystyle \{v_{1},v_{2}\}}$de vértices, cuyos elementos se denominan aristas (a veces enlaces o líneas ).

Un grafo vacío es aquel 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, generalmente denotado por n . El tamaño de un grafo es su número | E | de aristas, generalmente denotado por m . Sin embargo, en algunos contextos, como para expresar la complejidad computacional de los algoritmos, el término tamaño se usa 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 incidentes a él; para grafos con bucles, un bucle se cuenta dos veces.

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 y que 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 una arista${\displaystyle \{u,v\}}$Si existe, 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 extremos. En algunos textos, los multigrafos se denominan simplemente grafos. ^{[ 6 ] [ 7 ]}

En ocasiones, los grafos pueden contener bucles , que son aristas que unen un vértice consigo mismo. Para que existan bucles, los pares de vértices en E deben poder tener el mismo nodo dos veces. Estos grafos generalizados se denominan grafos con bucles o simplemente grafos cuando el contexto deja claro que se permiten bucles.

Generalmente, se considera que el conjunto de vértices V es finito (lo que implica que el conjunto de aristas E también lo es). En ocasiones se consideran grafos infinitos , pero suelen verse como un tipo especial de relación binaria , ya que la mayoría de los resultados sobre grafos finitos no se extienden al caso infinito o requieren una demostración bastante diferente.

En un grafo de orden n , el grado máximo de cada vértice es n − 1 (o n + 1 si se permiten bucles, ya que 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 entre los vértices, denominada 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 de 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 se caracterizan porque algunos o todos los A _ii son iguales a un entero positivo, y los multigrafos (con múltiples aristas entre vértices) se caracterizan porque algunos o todos los A _ij son iguales a un entero positivo. Los grafos no dirigidos tienen una matriz de adyacencia simétrica (es decir, A _ij = A _ji ).

Un grafo dirigido o digrafo es un grafo en el que las aristas tienen orientaciones.

En un sentido restringido pero muy común del término, ^{[ 8 ]} un grafo dirigido es un par G = ( V , E ) que comprende:

• V , un conjunto de vértices (también llamados nodos o puntos );
• E , un conjunto de aristas (también llamadas aristas dirigidas , enlaces dirigidos , líneas dirigidas , flechas o arcos ), que son pares ordenados de vértices distintos:${\displaystyle E\subseteq \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {y}}\;x\neq y\}}$.

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 extremos de la arista, x el origen de la arista e y el inicio de la arista. Se dice que la arista une x e y y que incide sobre x e y . Un vértice puede existir en un grafo y no pertenecer a ninguna 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 el mismo origen y el mismo final.

En un sentido más general del término que permite múltiples aristas, ^{[ 8 ]} un grafo dirigido se define a veces como una tripleta ordenada G = ( V , E , ϕ ) que comprende:

• V , un conjunto de vértices (también llamados nodos o puntos );
• E , un conjunto de aristas (también llamadas aristas dirigidas , enlaces dirigidos , líneas dirigidas , flechas o arcos );
• ϕ , una función de incidencia que asigna a cada arista un par ordenado de vértices (es decir, una arista está asociada con dos vértices distintos):${\displaystyle \phi :E\to \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {y}}\;x\neq y\}}$.

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 grafos dirigidos, tal como se definen en las dos definiciones anteriores, no pueden tener bucles, porque un bucle que une un vértice${\displaystyle x}$La arista es a sí misma (para un grafo simple dirigido) o es incidente sobre (para un multigrafo dirigido).${\displaystyle (x,x)}$que no está en${\displaystyle \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {y}}\;x\neq y\}}$. Por lo tanto, para permitir bucles, las definiciones deben ampliarse. Para grafos simples dirigidos, la definición de${\displaystyle E}$debe modificarse a${\displaystyle E\subseteq V^{2}}$. Para multigrafos dirigidos, la definición de${\displaystyle \phi }$debe modificarse a${\displaystyle \phi :E\a V^{2}}$Para evitar ambigüedades, estos tipos de objetos pueden denominarse precisamente grafo simple dirigido que permite bucles y multigrafo dirigido que permite bucles (o carcaj ), respectivamente.

Las aristas de un grafo simple dirigido que permite 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 arista ( x , y ) , se dice que sus puntos extremos x e y son adyacentes entre sí, lo que se denota como x ~ y .

Un grafo mixto es un grafo en el que algunas aristas pueden ser dirigidas y otras no. Se define como una terna ordenada G = ( V , E , A ) para un grafo simple mixto y G = ( V , E , A , ϕ _E , ϕ _A ) para un multigrafo mixto, donde V , E (las aristas no dirigidas), A (las aristas dirigidas), ϕ _E y ϕ _A se definen como se indicó anteriormente. Los grafos dirigidos y no dirigidos son casos especiales.

Un grafo ponderado o una red ^{[ 9 ] [ 10 ]} es un grafo en el que se asigna un número (el peso) a cada arista. ^{[ 11 ]} Dichos pesos pueden representar, por ejemplo, costos, longitudes o capacidades, según el problema en cuestión. Estos grafos surgen en muchos contextos, por ejemplo, en problemas de camino más corto como el problema del viajante .

Una definición de grafo orientado es que se trata de un grafo dirigido en el que, como máximo, uno de los puntos ( x , y ) y ( y , x ) puede ser una arista. Es decir, es un grafo dirigido que puede formarse como una orientación de un grafo no dirigido (simple).

Algunos autores usan "grafo orientado" como sinónimo de "grafo dirigido". Otros usan "grafo orientado" para referirse a cualquier orientación de un grafo no dirigido o multigrafo dado.

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 aquel 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 . En caso contrario, se denomina grafo infinito .

En teoría de grafos, lo más habitual es que se dé por sentado que los grafos analizados son finitos. Si los grafos son infinitos, normalmente se especifica.

En un grafo no dirigido, un par de vértices no ordenados { x , y } se denomina conectado si existe un camino que va de x a y . En caso 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 está conectado. En caso contrario, se denomina grafo desconectado .

En un grafo dirigido, un par ordenado de vértices ( x , y ) se denomina fuertemente conectado si existe un camino dirigido que va de x a y . En caso contrario, el par ordenado se denomina débilmente conectado si existe un camino no dirigido que va de x a y después de reemplazar todas sus aristas dirigidas por aristas no dirigidas. En caso contrario, el par ordenado se denomina desconectado .

Un grafo fuertemente conexo es un grafo dirigido en el que cada par ordenado de vértices está fuertemente conectado. En caso contrario, se denomina grafo débilmente conexo si cada par ordenado de vértices está débilmente conectado. De lo contrario, se denomina grafo desconectado .

Un grafo k-conexo por vértices o k-conexo por aristas es un grafo en el que no existe ningún conjunto de k − 1 vértices (o aristas) que, al ser eliminados, desconecte el grafo. Un grafo k -conexo por vértices se suele denominar simplemente grafo k-conexo .

Un grafo bipartito es un grafo simple cuyo conjunto de vértices se puede dividir en dos conjuntos, W y X , de manera que ningún par de vértices en W comparte una arista común, ni tampoco ningún par de vértices en X comparte una arista común. Alternativamente, es un grafo con un número cromático de 2.

En un grafo 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 caminos o grafo lineal de orden n ≥ 2 es un grafo cuyos vértices se pueden ordenar v ₁ , v ₂ , …, v _n de tal manera que las aristas son { v _i , v _{i +1} } donde i = 1, 2, …, n − 1. Los grafos de caminos se caracterizan por ser grafos conexos cuyo grado es 2 para todos los vértices excepto dos, y cuyo grado es 1 para los dos vértices restantes. Si un grafo de caminos aparece como subgrafo de otro grafo, se considera un camino en dicho grafo.

Un grafo planar es un grafo cuyos vértices y aristas se pueden dibujar en un plano de tal manera que no haya dos aristas que se crucen.

Un grafo cíclico o circular de orden n ≥ 3 es un grafo cuyos vértices se pueden ordenar v ₁ , v ₂ , …, v _n de tal manera que las aristas son { v _i , v _{i +1} } donde i = 1, 2, …, n − 1, más la arista { v _n , v ₁ } . Los grafos cíclicos se caracterizan por ser grafos conexos cuyo grado es 2. Si un grafo cíclico aparece como subgrafo de otro, se denomina ciclo o circuito en dicho grafo.

Un árbol es un grafo no dirigido en el que cualesquiera dos vértices están conectados por exactamente un camino , o equivalentemente un grafo no dirigido acíclico conexo .

Un bosque es un grafo no dirigido en el que cualesquiera dos vértices están conectados por como máximo un camino, o equivalentemente un grafo no dirigido acíclico, o equivalentemente una unión disjunta de árboles.

Un poliárbol (o árbol dirigido , árbol orientado o red conexa simple ) es un grafo acíclico dirigido (DAG) cuyo grafo subyacente no dirigido es un árbol.

Un polibosque (o bosque dirigido u bosque orientado ) es un grafo dirigido acíclico cuyo grafo subyacente no dirigido es un bosque.

Los tipos de gráficos más avanzados son:

• El grafo de Petersen y sus generalizaciones;
• gráficos perfectos ;
• cografos ;
• gráficos de cuerdas ;
• otros grafos con grandes grupos de automorfismos : grafos transitivos en vértices , transitivos en arcos y transitivos en distancias ;
• Grafos fuertemente regulares y sus generalizaciones: grafos distancia-regulares .