Abrir menú principal

Anexo:Glosario de teoría de grafos

(Redirigido desde «Glosario en teoría de grafos»)
Grafo simple no dirigido, con 6 vértices y 7 aristas.

A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los ejemplos están basados en la imagen de la derecha.

AEditar

 
Vértices adyacentes unidos por una arista.

AdyacentesEditar

En un grafo, los vértices son adyacentes si están unidos mediante una arista.
Véase también Vecindad.
 
Un árbol no posee ciclos.

ÁrbolEditar

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 ciencias de la computación (véase árbol).

ArcoEditar

Véase Arista.
 
Vértices unidos por una arista.

AristaEditar

Una arista o arco es una relación matemática que conecta dos vértices. Una arista dirigida es una arista de un digrafo y tiene una dirección asociada consigo, esto es, posee un vértice inicial y un vértice final. Una arista no dirigida es una donde no se distingue un vértice inicial ni uno final.

BEditar

 
Un bosque está formado por uno o más árboles.

BosqueEditar

Un bosque es un conjunto de árboles; o de forma equivalente, un bosque es un grafo acíclico.
 
Un bucle conecta un vértice consigo mismo.

BucleEditar

Un bucle o lazo (loop en inglés) en un grafo o digrafo es una arista que conecta al mismo vértice consigo mismo. Un grafo simple no puede tener bucles.
 
Orden en que se recorre un grafo en una búsqueda en anchura.

Búsqueda en anchuraEditar

La búsqueda en anchura o BFS (Breadth First Search) es un algoritmo que permite recorrer todos los vértices de un árbol de manera ordenada, recorriendo primero los vértices vecinos al inicial, luego los vértices vecinos a los recorridos en el paso anterior y así sucesivamente hasta agotar la gráfica.
 
Orden en que se recorre un grafo en una búsqueda en profundidad.

Búsqueda en profundidadEditar

La búsqueda en profundidad o DFS (Depth First Search) es un algoritmo que permite recorrer todos los vértices de un árbol de manera ordenada, avanzando sobre cada rama hasta que no haya posibilidad de continuar y luego se retrocede hasta la última bifurcación para seguir por otra rama.
Puede usarse para recorrer un grafo cualquiera si se usa un árbol generador del grafo.

CEditar

 
Un camino es una sucesión de vértices unidos por aristas.

CaminoEditar

Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor. Un camino simple es aquel que no repite vértices en su recorrido.
Dos caminos son ajenos o 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 camino euleriano recorre todas las aristas exactamente una vez (puede repetir vértices).

Camino eulerianoEditar

Un camino euleriano en un grafo es un camino que usa cada arista una y sólo una vez. Si existe tal camino decimos que el grafo es euleriano. Esta definición es dual a la de camino hamiltoniano.
 
Un camino hamiltoniano recorre todos los vértices exactamente una vez.

Camino hamiltonianoEditar

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.
 
Orden en que se recorre un grafo en una búsqueda en profundidad.

CicloEditar

Un Ciclo (o circuito) es un camino que empieza y acaba en el mismo vértice. Los ciclos de longitud 1 se denominan lazos o bucles.
Un ciclo simple es un ciclo que tiene como longitud al menos 3 y en el que el vértice inicial coincide con el vértice final.
 
Un ciclo euleriano pasa por todas las aristas exactamente una vez, regresando al punto de partida.

Ciclo eulerianoEditar

Un ciclo euleriano en un grafo es un ciclo que usa cada arista una y sólo una vez.
 
Un ciclo hamiltoniano pasa por todos los vértices exactamente una vez, regresando al punto de partida.

Ciclo hamiltonianoEditar

Un ciclo hamiltoniano en un grafo es un ciclo que visita cada vértice una y sólo una vez
 
No hay ciclos de longitud mayor a cuatro.

CircunferenciaEditar

La circunferencia de un grafo es la longitud de su ciclo simple más largo.

