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.
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.
B
Un bosque está formado por uno o más árboles.
Bosque
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.
Bucle
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 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.
Orden en que se recorre un grafo en una búsqueda en profundidad.
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
Un camino es una sucesión de vértices unidos por aristas.
Camino
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 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.
Un camino hamiltoniano recorre todos los vértices exactamente una vez.
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.
Orden en que se recorre un grafo en una búsqueda en profundidad.
Ciclo
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 no se repiten vértices.
Un ciclo euleriano pasa por todas las aristas exactamente una vez, regresando al punto de partida.
Ciclo euleriano
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.
La circunferencia de un grafo es la longitud de su ciclo simple 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 los 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é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 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 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.
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.
Es un grafo cuyas aristas son dirigidas, es decir, cada arista posee un vértice inicial y uno final.
Distancia
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
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.
Grado
El grado o valencia de un vértice es el número de aristas incidentes en él. Para un grafo con bucles, estos 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.
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 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 completo
Un grafo completo es un grafo simple en el que cada vértice es adyacente a cualquier 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 conexo
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 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.
El grafo nulo es el grafo cuyos conjuntos de aristas y de vértices son 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.
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 vacío.
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.
Un Isomorfismo de grafos entre dos grafosG y H es una biyecciónf 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.
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.
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.
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 vértice o 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.
Diciembre 08, 2022
anexo, glosario, teoría, grafos, este, artículo, sección, contiene, definición, diccionario, contenido, enciclopédico, debería, estar, wikcionario, buscar, wikcionario, recuerda, contenidos, diccionario, real, academia, española, mayoría, diccionarios, present. Este articulo o seccion contiene una definicion de diccionario contenido no enciclopedico que deberia estar en Wikcionario buscar en Wikcionario Recuerda que los contenidos del Diccionario de la Real Academia Espanola y de la mayoria de los diccionarios presentan derechos de autor Grafo simple no dirigido con 6 vertices y 7 aristas A continuacion se detallan los principales conceptos de la teoria de grafos Para las definiciones formales o mas detalladas puede dirigirse al articulo principal correspondiente Todos los ejemplos estan basados en la imagen de la derecha Indice A B C D E F G H I J K L M N N O P Q R S T U V W X Y ZA Editar Vertices adyacentes unidos por una arista Adyacentes Editar En un grafo los vertices son adyacentes si estan unidos mediante una arista Vease tambien Vecindad dd Un arbol no posee ciclos Arbol Editar Un arbol es un grafo conexo simple aciclico Algunas veces un vertice del arbol es distinguido llamandolo raiz Los arboles se usan frecuentemente como estructuras de datos en ciencias de la computacion vease arbol Arco Editar Vease Arista Vertices unidos por una arista Arista Editar Una arista o arco es una relacion matematica que conecta dos vertices Una arista dirigida es una arista de un digrafo y tiene una direccion asociada consigo esto es posee un vertice inicial y un vertice final Una arista no dirigida es una donde no se distingue un vertice inicial ni uno final B Editar Un bosque esta formado por uno o mas arboles Bosque Editar Un bosque es un conjunto de arboles o de forma equivalente un bosque es un grafo aciclico Un bucle conecta un vertice consigo mismo Bucle Editar Un bucle o lazo loop en ingles en un grafo o digrafo es una arista que conecta al mismo vertice consigo mismo Un grafo simple no puede tener bucles Orden en que se recorre un grafo en una busqueda en anchura Busqueda en anchura Editar La busqueda en anchura o BFS Breadth First Search es un algoritmo que permite recorrer todos los vertices de un arbol de manera ordenada recorriendo primero los vertices vecinos al inicial luego los vertices vecinos a los recorridos en el paso anterior y asi sucesivamente hasta agotar la grafica Orden en que se recorre un grafo en una busqueda en profundidad Busqueda en profundidad Editar La busqueda en profundidad o DFS Depth First Search es un algoritmo que permite recorrer todos los vertices de un arbol de manera ordenada avanzando sobre cada rama hasta que no haya posibilidad de continuar y luego se retrocede hasta la ultima bifurcacion para seguir por otra rama Puede usarse para recorrer un grafo cualquiera si se usa un arbol generador del grafo C Editar Un camino es una sucesion de vertices unidos por aristas Camino Editar Un camino es una sucesion de vertices tal que de cada uno de sus vertices existe una arista hacia el vertice sucesor Un camino simple es aquel que no repite vertices en su recorrido Dos caminos son ajenos o independientes si no tienen ningun vertice en comun excepto el primero y el ultimo La longitud de un camino es el numero de aristas que usa dicho camino contando aristas recorridas varias veces el mismo numero 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 vertices Camino euleriano Editar Un camino euleriano en un grafo es un camino que usa cada arista una y solo una vez Si existe tal camino decimos que el grafo es euleriano Esta definicion es dual a la de camino hamiltoniano Un camino hamiltoniano recorre todos los vertices exactamente una vez Camino hamiltoniano Editar Existe un concepto dual al de camino ciclo Euleriano Un camino hamiltoniano en un grafo es un camino que visita cada vertice una y solo una vez Orden en que se recorre un grafo en una busqueda en profundidad Ciclo Editar Un Ciclo o circuito es un camino que empieza y acaba en el mismo vertice 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 no se repiten vertices Un ciclo euleriano pasa por todas las aristas exactamente una vez regresando al punto de partida Ciclo euleriano Editar Un ciclo euleriano en un grafo es un ciclo que usa cada arista una y solo una vez Un ciclo hamiltoniano pasa por todos los vertices exactamente una vez regresando al punto de partida Ciclo hamiltoniano Editar Un ciclo hamiltoniano en un grafo es un ciclo que visita cada vertice una y solo una vez No hay ciclos de longitud mayor a cuatro Circunferencia Editar La circunferencia de un grafo es la longitud de su ciclo simple mas largo Clique Editar Una clique en un grafo es un conjunto de vertices tal que para todo par de vertices existe una arista que los conecta En el ejemplo los vertices 1 2 y 5 forman una clique de tamano 3 En otras palabras es un subgrafo completo K n displaystyle K n Cobertura de vertices Editar La cobertura de vertices covering o recubrimiento de vertices de un grafo es un conjunto de vertices cuyos elementos son adyacentes a todos los demas vertices del grafo Coloracion de grafos Editar La coloracion de grafos es quiza el problema NP completo mas afamado de la teoria de grafos y consiste en asignarle distintos colores o marcas a los vertices de un grafo de manera que ningun par de vertices adyacentes compartan el mismo color o marca Contraccion de aristas Editar La contraccion es una operacion que elimina una arista del grafo al mismo tiempo que fusiona los dos vertices extremos La contraccion es una operacion fundamental en la teoria de grafos Componente fuertemente conexo Editar Un componente fuertemente conexo es un grafo tal que para cada par de vertices existe un camino de uno hacia el otro y viceversa Los componentes fuertemente conexos de un grafo dirigido son sus subgrafos maximos fuertemente conexos Estos subgrafos forman una particion del grafo Conjunto estable Editar Vease Conjunto independiente Conjunto independiente Editar Un conjunto independiente en un grafo es un conjunto de vertices tal que ninguno es adyacente a otro En el ejemplo los vertices 1 3 y 6 forman un conjunto tal y los 3 5 y 6 forman otro conjunto independiente Covering Editar Vease Cobertura de vertices D EditarDepth First Search Editar Vease Busqueda en profundidad DFS Editar Vease Busqueda en profundidad Digrafo Editar Es un grafo cuyas aristas son dirigidas es decir cada arista posee un vertice inicial y uno final Distancia Editar Se denomina distancia entre dos vertices de un grafo al numero de vertices minimo que debe recorrerse para unirlos La distancia entre dos nodos de un grafo es la longitud del camino mas cortoE EditarEuleriano Editar Vease Ciclo euleriano G EditarGirth Editar El girth o cintura de un grafo es la longitud del ciclo simple mas corto en el grafo El girth de un grafo aciclico se define como infinito Grado Editar El grado o valencia de un vertice es el numero de aristas incidentes en el Para un grafo con bucles estos son contados por dos En el ejemplo los vertices 1 y 3 tienen grado 2 los vertices 2 4 y 5 grado 3 y el vertice 6 grado 1 En un digrafo podemos distinguir el grado saliente el numero de aristas que dejan el vertice y el grado entrante el numero de aristas que entran en un vertice El grado de un vertice seria la suma de ambos numeros Grafo Editar Un grafo es un conjunto de vertice o nodos unidos por aristas o arcos Grafo aciclico Editar Un grafo se dice aciclico si no contiene ningun ciclo simple Grafo bipartito Editar Un grafo bipartito es cualquier grafo cuyos vertices pueden ser divididos en dos conjuntos tal que no haya aristas entre los vertices del mismo conjunto Se ve que un grafo es bipartito si no hay ciclos de longitud impar Vease tambien grafo bipartito completo Un grafo k partido o grafo k colorable es un grafo con cuyos vertices se puede hacer una particion en k subconjuntos disjuntos tal que no haya aristas entre vertices del mismo subconjunto Un grafo 2 partido es lo mismo que un grafo bipartito Un grafo k partido se dice semiregular si cada particion tiene un grado uniforme Grafo completo Editar Un grafo completo es un grafo simple en el que cada vertice es adyacente a cualquier otro vertice El del ejemplo no es completo El grafo completo en n vertices se denota a menudo por Kn Tiene n n 1 2 aristas correspondiendo a todas las posibles elecciones de pares de vertices Grafo conexo Editar Si es posible formar un camino desde cualquier vertice a cualquier otro en el grafo decimos que el grafo es conexo Si es posible hacer esto incluso tras quitar k 1 vertices decimos que el grafo es k conexo Un grafo es k conexo si y solo si contiene k caminos independientes entre cualesquiera dos vertices Teorema de Menger El grafo ejemplo es conexo y por tanto 1 conexo pero no es 2 conexo Grafo denso Editar Un grafo denso es un grafo en el que el numero de aristas esta cercano al numero de maximo de aristas Lo opuesto un grafo con solo algunas aristas es un grafo disperso Grafo dirigido Editar Es un conjunto de vertices V y un conjunto de aristas E tal que para cada arista perteneciente al conjunto de aristas E se asocia con dos vertices en forma ordenada Vease Digrafo Grafo nulo Editar El grafo nulo es el grafo cuyos conjuntos de aristas y de vertices son vacios Grafo plano Editar Un grafo plano es uno que es posible dibujar en el plano sin que ningun par de aristas se interseque El del ejemplo lo es el grafo completo de n vertices para n gt 4 no es plano Grafo ponderado Editar 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 Editar Un grafo regular es un grafo cuyos vertices tienen todos el mismo grado Grafo simple Editar Un grafo simple es un grafo o digrafo que no tiene bucles y que no es un multigrafo Grafo trivial Editar Un grafo trivial es un grafo vacio con un unico vertice Grafo universal Editar Un grafo universal en una clase K de grafos es un grafo en el que puede incluirse como subgrafo todo elemento de K Grafo vacio Editar Un grafo vacio es el grafo cuyo conjunto de aristas es vacio H EditarHamiltoniano Editar Vease Camino hamiltoniano Hipergrafo Editar Un hipergrafo es una generalizacion de un grafo cuyas aristas aqui se llaman hiperaristas y pueden relacionar a cualquier cantidad de vertices en lugar de solo un maximo de dos como en el caso particular I EditarIncidencia Editar Vease Vecindad Isomorfismo Editar Un Isomorfismo de grafos entre dos grafos G y H es una biyeccion f entre los conjuntos de sus vertices f V G V H displaystyle f V G rightarrow V H que preserva la relacion de adyacencia Es decir cualquier par de vertices u y v de G son adyacentes si y solo si lo son sus imagenes f u y f v en H L EditarLista de adyacencia Editar Una lista de adyacencia es una representacion de todas las aristas o arcos de un grafo mediante una lista Lista de grados Editar Loop Editar Vease Bucle M EditarMatriz de adyacencia Editar Una matriz de adyacencia es una matriz de n x n que permite representar un grafo o digrafo finito donde cada valor en la posicion i j representa el numero de aristas desde el vertice i esimo al j esimo N EditarNodo Editar Vease Vertice Numero cromatico Editar El numero cromatico es el minimo de colores necesarios para colorear los vertices de un grafo El numero cromatico de un grafo G displaystyle G es x G displaystyle chi G O EditarOrden Editar Se llama orden del grafo G displaystyle G a su numero de vertices designado como V displaystyle V P EditarPuente Editar Un puente a es una arista tal que si la quitamos nos quedamos con un grafo con una componente conexa mas que el original Punto de articulacion Editar Vease Vertice de corte Punto de corte Editar Vease Vertice de corte R EditarRecubrimiento de vertices Editar Vease Cobertura de vertices S EditarSubarbol Editar Un subarbol de un grafo G es un subgrafo que es ademas un arbol Subgrafo Editar Un subgrafo de un grafo G es un grafo cuyo conjunto de vertices es un subconjunto del de G cuyo conjunto de aristas es un subconjunto del conjunto de las aristas de G y tal que la aplicacion w es la restriccion de la aplicacion de G Subgrafo de expansion Editar Un subgrafo de expansion de un grafo G es un subgrafo con el mismo conjunto de vertices que G Un arbol expansion es un subgrafo expansion que es un arbol Cada grafo tiene un arbol de expansion T EditarTeoria espectral Editar La teoria espectral es aquella que estudia las relaciones entre las propiedades de la matriz de adyacencia y las de su grafo Torneo Editar Un torneo es un grafo dirigido completo simple no generalizado no degenerado y sin digonos V EditarValencia Editar Vease Grado Vecindad Editar Dos vertices son vecinos adyacentes o incidentes si existe una arista entre ellos En el ejemplo el vertice 1 tiene dos vecinos el vertice 2 y el 5 Para un grafo simple el numero de vecinos de un vertice es igual a su grado Vertice Editar Un vertice o nodo es la unidad fundamental de la que estan formados los grafos Vertice de corte Editar Un vertice de corte es un vertice tal que si lo quitamos nos quedamos con un grafo con mas componentes conexas que el original Obtenido de https es wikipedia org w index php title Anexo Glosario de teoria de grafos amp oldid 137717390, wikipedia, wiki, leyendo, leer, libro, biblioteca,