Revision 64522252 of "Anexo:Glosario de teoría de grafos" on eswiki

[[Archivo:Grafo simple.svg|thumb|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.
__NOTOC__
{{Índice}}
{{clear}}
== A ==
{|  valign="top" style="vertical-align:top;"
| width="150px" | [[Imagen:Grafo - Vértices adyacentes.svg|thumb|left|120px|Vértices '''adyacentes''' unidos por una arista.]]
|valign="top"|
===Adyacencia=== 
: En un grafo, los vertices son adyacentes si están unidos mediante una arista.
:: ''Véase también [[#Vecindad|Vecindad]]''.
|-
|[[Imagen:Grafo - Árbol.svg|thumb|left|120px|Un '''árbol''' no posee ciclos.]]
|valign="top"|
===Árbol===
: Un '''[[árbol (teoría de grafos)|árbol]]''' es un [[grafo conexo]] [[#Grafo simple|simple]] [[#Grafo acíclico|acíclico]]. Algunas veces, un vértice del árbol es distinguido llamándolo ''raíz''. Los árboles se usan frecuentemente como [[estructura de datos|estructuras de datos]] en [[ciencias de la computación]] (véase [[árbol (informática)|árbol]]).
|-
|
|
===Arco===
: ''Véase [[#Arista|Arista]]''.
|-
|[[Imagen:Grafo - Arista.svg|thumb|left|120px|Vértices unidos por una '''arista'''.]]
|valign="top"|
=== Arista===
: Una '''[[Arista (teoría de grafos)|arista]]''' o '''arco''' es una [[relación matemática]] que conecta dos vértices. Una '''arista dirigida''' es una arista de un [[#digrafo|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.
|}

== B ==
{|  valign="top" style="vertical-align:top;"
| width="150px" | [[Imagen:Grafo - Bosque.svg|thumb|left|120px|Un '''bosque''' está formado por uno o más árboles.]]
|valign="top"|
===Bosque===
: Un '''bosque''' es un conjunto de [[Árbol (teoría de grafos)|árboles]]; o de forma equivalente, un bosque es un [[#Grafo acíclico|grafo acíclico]].
|-
|  [[Imagen:Grafo - Bucle.svg|thumb|left|120px|Un '''bucle''' conecta un vértice consigo mismo.]]
| valign="top" | 
===Bucle===
: Un '''[[Bucle (teoría de grafos)|bucle]]''' o '''lazo''' (''loop'' en inglés) en un grafo o [[#Digrafo|digrafo]] es una arista que conecta al mismo vértice consigo mismo. Un grafo simple no puede tener bucles.
|-
| [[Imagen:Grafo - BFS.svg|thumb|left|120px|Orden en que se recorre un grafo en una '''búsqueda en anchura'''.]]
| valign="top" | 
===Búsqueda en anchura===
: 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.
|-
| [[Imagen:Grafo - DFS.svg|thumb|left|120px|Orden en que se recorre un grafo en una '''búsqueda en profundidad'''.]]
| valign="top" | 
===Búsqueda en profundidad===
: 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.
|}

== C ==

=== Camino ===
: Un '''[[Camino (teoría de grafos)|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 en que todas las aristas del camino son diferentes.
: 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..

=== Camino euleriano ===
: 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]].

=== Camino hamiltoniano ===
: 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.

=== Ciclo ===
: Un '''[[Grafo ciclo|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.

=== Ciclo euleriano ===
: Un '''[[ciclo euleriano]]''' en un grafo es un [[grafo ciclo|ciclo]] que usa cada arista una y sólo una vez. 

=== Ciclo hamiltoniano ===
: Un '''[[ciclo hamiltoniano]]''' en un grafo es un [[grafo ciclo|ciclo]] que visita cada vértice una y sólo una vez.
===Circunferencia===
: La '''[[circunferencia (grafo)|circunferencia]]''' de un grafo es la longitud de su ciclo más largo.
=== Clique ===
: 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.

=== Cobertura de vértices ===
: 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 grafos ===
: 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)===
: La '''[[Contracción de aristas|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 conexo ===
: Un '''[[componente fuertemente conexo]]''' es un grafo tal que para cada par de vértices, existe un [[#Camino|camino]] de uno hacia el otro, y viceversa. Los componentes fuertemente conexos de un [[#grafo dirigido|grafo dirigido]] son sus [[#subgrafo|subgrafos]] máximos fuertemente conexos. Estos subgrafos forman una [[partición (matemática)|partición]] del grafo.

=== Conjunto estable ===
: ''Véase [[#Conjunto independiente|Conjunto independiente]]''.

=== Conjunto independiente ===
: 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.

=== Covering ===
: ''Véase [[#Cobertura de vértices|Cobertura de vértices]]''.

== D ==

=== Depth First Search ===
: ''Véase [[#Búsqueda en profundidad|Búsqueda en profundidad]]''.

=== DFS ===
: ''Véase [[#Búsqueda en profundidad|Búsqueda en profundidad]]''.

=== Digrafo ===
: Es un grafo cuyas aristas son dirigidas, es decir, cada arista posee un vértice inicial y uno final.
===Distancia===
: Se denomina '''[[Distancia (teoría de grafos)|distancia]]''' entre dos [[vértice (teoría de grafos)|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
==E==
===Euleriano===
: ''Véase [[#Ciclo euleriano|Ciclo euleriano]]''.
== G ==

=== Girth ===
: 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]].

=== Grado ===
: El '''[[grado (teoría de grafos)|grado]]''' o '''[[grado (teoría de grafos)|valencia]]''' de un vértice es el número de ''aristas incidentes'' en él. Para un grafo con [[Bucle (teoría de grafos)|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 [[dígrafo]], podemos distinguir el '''[[grado (teoría de grafos)|grado saliente]]''' (el número de ''aristas'' que dejan el vértice) y el '''[[grado (teoría de grafos)|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.

=== Grafo ===
: Un '''[[grafo]]''' es un conjunto de [[Teoría de grafos#Vértice|vértice]] o '''[[Teoría de grafos#Vértice|nodos]] unidos por [[Arista (teoría de grafos)|aristas]] o [[Arista (teoría de grafos)|arcos]].

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

=== Grafo bipartito ===
: 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 bipartido 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 bipartido.
: Un grafo ''k''-partido se dice '''semiregular''' si cada partición tiene un grado uniforme.

=== Grafo completo ===
: 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 ''K<sub>n</sub>''. Tiene ''n''(''n''-1)/2 aristas (correspondiendo a todas las posibles elecciones de pares de vértices).

=== Grafo conexo ===
: Si es posible formar un camino desde cualquier vértice a cualquier otro en el grafo, decimos que el grafo es '''[[Grafo conexo|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 denso===
: 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 dirigido ===
: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|Digrafo]]''.

=== Grafo nulo ===
: El '''[[grafo nulo]]''' es el grafo cuyos conjuntos de aristas y de vértices son [[conjunto vacío|vacíos]].

=== Grafo plano ===
: 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 ponderado ===
: 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 regular ===
: Un '''[[grafo regular]]''' es un grafo cuyos vértices tienen todos el mismo [[Grado (teoría de grafos)|grado]].

=== Grafo simple ===
: Un '''grafo simple''' es un grafo o ''digrafo'' que no tiene bucles, y que no es un [[multigrafo]].

=== Grafo trivial ===
: Un '''[[grafo trivial]]''' es un ''grafo vacío'' con un único vértice.

=== Grafo universal ===
: 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ío ===
: Un '''grafo vacío''' es el grafo cuyo conjunto de aristas es [[conjunto vacío|vacío]].
==H==
===Hamiltoniano===
: ''Véase [[#Camino hamiltoniano|Camino hamiltoniano]]''.
===Hipergrafo===
: Un '''[[hipergrafo]]''' es una generalización de un [[grafo]], cuyas [[arista (teoría de grafos)|aristas]] aquí se llaman [[hiperarista]]s, y pueden relacionar a cualquier cantidad de [[vértice (teoría de grafos)|vértices]], en lugar de sólo un máximo de dos como en el caso particular.
== I ==

=== Incidencia ===
: ''Véase [[#Vecindad|Vecindad]]''.
===Isomorfismo===
: Un '''[[Isomorfismo de grafos]]''' entre dos [[grafo]]s ''G'' y ''H'' es una [[biyección]] ''f'' entre los conjuntos de sus [[vértice (teoría de grafos)|vértices]] <math> f: V(G) \rightarrow V(H) </math> 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''.

== L ==
===Lista de adyacencia===
: Una '''[[lista de adyacencia]]''' es una representación de todas las [[arista (teoría de grafos)|aristas]] o arcos de un [[grafo]] mediante una [[Lista (informática)|lista]].
===Lista de grados===
=== Loop ===
: ''Véase [[#Bucle|Bucle]]''.

== M ==

=== Matriz de adyacencia ===
: Una '''[[matriz de adyacencia]]''' es una [[Matriz (matemática)|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. 

== N ==

=== Nodo ===
: ''Véase [[#Vértice|Vértice]]''.
===Número cromático===
: 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 <math>G \,</MATH> es <math>\chi(G)</math>.
==O==
===Orden===
: Se llama '''orden''' del grafo <math>G</math> a su número de vértices, designado como <math>|V|</math>.
== P ==

=== Puente ===
: 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ón ===
: ''Véase [[#Vértice de corte|Vértice de corte]]''.

=== Punto de corte ===
: ''Véase [[#Vértice de corte|Vértice de corte]]''.

== R ==

=== Recubrimiento de vértices ===
: ''Véase [[#Cobertura de vértices|Cobertura de vértices]]''.

== S ==

=== Subárbol ===
: Un '''subárbol''' de un grafo ''G'' es un subgrafo que es además un árbol.

=== Subgrafo ===
: 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ón ===
: 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.

== T ==

=== Teoría espectral ===
: La '''[[teoría espectral]]''' es aquella que estudia las relaciones entre las propiedades de la matriz de adyacencia y las de su grafo.

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

== V ==

=== Valencia ===
: ''Véase [[#Grado|Grado]]''.

=== Vecindad ===
: 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értice ===
: Un '''[[Teoría de grafos#Vértice|vértice]]''' o '''[[Teoría de grafos#Vértice|nodo]]''' es la unidad fundamental de la que están formados los grafos.

=== Vértice de corte ===
: 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. 

[[Categoría:Teoría de grafos|*]]
[[Categoría:Anexos:Glosarios de matemáticas|Teoria de grafos]]

[[de:Glossar Graphentheorie]]
[[he:תת גרף]]
[[ru:Словарь терминов теории графов]]