CliqueEditar

Una clique en un grafo es un conjunto de vértices tal que para todo par de vértices, existe una arista que las conecta. En el ejemplo, los vértices 1, 2 y 5 forman una clique de tamaño 3. En otras palabras, es un subgrafo completo  .

Cobertura de vérticesEditar

La cobertura de vértices, covering o recubrimiento de vértices de un grafo es un conjunto de vértices cuyos elementos son adyacentes a todos los demás vértices del grafo.

Coloración de grafosEditar

La coloración de grafos es quizá el problema NP-completo más afamado de la teoría de grafos, y consiste en asignarle distintos colores o marcas a los vértices de un grafo, de manera que ningún par de vértices adyacentes compartan el mismo color o marca.

Contracción (de aristas)Editar

La contracción es una operación que elimina una arista del grafo al mismo tiempo que fusiona los dos vértices extremos. La contracción es una operación fundamental en la teoría de grafos.

Componente fuertemente conexoEditar

Un componente fuertemente conexo es un grafo tal que para cada par de vértices, existe un camino de uno hacia el otro, y viceversa. Los componentes fuertemente conexos de un grafo dirigido son sus subgrafos máximos fuertemente conexos. Estos subgrafos forman una partición del grafo.

Conjunto estableEditar

Véase Conjunto independiente.

Conjunto independienteEditar

Un conjunto independiente en un grafo es un conjunto de vértices tal que ninguno es adyacente a otro. En el ejemplo, los vértices 1,3, y 6 forman un conjunto tal y los 3,5, y 6 forman otro conjunto independiente.

CoveringEditar

Véase Cobertura de vértices.

DEditar

Depth First SearchEditar

Véase Búsqueda en profundidad.

DFSEditar

Véase Búsqueda en profundidad.

DigrafoEditar

Es un grafo cuyas aristas son dirigidas, es decir, cada arista posee un vértice inicial y uno final.

DistanciaEditar

Se denomina distancia entre dos vértices de un grafo al número de vértices mínimo que debe recorrerse para unirlos. La distancia entre dos nodos de un grafo es la longitud del camino más corto

EEditar

EulerianoEditar

Véase Ciclo euleriano.

GEditar

GirthEditar

El girth o cintura 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.

GradoEditar

