Las definiciones en la teoría de grafos varían. Las siguientes son algunas de las formas más básicas de definir los grafos y las estructuras matemáticas relacionadas.
GraphEdit
Los vértices x e y de una arista {x, y} se llaman puntos finales de la arista. Se dice que la arista une x e y y que es incidente en x e y. Un vértice puede no pertenecer a ninguna arista, en cuyo caso no está unido a ningún otro vértice.
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 llaman simplemente grafos.
A veces, se permite que los grafos contengan bucles, que son aristas que unen un vértice a sí mismo. Para permitir bucles, hay que cambiar la definición anterior definiendo las aristas como conjuntos múltiples de dos vértices en lugar de conjuntos de dos. Estos grafos generalizados se denominan grafos con bucles o simplemente grafos cuando está claro por el contexto que se permiten los bucles.
Generalmente, se supone que el conjunto de vértices V es finito; esto implica que el conjunto de aristas también es finito. Los grafos infinitos se consideran a veces, pero se ven más a menudo 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 necesitan una prueba bastante diferente.
Un grafo vacío es un grafo que tiene un conjunto vacío de vértices (y por tanto un conjunto vacío de aristas). El orden de un grafo es su número de vértices |V|. El tamaño de un grafo es su número de aristas |E|. Sin embargo, en algunos contextos, como para expresar la complejidad computacional de los algoritmos, el tamaño es |V| + |E| (de lo contrario, un grafo no vacío podría tener un tamaño 0). El grado o valencia de un vértice es el número de aristas que inciden en él; para los grafos con bucles, un bucle se cuenta dos veces.
En un grafo de orden n, el grado máximo de cada vértice es n – 1 (o n si se permiten bucles), 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 sobre los vértices, llamada relación de adyacencia. En concreto, dos vértices x e y son adyacentes si {x, y} es una arista. Un grafo puede ser especificado completamente por su matriz de adyacencia A, que es una matriz n × n {desplegable n\nveces n}
matriz cuadrada, con Aij especificando el número de conexiones del vértice i al vértice j. Para un grafo simple, A i j ∈ {{displaystyle A_{ij}\a{{0,1\}}
, indicando desconexión o conexión respectivamente, mientras que A i i = 0 {{displaystyle A_{ii}}=0}
(es decir, una arista no puede empezar y terminar en el mismo vértice). Los grafos con bucles propios se caracterizarán por algunos o todos los A i i {{displaystyle A_{ii}}
que sea igual a un número entero positivo, y los multigrafos (con múltiples aristas entre vértices) se caracterizarán por algunos o todos los A i j {{displaystyle A_{ij}}
siendo igual a un entero positivo. Los grafos no dirigidos tendrán una matriz de adyacencia simétrica ( A i j = A j i {\displaystyle A_{ij}=A_{ji}}
).
Grafo dirigidoEditar
Un grafo dirigido o dígrafo es un grafo en el que las aristas tienen orientaciones.
En un sentido restringido pero muy común del término, un grafo dirigido es un par G = ( V , E ) {\displaystyle G=(V,E)}
que comprende:
- V {\displaystyle V}
, un conjunto de vértices (también llamados nodos o puntos);
- E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 y x ≠ y } {\displaystyle E\\seteq \ {(x,y)\Nen V^{2}\};{\textrm {y}\};x\neq y\}}
, un conjunto de aristas (también llamadas aristas dirigidas, enlaces dirigidos, líneas dirigidas, flechas o arcos) que son pares ordenados de vértices (es decir, una arista está asociada a dos vértices distintos).
Para evitar ambigüedades, a este tipo de objeto se le puede llamar precisamente grafo simple dirigido.
En la arista ( x , y ) {\displaystyle (x,y)}
dirigida desde x {\displaystyle x}
hasta y {\displaystyle y}
, los vértices x {\displaystyle x}
e y {\displaystyle y}
se llaman los puntos finales de la arista, x {\displaystyle x}
la cola de la arista e y {\displaystyle y}
la cabeza de la arista. Se dice que la arista une x {\displaystyle x}
y y {\displaystyle y}
y ser incidente en x {\displaystyle x}
y en y {\displaystyle y}
. Un vértice puede existir en un gráfico y no pertenecer a una arista. La arista ( y , x ) {\displaystyle (y,x)}
se llama arista invertida de ( x , y ) {\displaystyle (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 aristas múltiples, un grafo dirigido es un triple ordenado G = ( V , E , ϕ ) {\displaystyle G=(V,E,\phi )}
que comprende:
- V {\displaystyle V}
, un conjunto de vértices (también llamados nodos o puntos);
- E {\displaystyle E}
, un conjunto de aristas (también llamadas aristas dirigidas, enlaces dirigidos, líneas dirigidas, flechas o arcos);
- ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 y x ≠ y } {\displaystyle \phi :E\to \ {(x,y)\mid (x,y)\Nen V^{2};{\textrm {y}};x\neq y}}
, una función de incidencia que asigna cada arista a un par ordenado de vértices (es decir, una arista está asociada a dos vértices distintos).
Para evitar la ambigüedad, este tipo de objeto puede llamarse precisamente multigrafo dirigido.
Un bucle es una arista que une un vértice consigo mismo. Los grafos dirigidos tal y como se definen en las dos definiciones anteriores no pueden tener bucles, porque un bucle que une un vértice x {\displaystyle x}
a sí mismo es la arista (para un grafo dirigido simple) o es incidente en (para un multigrafo dirigido) ( x , x ) {\displaystyle (x,x)}.
que no está en { ( x , y ) ∣ ( x , y ) ∈ V 2 y x ≠ y } {\displaystyle \{(x,y)\{mid (x,y)\{en V^{2}};{\textrm {y}};x\neq y}}
. Así que para permitir los bucles las definiciones deben ser ampliadas. Para los grafos simples dirigidos, la definición de E
debe modificarse a E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 } {\displaystyle E\\seteq \ {(x,y)\mid (x,y)\Nen V^{2}}
. Para los multigrafos dirigidos, la definición de ϕ {\displaystyle \phi }
debe modificarse por ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 } {\displaystyle \phi :E\to \ {(x,y)\mid (x,y)\Nen V^{2}\}
. Para evitar la ambigüedad, estos tipos de objetos pueden llamarse precisamente un grafo simple dirigido que permite bucles y un multigrafo dirigido que permite bucles (o un carcaj) respectivamente.
Las aristas de un grafo simple dirigido que permite bucles G {\displaystyle G}
es una relación homogénea ~ sobre los vértices de G {\displaystyle G}
que se denomina relación de adyacencia de G
. En concreto, para cada arista ( x , y ) {\displaystyle (x,y)}
, sus puntos finales x {\displaystyle x}
e y {\displaystyle y}
se dice que son adyacentes entre sí, lo que se denota x {\displaystyle x}
~ y {\displaystyle y}
.
Gráfica mixtaEditar
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 definidos como arriba. Los grafos dirigidos y no dirigidos son casos especiales.
Grafo ponderadoEditar
