Difference between revisions 64522252 and 65477648 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;"
(contracted; show full)
===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 ==

{|  valign="top" style="vertical-align:top;"
| width="150px" | [[Imagen:Grafo - camino.svg|thumb|left|120px|Un '''camino''' es una sucesión de vértices unidos por aristas.]]
|valign="top"|
=== 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..
|-
| [[Imagen:Grafo - camino euleriano.svg|thumb|left|120px|Un '''camino''' euleriano recorre todas las aristas exactamente una vez (puede repetir vértices).]]
| valign="top" | 
=== 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]].
|-
| [[Imagen:Grafo - camino hamiltoniano.svg|thumb|left|120px|Un '''camino hamiltoniano''' recorre todos los vértices exactamente una vez.]]
| valign="top" | 
=== 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.
|-
| [[Imagen:Grafo - ciclo simple.svg|thumb|left|120px|Orden en que se recorre un grafo en una '''búsqueda en profundidad'''.]]
| valign="top" | 
==== 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.e denominan lazos o bucles. 
: 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. ⏎
inicial coincide con el vértice final.
|-
| [[Imagen:Grafo - ciclo euleriano.svg|thumb|left|120px|Orden en que se recorre un grafo en una '''búsqueda en profundidad'''.]]
| valign="top" | 
=== Ciclo euleriano ===
: Un '''[[ciclo euleriano]]''' en un grafo es un [[grafo ciclo|ciclo]] que usa cada arista una y sólo una vez. 
|-
| [[Imagen:Grafo - ciclo hamiltoniano.svg|thumb|left|120px|Orden en que se recorre un grafo en una '''búsqueda en profundidad'''.]]
| valign="top" | 
=== Ciclo hamiltoniano ===
: Un '''[[ciclo hamiltoniano]]''' en un grafo es un [[grafo ciclo|ciclo]] que visita cada vértice una y sólo una vez.
|-
| 
| valign="top" | ⏎
===Circunferencia===
: La '''[[circunferencia (grafo)|circunferencia]]''' de un grafo es la longitud de su ciclo más largo.
|-
| 
| valign="top" | ⏎
=== 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.
|-
| 
| valign="top" | 
=== 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.
|-
| 
| valign="top" | 
=== 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.
|-
| 
| valign="top" | ⏎
===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. 
|-
| 
| valign="top" | ⏎
=== 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.
|-
| 
| valign="top" | 
=== Conjunto estable ===
: ''Véase [[#Conjunto independiente|Conjunto independiente]]''.
|-
| 
| valign="top" | 
=== 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.
|-
| 
| valign="top" | 
=== 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 ===
(contracted; show full): 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:Словарь терминов теории графов]]