El grado o valencia de un vértice es el número de aristas incidentes en él. Para un grafo con bucles, éstos son contados por dos. En el ejemplo, los vértices 1 y 3 tienen grado 2; los vértices 2, 4 y 5, grado 3; y el vértice 6, grado 1.
En un digrafo, podemos distinguir el grado saliente (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.

GrafoEditar

Un grafo es un conjunto de vértice o nodos unidos por aristas o arcos.

Grafo acíclicoEditar

Un grafo se dice acíclico si no contiene ningún ciclo simple.

Grafo bipartitoEditar

Un grafo bipartito 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 bipartito si no hay ciclos de longitud impar. Véase también grafo bipartito completo.
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 bipartito.
Un grafo k-partido se dice semiregular si cada partición tiene un grado uniforme.

Grafo completoEditar

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 aristas (correspondiendo a todas las posibles elecciones de pares de vértices).

Grafo conexoEditar

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.
Un grafo es k-conexo si y sólo si contiene k caminos independientes entre cualesquiera dos vértices. Teorema de Menger El grafo ejemplo es conexo (y por tanto 1-conexo), pero no es 2-conexo.

Grafo densoEditar

Un grafo denso es un grafo en el que el número de aristas está cercano al número de máximo de aristas. Lo opuesto, un grafo con solo algunas aristas, es un grafo disperso.

Grafo dirigidoEditar

Es un conjunto de vértices V y un conjunto de aristas E tal que para cada arista perteneciente al conjunto de aristas E se asocia con dos vértices en forma ordenada.
Véase Digrafo.

Grafo nuloEditar

El grafo nulo es el grafo cuyos conjuntos de aristas y de vértices son vacíos.

Grafo planoEditar

Un grafo plano es uno que es posible dibujar en el plano sin que ningún par de aristas se interseque. El del ejemplo lo es; el grafo completo de n vértices, para n > 4, no es plano.

Grafo ponderadoEditar

Un grafo ponderado asocia un valor o peso a cada arista en el grafo. El peso de un camino en un grafo con pesos es la suma de los pesos de todas las aristas atravesadas.

Grafo regularEditar

Un grafo regular es un grafo cuyos vértices tienen todos el mismo grado.

Grafo simpleEditar

Un grafo simple es un grafo o digrafo que no tiene bucles, y que no es un multigrafo.

Grafo trivialEditar

Un grafo trivial es un grafo vacío con un único vértice.

Grafo universalEditar

Un grafo universal en una clase K de grafos es un grafo en el que puede incluirse como subgrafo todo elemento de K.

Grafo vacíoEditar

Un grafo vacío es el grafo cuyo conjunto de aristas es vacío.

HEditar

HamiltonianoEditar

Véase Camino hamiltoniano.

HipergrafoEditar

Un hipergrafo es una generalización de un grafo, cuyas aristas aquí se llaman hiperaristas, y pueden relacionar a cualquier cantidad de vértices, en lugar de sólo un máximo de dos como en el caso particular.

IEditar

IncidenciaEditar

Véase Vecindad.

IsomorfismoEditar

Un Isomorfismo de grafos entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices   que preserva la relación de adyacencia. Es decir, cualquier par de vértices u y v de G son adyacentes si y solo si lo son sus imágenes, f(u) y f(v), en H.

LEditar

Lista de adyacenciaEditar

Una lista de adyacencia es una representación de todas las aristas o arcos de un grafo mediante una lista.

Lista de gradosEditar

LoopEditar

Véase Bucle.

MEditar

Matriz de adyacenciaEditar

Una matriz de adyacencia es una matriz de n x n que permite representar un grafo o digrafo finito, donde cada valor en la posición (i, j) representa el número de aristas desde el vértice i-ésimo al j-ésimo.

NEditar

NodoEditar

Véase Vértice.

Número cromáticoEditar

El número cromático es el mínimo de colores necesarios para colorear los vértices de un grafo. El número cromático de un grafo   es  .

OEditar

OrdenEditar

Se llama orden del grafo   a su número de vértices, designado como  .

PEditar

PuenteEditar

Un puente a es una arista tal que si la quitamos nos quedamos con un grafo con una componente conexa más que el original.

Punto de articulaciónEditar

Véase Vértice de corte.

Punto de corteEditar

Véase Vértice de corte.

REditar

Recubrimiento de vérticesEditar

Véase Cobertura de vértices.

SEditar

SubárbolEditar

Un subárbol de un grafo G es un subgrafo que es además un árbol.

SubgrafoEditar

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 aristas de G, y tal que la aplicación w es la restricción de la aplicación de G.

Subgrafo de expansiónEditar

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.

TEditar

Teoría espectralEditar

La teoría espectral es aquella que estudia las relaciones entre las propiedades de la matriz de adyacencia y las de su grafo.

TorneoEditar

Un torneo es un grafo dirigido completo, simple, no generalizado, no degenerado y sin dígonos.

VEditar

ValenciaEditar

Véase Grado.

VecindadEditar

Dos vértices son vecinos, adyacentes o incidentes si existe una arista entre ellos. En el ejemplo, el vértice 1 tiene dos vecinos: el vértice 2 y el 5. Para un grafo simple, el número de vecinos de un vértice es igual a su grado.

VérticeEditar

Un vértice o nodo es la unidad fundamental de la que están formados los grafos.

Vértice de corteEditar

Un vértice de corte es un vértice tal que si lo quitamos nos quedamos con un grafo con más componentes conexas que el original.