Difference between revisions 62250503 and 62466628 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)

=== 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 ===
(contracted; show full)
: 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 veértices V y un conjunto de aristas E tal que para cada arista perteneciente al conjunto de aristas E se asocia con dos veé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 ===
(contracted; show full): 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]].

⏎
== I ==

=== Incidencia ===
: ''Véase [[#Vecindad|Vecindad]]''.

== L ==⏎
==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]]''.
(contracted; show full)[[fr:Lexique de la théorie des graphes]]
[[he:תת גרף]]
[[it:Glossario di teoria dei grafi]]
[[ko:그래프 이론 용어사전]]
[[pl:Podgraf]]
[[ru:Словарь терминов теории графов]]
[[th:อภิธานศัพท์ทฤษฎีกราฟ]]
[[vi:Thuật ngữ lý thuyết đồ thị]]