Glosario en teoría de grafos
Keywords: Glosario en teoría de grafos, Conjunto vacío, Estructura de datos, Infinito, Matriz (matemáticas), Problema de la clique, Sii, Teoría de grafos, Camino Hamiltoniano
Quizá quieras empezar por Teoría de grafos o el artículo Grafo_(matemáticas).
Una arista dirigida es una arista de un grafo dirigido y tiene una dirección asociada consigo, esto es, la pensamos como "viniendo" de uno de los vértices y yendo hacia el otro. Una arista no dirigida trata ambos vértices de manera intercambiable.
Un bucle en un grafo o un digrafo es una arista e en E cuyos puntos finales son el mismo vértice. Un digrafo o un grafo se dice simple si no tiene bucles y existe como mucho una arista entre cada par de vértices.
| Imagen no existente 6n-graf.png Image:6n-graf.png |
El grafo del ejemplo a la derecha es un grafo simple con conjunto de vértices V = {1, 2, 3, 4, 5, 6} y de aristas E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}} (cuya aplicación w es la identidad).
Una arista conecta dos vértices, que por eso son llamados incidentes respecto a dicha arista. La valencia (o grado) de un vértice es el número de aristas incidentes en él, y si hay bucles son contados por dos. En el grafo ejemplo los vértices 1 y 3 tienen una valencia de 2, vértices 2,4 y 5 la tienen de 3 y el vértice 6 la tiene de 1. Si E es finito, entonces la valencia total de los vértices es el doble del número de aristas. En un digrafo, podemos distinguir los grados salientes (=el número de aristas que dejan el vértice) y el grado entrante (=el número de aristas que entran en un vértice). El grado de un vértice sería la suma de ambos números.
Dos vértices son considerados adyacentes si existe una arista entre los dos. En el grafo ejemplo, los vértices 1 y 2 lo son, pero no así los 2 y 4. El conjunto de vecinos para un vértice consiste de aquellos vértices adyacentes a él mismo. En el ejemplo, el vértice 1 tiene dos vecinos: el vértice 2 y el nodo 5. Para un grafo simple, El número de vecinos de un vértice es igual a su valencia.
En las computadoras, un grafo finito dirigido o sin dirigir (con n vértices, pongamos) es amenudo representado por su matriz de adyacencias: una matriz n-por-n cuyas entradas en la fila i y columna j da el número de aristas desde el vértice i-ésimo al j-ésimo. La rica teoría que envuelve las relaciones entre las propiedades de esta matriz y las de su grafo se estudia en lo que se llama Teoría de grafos espectral.
Un camino_(teoría de grafos) es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor. Se dice que un camino A es simple si no se repite ninguno de sus vértices en él. Dos caminos son independientes si no tienen ningún vértice en común excepto el primero y el último.
La longitud de un camino es el número de aristas que usa dicho camino, contando aristas recorridas varias veces el mismo número de veces que las recorramos. En el ejemplo, (1, 2, 5, 1, 2, 3) es un camino con longitud 5, y (5, 2, 1) es un camino simple de longitud 2.
Un grafo con pesos, o con coste decimos a veces, asocia un valor (peso) a cada arista en el grafo. El peso de un camino en un grafo con pesos es la suma de los pesos de todos los caminos atravesados.
Si es posible formar un camino desde cualquier vértice a cualquier otro en el grafo, decimos que el grafo es conexo. Si es posible hacer esto incluso tras quitar k-1 vértices, decimos que el grafo es k-conexo. Notar que un grafo es k-conexo sii contiene k caminos independientes entre cualesquiera dos vértices. El grafo ejemplo es conexo (y por tanto 1-conexo), pero no es 2-conexo.
Un ciclo (o circuito) es un camino que empieza y acaba en el mismo vértice. Los ciclos de longitud 1 son los bucles. En el ejemplo, (1, 2, 3, 4, 5, 2, 1) es un ciclo de longitud 6. Un ciclo simple es un ciclo que tiene como longitud al menos 3 y en el que el vértice del comienzo sólo aparece una vez más y como vértice final, y los demás sólo aparecen una vez. En el grafo de arriba (1, 5, 2, 1) es un ciclo simple. Un grafo se dice acíclico si no contiene ningún ciclo simple.
Un punto de articulación es un vértice tal que si lo quitamos nos quedamos con un grafo disconexo. Un puente A es una arista tal que si la quitamos nos quedamos con un grafo disconexo. Un componente biconexa es un conjunto maximal de aristas tal que cualesquiera dos aristas en el conjunto pertenecen a un ciclo simple común. El girth de un grafo es la longitud del ciclo simple más corto en el grafo. El "girth" de un grafo acíclico se define como infinito.
Un árbol es un grafo conexo simple acíclico. Algunas veces, un vértice del árbol es distinguido llamándolo raíz. Los árboles se usan frecuentemente como estructuras de datos en teoría de computación (ver estructuras de datos arborecentes).
Un bosque es un conjunto de árboles; o de forma equivalente, un bosque es un grafo acíclico.
Un subgrafo de un grafo G es un grafo cuyo conjunto de vértices es un subconjunto del de G, cuyo conjunto de aristas es un subconjunto del conjunto de las de G, y tal que la aplicación w es la restricción de la aplicación de G.
Un subárbol de un grafo G es un subgrafo que es además un árbol.
Un subgrafo de expansión de un grafo G es un subgrafo con el mismo conjunto de vértices que G. Un árbol expansión es un subgrafo expansión que es un árbol. Cada grafo tiene un árbol de expansión.
Un grafo completo es un grafo simple en el que cada vértice es adyacente a cualquier todo otro vértice. El del ejemplo no es completo. El grafo completo en n vértices se denota a menudo por Kn. Tiene n(n-1)/2 edges (correspondiendo a todas las posibles elecciones de pares de vértices).
Un grafo regular tiene todos los vértices con la misma valencia.
Un grafo universal en una clase K de grafos es un grafo simple que puede incluirse como subgrafo en otod elemento de K.
Un grafo planar es uno que puede ser dibujado en el plano sin que se intersequen cualesquiera dos aristas. El del ejemplo lo es; el grafo completo en n vértices, para n> 4, no es planar.
Un camino Euleriano en un grafo es un camino que usa cada arista justo una vez. Si existe tal camino decimos que el grafo es atravesable. Un ciclo Euleriano es un ciclo que usa cada arista justo una vez.
Existe un concepto dual al de camino/ciclo Euleriano. Un camino Hamiltoniano en un grafo es un camino que "visita" cada vértice una y sólo una vez; y un ciclo Hamiltoniano es un ciclo que visita cada vértice una y sólo una vez.
El grafo del ejemplo no contiene caminos Eulerianos pero sí uno Hamiltoniano.
Un grafo vacío es el grafo cuyo conjunto de aristas es vacío.
El grafo nulo es el grafo cuyos conjuntos de aristas y de vértices son vacíos.
Un conjunto independiente en un grafo es un conjunto de vértices no adyacentes dos a dos. En el ejemplo, los vértices 1,3, y 6 forman un conjunto tal y los 3,5, y 6 forman otro conjunto independiente.
Una clique (pronunciado "clik") en un grafo es un conjunto de vértices dos a dos adyacentes. En el ejemplo lo es el compuesto por los vértices 1, 2 y 5.
Un grafo bipartido es cualquier grafo cuyos vértices pueden ser divididos en dos conjuntos, tal que no haya aristas entre los vértices del mismo conjunto. Se ve que un grafo es bipartido si no hay ciclos de longitud impar. Ver grafo completo bipartido
Un grafo k-partido o grafo k-colorable es un grafo con cuyos vértices se puede hacer una partición en k subconjuntos disjuntos tal que no haya aristas entre vértices del mismo subconjunto. Un grafo 2-partido es lo mismo que un grafo bipartido.
Un grafo k-partido se dice semiregular si cada partición tiene un grado uniforme.
Un tournament es un grafo dirigido en el que cada par de vértices está conectado por justo un arco.
Ver también: Grafo_(matemáticas), Teoría de grafos, Lista de tópicos en teoría de grafos