Glosario de teoría de grafos

Busque el Apéndice: Glosario de teoría de grafos en Wikcionario, el diccionario gratuito.

Este es un glosario de teoría de grafos . La teoría de grafos es el estudio de grafos , sistemas de nodos o vértices conectados de dos en dos por líneas o aristas.

Símbolos

Corchetes [ ]: $G [S]$ es el subgrafo inducido de un gráfico $G$ para el subconjunto de vértices $S$ .
Símbolo principal ': El símbolo primo se usa a menudo para modificar la notación de invariantes de gráficos de modo que se aplique al gráfico lineal en lugar del gráfico dado. Por ejemplo, $α (G)$ es el número de independencia de un gráfico; $α'(G)$ es el número coincidente del gráfico, que es igual al número de independencia de su gráfico lineal. De manera similar, $χ (G)$ es el número cromático de una gráfica; $χ'(G)$ es el índice cromático del gráfico, que es igual al número cromático de su gráfico lineal.

A

absorbente: Un conjunto absorbente de un gráfico dirigido es un conjunto de vértices tal que para cualquier vértice , hay una arista desde hacia un vértice de . $A$ $G$ $v\en G\setminus A$ $v$ $A$
acromático: El número acromático de un gráfico es el número máximo de colores en una coloración completa. ^[1]
acíclico: 1. Una gráfica es acíclica si no tiene ciclos. Un gráfico acíclico no dirigido es lo mismo que un bosque . Un gráfico dirigido acíclico, que es un dígrafo sin ciclos dirigidos, suele denominarse gráfico acíclico dirigido , especialmente en informática. ^[2]; 2. Una coloración acíclica de un gráfico no dirigido es una coloración adecuada en la que cada dos clases de color inducen un bosque. ^[3]
matriz de adyacencia: La matriz de adyacencia de un gráfico es una matriz cuyas filas y columnas están indexadas por los vértices del gráfico, con un uno en la celda para la fila $i$ y la columna $j$ cuando los vértices $i$ y $j$ son adyacentes, y un cero en caso contrario. ^[4]
adyacente: 1. La relación entre dos vértices que son ambos extremos de la misma arista. ^[2]; 2. La relación entre dos aristas distintas que comparten un vértice final. ^[5]
α: Para un gráfico $G$ , $α (G)$ (usando la letra griega alfa) es su número de independencia (ver independiente), y $α'(G)$ es su número coincidente (ver coincidencia).
alterno: En un gráfico con coincidencia, una ruta alterna es una ruta cuyos bordes alternan entre bordes coincidentes y no coincidentes. Un ciclo alterno es, de manera similar, un ciclo cuyos bordes alternan entre bordes coincidentes y no coincidentes. Un camino aumentante es un camino alterno que comienza y termina en vértices no saturados. Se puede encontrar una coincidencia mayor como la diferencia simétrica entre la ruta de coincidencia y la ruta de aumento; una coincidencia es máxima si y sólo si no tiene una ruta de aumento.
anticadena: En un gráfico acíclico dirigido , un subconjunto $S$ de vértices que son incomparables por pares, es decir, para cualquiera en $S$ , no hay un camino dirigido de $x$ a $y$ o de $y$ a $x$ . Inspirado en la noción de anticadenas en conjuntos parcialmente ordenados . $x\leq y$
anti-borde: Sinónimo de sin arista , un par de vértices no adyacentes.
anti-triángulo: Un conjunto independiente de tres vértices, complemento de un triángulo.
apéndice: 1. Un gráfico de vértices es un gráfico en el que se puede eliminar un vértice, dejando un subgrafo plano. El vértice eliminado se llama ápice. Un gráfico $de k$ -ápices es un gráfico que se puede hacer plano mediante la eliminación de $k$ vértices.; 2. Sinónimo de vértice universal , vértice adyacente a todos los demás vértices.
arborescencia: Sinónimo de árbol enraizado y dirigido; ver árbol.
arco: Ver borde.
flecha: Un par ordenado de vértices, como una arista en un gráfico dirigido. Una flecha $(x, y)$ $tiene$ una cola $x$ , una cabeza $y$ y una dirección $de xa y$ ; $Se dice que y$ es el sucesor directo de $x$ y $x$ el predecesor directo de $y$ . La flecha $(y, x)$ es la flecha invertida de la flecha $(x, y)$ .
punto de articulación: Un vértice en un gráfico conectado cuya eliminación desconectaría el gráfico.
-ario: Un árbol k -ario es un árbol enraizado en el que cada vértice interno no tiene más de $k$ hijos. Un árbol 1-ario es solo un camino. Un árbol biario también se llama árbol binario , aunque ese término se refiere más propiamente a árboles biarios en los que los hijos de cada nodo se distinguen como hijos izquierdos o derechos (con como máximo uno de cada tipo). Se dice que un árbol $k$ -ario está completo si cada vértice interno tiene exactamente $k$ hijos.
aumentando: Un tipo especial de camino alterno; ver alternancia.
automorfismo: Un automorfismo de grafo es una simetría de un grafo, un isomorfismo del grafo a sí mismo.

B

bolsa: Uno de los conjuntos de vértices en la descomposición de un árbol.
equilibrado: Un gráfico bipartito o multipartito está equilibrado si cada dos subconjuntos de su partición de vértices tienen tamaños dentro del uno del otro.
banda ancha: El ancho de banda de un gráfico $G$ es el mínimo, sobre todos los ordenamientos de vértices de $G$ , de la longitud del borde más largo (el número de pasos en el ordenamiento entre sus dos puntos finales). También es uno menos que el tamaño de la camarilla máxima en un intervalo adecuado de $G$ , elegido para minimizar el tamaño de la camarilla.
bicicleta: Sinónimo de grafo bipartito completo o subgrafo bipartito completo; ver completo.
biconectado: Generalmente es sinónimo de $2$ -vertex-connected , pero a veces incluye K ₂ aunque no está 2-conectado. Ver conectado; para componentes biconectados , consulte componente.
número vinculante: La relación más pequeña posible entre el número de vecinos de un subconjunto adecuado de vértices y el tamaño del subconjunto. ^[6]
bipartito: Un gráfico bipartito es un gráfico cuyos vértices se pueden dividir en dos conjuntos disjuntos de modo que los vértices de un conjunto no estén conectados entre sí, pero puedan estar conectados a los vértices del otro conjunto. Dicho de otra manera, un gráfico bipartito es un gráfico sin ciclos impares; De manera equivalente, es un gráfico que se puede colorear adecuadamente con dos colores. Los gráficos bipartitos a menudo se escriben $G = (U, V, E)$ donde $U$ y $V$ son los subconjuntos de vértices de cada color. Sin embargo, a menos que el gráfico esté conectado, es posible que no tenga dos colores únicos.
biregular: Un gráfico biregular es un gráfico bipartito en el que sólo hay dos grados de vértice diferentes, uno para cada conjunto de bipartición de vértices.
bloquear: 1. Un bloque de un gráfico $G$ es un subgrafo máximo que es un vértice aislado, un borde de puente o un subgrafo biconexo. Si un bloque está conectado por 2, cada par de vértices que contiene pertenecen a un ciclo común. Cada borde de un gráfico pertenece exactamente a un bloque.; 2. El gráfico de bloques de un gráfico $G$ es otro gráfico cuyos vértices son los bloques de $G$ , con una arista que conecta dos vértices cuando los bloques correspondientes comparten un punto de articulación; es decir, es la gráfica de intersección de los bloques de $G.$ El gráfico de bloques de cualquier gráfico es un bosque.; 3. El gráfico de corte de bloque (o punto de corte de bloque) de un gráfico $G$ es un gráfico bipartito donde un conjunto partito consta de los vértices de corte de $G$ y el otro tiene un vértice para cada bloque de $G.$ Cuando $G$ es conexo, su gráfico de punto de corte de bloque es un árbol. ${\ Displaystyle b_ {i}}$ ${\ Displaystyle B_ {i}}$; 4. Un gráfico de bloques (también llamado árbol de camarilla si está conectado, y a veces llamado erróneamente árbol de Husimi) es un gráfico cuyos bloques son gráficos completos. Un bosque es un gráfico de bloques; entonces, en particular, el gráfico de bloques de cualquier gráfico es un gráfico de bloques, y cada gráfico de bloques puede construirse como el gráfico de bloques de un gráfico.
vínculo: Un conjunto de corte mínimo: un conjunto de aristas cuya eliminación desconecta el gráfico, para el cual ningún subconjunto adecuado tiene la misma propiedad.
libro: 1. Un libro , libro gráfico o libro triangular es un gráfico tripartito completo $K 1,1, n$ ; una colección de $n$ triángulos unidos por un borde compartido.; 2. Otro tipo de gráfico, también llamado libro o libro cuadrilátero, es una colección de $4$ ciclos unidos en un borde compartido; el producto cartesiano de una estrella con arista.; 3. La incrustación de un libro es la incrustación de un gráfico en un libro topológico, un espacio formado al unir una colección de semiplanos a lo largo de una línea compartida. Por lo general, se requiere que los vértices de la incrustación estén en la línea, que se llama lomo de la incrustación, y los bordes de la incrustación deben estar dentro de un único semiplano, una de las páginas del libro.
Perímetro: 1. En una incrustación de gráficos , un recorrido por los límites es el subgrafo que contiene todos los bordes y vértices incidentes en una cara.
zarza: Una zarza es una colección de subgrafos conectados que se tocan mutuamente, donde dos subgrafos se tocan si comparten un vértice o cada uno incluye un punto final de un borde. El orden de una zarza es el tamaño más pequeño de un conjunto de vértices que tiene una intersección no vacía con todos los subgrafos. El ancho de árbol de un gráfico es el orden máximo de cualquiera de sus zarzas.
rama: Un camino de vértices de grado dos, que termina en vértices cuyo grado es desigual a dos. ^[7]
descomposición de ramas: Una descomposición en ramas de $G$ es una agrupación jerárquica de los bordes de $G$ , representada por un árbol binario sin raíz con sus hojas etiquetadas por los bordes de $G.$ El ancho de una descomposición de rama es el máximo, sobre los bordes $e$ de este árbol binario, del número de vértices compartidos entre los subgrafos determinados por los bordes de $G$ en los dos subárboles separados por $e$ . El ancho de rama de $G$ es el ancho mínimo de cualquier descomposición de rama de $G$ .
ancho de rama: Ver descomposición en ramas.
puente: 1. Un puente , istmo o borde de corte es un borde cuya eliminación desconectaría el grafo. Un grafo sin puentes es aquel que no tiene puentes; equivalentemente, un gráfico de 2 aristas conectadas.; 2. Especialmente en el contexto de las pruebas de planaridad , un puente de un ciclo es un subgrafo máximo que está separado del ciclo y en el que cada dos aristas pertenecen a una ruta que está internamente separada del ciclo. Un acorde es un puente de un solo borde. Un ciclo periférico es un ciclo con como máximo un puente; debe ser una cara en cualquier incrustación plana de su gráfico.; 3. Un puente de un ciclo también puede significar un camino que conecta dos vértices de un ciclo pero es más corto que cualquiera de los caminos del ciclo que conecta los mismos dos vértices. Un gráfico puenteado es un gráfico en el que cada ciclo de cuatro o más vértices tiene un puente.
sin puente: Un gráfico sin puente es un gráfico que no tiene aristas de puente; es decir, un gráfico de 2 aristas conectadas .
mariposa: 1. El gráfico de mariposa tiene cinco vértices y seis aristas; está formado por dos triángulos que comparten un vértice.; 2. La red mariposa es un gráfico utilizado como arquitectura de red en informática distribuida, estrechamente relacionado con los ciclos conectados por cubos .

C

C: $C n$ es un gráfico de ciclo $de n$ vértices; ver ciclo.
cactus: Un gráfico de cactus , árbol de cactus, cactus o árbol de Husimi es un gráfico conexo en el que cada arista pertenece como máximo a un ciclo. Sus bloques son ciclos o aristas simples. Si, además, cada vértice pertenece como máximo a dos bloques, entonces se llama cactus de Navidad.
jaula: Una jaula es un gráfico regular con el orden más pequeño posible para su circunferencia.
canónico
canonización: Una forma canónica de un gráfico es un invariante tal que dos gráficos tienen invariantes iguales si y sólo si son isomórficos. Las formas canónicas también pueden denominarse invariantes canónicas o invariantes completas y, a veces, se definen sólo para los gráficos dentro de una familia particular de gráficos. La canonización de grafos es el proceso de calcular una forma canónica.
tarjeta: Un gráfico formado a partir de un gráfico dado eliminando un vértice, especialmente en el contexto de la conjetura de reconstrucción . Véase también mazo, el conjunto múltiple de todas las cartas de un gráfico.
ancho de talla: El ancho de tallado es una noción de ancho de gráfico análoga al ancho de rama, pero que utiliza agrupaciones jerárquicas de vértices en lugar de agrupaciones jerárquicas de bordes.
oruga: Un árbol oruga u oruga es un árbol en el que los nodos internos inducen un camino.
centro: El centro de un gráfico es el conjunto de vértices de mínima excentricidad.
cadena: 1. Sinónimo de caminar.; 2. Al aplicar métodos de topología algebraica a gráficos, un elemento de un complejo de cadena , es decir, un conjunto de vértices o un conjunto de aristas.
constante de alegría: Ver expansión.
cereza: Una cereza es un camino en tres vértices. ^[8]
χ: $χ (G)$ (usando la letra griega chi) es el número cromático de $G$ y $χ'(G)$ es su índice cromático; ver cromática y coloración.
niño: En un árbol enraizado, un hijo de un vértice $v$ es vecino de $v$ a lo largo de un borde saliente, uno que se aleja de la raíz.
acorde
cordal: 1. Una cuerda de un ciclo es una arista que no pertenece al ciclo, por lo que ambos extremos pertenecen al ciclo.; 2. Un grafo cordal es un grafo en el que cada ciclo de cuatro o más vértices tiene una cuerda, por lo que los únicos ciclos inducidos son los triángulos.; 3. Un gráfico fuertemente cordal es un gráfico cordal en el que cada ciclo de longitud seis o más tiene una cuerda impar.; 4. Un grafo bipartito cordal no es cordal (a menos que sea un bosque); Es un gráfico bipartito en el que cada ciclo de seis o más vértices tiene una cuerda, por lo que los únicos ciclos inducidos son de 4 ciclos.; 5. Una cuerda de un círculo es un segmento de línea que conecta dos puntos del círculo; La gráfica de intersección de una colección de cuerdas se llama gráfica circular .
cromático: Relativo a la coloración; ver color. La teoría de grafos cromáticos es la teoría de la coloración de grafos. El número cromático χ $(G) es$ el número mínimo de colores necesarios para una coloración adecuada de $G.$ $χ'(G)$ es el índice cromático de $G$ , el número mínimo de colores necesarios para una coloración de borde adecuada de $G$ .
seleccionable
capacidad de elección: Un gráfico es $k$ seleccionable si tiene una lista de colores siempre que cada vértice tenga una lista de $k$ colores disponibles. La posibilidad de elección del gráfico es la $k más pequeña para$ $la$ cual se puede elegir.
círculo: Una gráfica circular es la gráfica de intersección de las cuerdas de un círculo.
circuito: Un circuito puede referirse a un sendero cerrado o a un elemento del espacio ciclista (un subgrafo que abarca a Euler). El rango de circuito de un gráfico es la dimensión de su espacio de ciclo.
circunferencia: La circunferencia de un gráfico es la longitud de su ciclo simple más largo. La gráfica es hamiltoniana si y sólo si su circunferencia es igual a su orden.
clase: 1. Una clase de gráficos o familia de gráficos es una colección (generalmente infinita) de gráficos, a menudo definida como gráfica que tiene alguna propiedad específica. Se utiliza la palabra "clase" en lugar de "conjunto" porque, a menos que se establezcan restricciones especiales (como restringir los vértices que se extraerán de un conjunto particular y definir las aristas como conjuntos de dos vértices), las clases de gráficos generalmente no son conjuntos. cuando se formaliza utilizando la teoría de conjuntos.; 2. Una clase de color de un gráfico coloreado es el conjunto de vértices o aristas que tienen un color particular.; 3. En el contexto del teorema de Vizing , al colorear gráficos simples con bordes, se dice que un gráfico es de clase uno si su índice cromático es igual a su grado máximo, y de clase dos si su índice cromático es igual a uno más el grado. Según el teorema de Vizing, todas las gráficas simples son de clase uno o clase dos.
garra: Una garra es un árbol con un vértice interno y tres hojas, o equivalentemente el gráfico bipartito completo $K 1,3$ . Un gráfico sin garras es un gráfico que no tiene un subgrafo inducido que sea una garra.
camarilla: Una camarilla es un conjunto de vértices mutuamente adyacentes (o el subgrafo completo inducido por ese conjunto). A veces, una camarilla se define como un conjunto máximo de vértices mutuamente adyacentes (o subgrafo completo máximo), uno que no forma parte de ningún conjunto (o subgrafo) más grande. Una $k$ -clique es una camarilla de orden $k$ . El número de camarilla $ω (G)$ de un gráfico $G$ es el orden de su camarilla más grande. El gráfico de camarillas de un gráfico G es el gráfico de intersección de las camarillas máximas en G. Véase también biclique, un subgrafo bipartito completo.
árbol de camarilla: Sinónimo de gráfico de bloques.
ancho de camarilla: El ancho de camarilla de un gráfico $G$ es el número mínimo de etiquetas distintas necesarias para construir $G$ mediante operaciones que crean un vértice etiquetado, forman la unión disjunta de dos gráficos etiquetados, agregan un borde que conecta todos los pares de vértices con etiquetas dadas o vuelven a etiquetar todos los vértices con una etiqueta determinada. Las gráficas de ancho de camarilla como máximo $2$ son exactamente las cografías .
cerrado: 1. Una vecindad cerrada es aquella que incluye su vértice central; ver barrio.; 2. Un paseo cerrado es aquel que comienza y termina en el mismo vértice; ver caminar.; 3. Un grafo es transitivamente cerrado si es igual a su propio cierre transitivo; ver transitivo.; 4. Una propiedad de gráfico se cierra bajo alguna operación en gráficos si, siempre que el argumento o argumentos de la operación tienen la propiedad, también la tiene el resultado. Por ejemplo, las propiedades hereditarias están cerradas bajo subgrafos inducidos; las propiedades monótonas están cerradas bajo subgrafos; y las propiedades cerradas para menores están cerradas para menores.
cierre: 1. Para el cierre transitivo de un gráfico dirigido, consulte transitivo.; 2. Un cierre de un gráfico dirigido es un conjunto de vértices que no tienen aristas de salida hacia los vértices fuera del cierre. Por ejemplo, un sumidero es un cierre de un vértice. El problema del cierre es el problema de encontrar un cierre de peso mínimo o máximo.
co-: Este prefijo tiene varios significados que generalmente involucran gráficos de complemento . Por ejemplo, un cografo es un gráfico producido por operaciones que incluyen complementación; una cocoloración es una coloración en la que cada vértice induce un conjunto independiente (como en la coloración adecuada) o una camarilla (como en la coloración del complemento).
color
colorante: 1. La coloración de un gráfico es un etiquetado de los vértices de un gráfico mediante elementos de un conjunto de colores determinado, o equivalentemente, una partición de los vértices en subconjuntos, llamados "clases de colores", cada uno de los cuales está asociado con uno de los colores.; 2. Algunos autores usan "colorear", sin calificar, para referirse a una coloración adecuada, aquella que asigna diferentes colores a los puntos finales de cada borde. Al colorear gráficos, el objetivo es encontrar una coloración adecuada que utilice la menor cantidad de colores posible; por ejemplo, los gráficos bipartitos son los gráficos que tienen coloraciones con solo dos colores, y el teorema de los cuatro colores establece que cada gráfico plano se puede colorear con un máximo de cuatro colores. Se dice que un gráfico tiene $k$ color si ha sido coloreado (correctamente) con $k$ colores, y $k$ coloreable o $k$ cromático si esto es posible.; 3. Se han estudiado muchas variaciones de coloración, incluida la coloración de bordes (colorear los bordes para que no haya dos bordes con el mismo punto final que compartan un color), la coloración de listas (coloración adecuada con cada vértice restringido a un subconjunto de los colores disponibles), la coloración acíclica (cada subgrafo de 2 colores es acíclico), co-coloración (cada clase de color induce un conjunto independiente o una camarilla), coloración completa (cada dos clases de color comparten un borde) y coloración total (tanto los bordes como los vértices están coloreados).; 4. El número de color de un gráfico es uno más la degeneración . Se llama así porque al aplicar un algoritmo de coloración codiciosa a un orden de degeneración del gráfico se utiliza como máximo esta cantidad de colores.
comparabilidad: Un gráfico no dirigido es un gráfico de comparabilidad si sus vértices son los elementos de un conjunto parcialmente ordenado y dos vértices son adyacentes cuando son comparables en el orden parcial. De manera equivalente, un gráfico de comparabilidad es un gráfico que tiene una orientación transitiva. Muchas otras clases de gráficos se pueden definir como gráficos de comparabilidad de tipos especiales de orden parcial.
complementar: El gráfico complemento de un gráfico simple $G$ es otro gráfico en el mismo conjunto de vértices que $G$ , con una arista para cada dos vértices que no son adyacentes en $G.$ ${\bar {G}}$
completo: 1. Un grafo completo es aquel en el que cada dos vértices son adyacentes: todas las aristas que podrían existir están presentes. Un gráfico completo con $n$ vértices a menudo se denota como $K n$ . Un gráfico bipartito completo es aquel en el que cada dos vértices en lados opuestos de la partición de vértices son adyacentes. Un gráfico bipartito completo con $vértices$ a en un lado de la partición y $b$ vértices en el otro lado a menudo se denota como $K a, b$ . La misma terminología y notación también se ha extendido a gráficos multipartitos completos , gráficos en los que los vértices se dividen en más de dos subconjuntos y cada par de vértices en diferentes subconjuntos son adyacentes; si los números de vértices en los subconjuntos son $a, b, c,...$ entonces esta gráfica se denota $K a, b, c,$ ....; 2. Una finalización de un gráfico dado es un supergrafo que tiene alguna propiedad deseada. Por ejemplo, una terminación cordal es un supergrafo que es un grafo cordal.; 3. Un emparejamiento completo es sinónimo de un emparejamiento perfecto ; ver coincidencia.; 4. Una coloración completa es una coloración adecuada en la que cada par de colores se utiliza para los puntos finales de al menos un borde. Toda coloración con un número mínimo de colores es completa, pero pueden existir coloraciones completas con un número mayor de colores. El número acromático de un gráfico es el número máximo de colores en una coloración completa.; 5. Un invariante completo de un gráfico es sinónimo de forma canónica, un invariante que tiene diferentes valores para gráficos no isomorfos.
componente: Un componente conectado de un gráfico es un subgrafo conectado máximo. El término también se utiliza para subgrafos máximos o subconjuntos de vértices de un gráfico que tienen algún orden superior de conectividad, incluidos componentes biconectados , componentes triconectados y componentes fuertemente conectados .
condensación: La condensación de un gráfico dirigido $G$ es un gráfico acíclico dirigido con un vértice para cada componente fuertemente conectado de G $y$ un borde que conecta pares de componentes que contienen los dos puntos finales de al menos un borde en $G.$
cono: Un gráfico que contiene un vértice universal .
conectar: Causa para estar conectado.
conectado: Un gráfico conexo es aquel en el que cada par de vértices forma los puntos finales de un camino. Las formas superiores de conectividad incluyen una fuerte conectividad en gráficos dirigidos (para cada dos vértices hay caminos de uno al otro en ambas direcciones), $k$ -gráficos conectados por vértices (eliminar menos de $k$ vértices no puede desconectar el gráfico) y $k$ -edge -Gráficos conectados (eliminar menos de $k$ aristas no puede desconectar el gráfico).
componente conectado: Sinónimo de componente.
conversar: El gráfico inverso es sinónimo de gráfico transpuesto; ver transponer.
centro: 1. Un $k$ -núcleo es el subgrafo inducido formado al eliminar todos los vértices de grado menor que $k$ , y todos los vértices cuyo grado se vuelve menor que $k$ después de eliminaciones anteriores. Ver degeneración.; 2. Un núcleo es un gráfico $G$ tal que cada homomorfismo del gráfico desde $G$ hacia sí mismo es un isomorfismo.; 3. El núcleo de un gráfico $G$ es un gráfico mínimo $H$ tal que existen homomorfismos de $G$ a $H$ y viceversa. $H$ es único hasta el isomorfismo. Puede representarse como un subgrafo inducido de $G$ y es un núcleo en el sentido de que todos sus autohomomorfismos son isomorfismos.; 4. En la teoría de las coincidencias de gráficos, el núcleo de un gráfico es un aspecto de su descomposición de Dulmage-Mendelsohn , formado como la unión de todas las coincidencias máximas.
cotree: 1. El complemento de un árbol generador .; 2. Una estructura de árbol enraizada utilizada para describir un cografo , en la que cada vértice del cografo es una hoja del árbol, cada nodo interno del árbol está etiquetado con 0 o 1, y dos vértices del cografo son adyacentes si y solo si su mínimo común El ancestro en el árbol está etiquetado como 1.
cubrir: Una cobertura de vértices es un conjunto de vértices que inciden en cada arista de un gráfico. Una cobertura de aristas es un conjunto de aristas que inciden en cada vértice de un gráfico. Un conjunto de subgrafos de un gráfico cubre ese gráfico si su unión , tomada en los vértices y en los bordes, es igual al gráfico.
crítico: Un gráfico crítico para una propiedad dada es un gráfico que tiene la propiedad pero que cada subgrafo formado al eliminar un solo vértice no tiene la propiedad. Por ejemplo, un gráfico de factores críticos es aquel que tiene una coincidencia perfecta (un factor 1) para cada eliminación de vértice, pero (debido a que tiene un número impar de vértices) no tiene una coincidencia perfecta en sí misma. Compare hipo- , usado para gráficos que no tienen una propiedad pero para los cuales cada eliminación de un vértice sí la tiene.
cubo
cúbico: 1. Gráfico de cubo , el gráfico de ocho vértices de los vértices y aristas de un cubo.; 2. Gráfico de hipercubo , una generalización de dimensiones superiores del gráfico de cubo.; 3. Gráfico de cubo plegado , formado a partir de un hipercubo agregando vértices opuestos conectados coincidentes.; 4. Gráfico de cubo dividido por la mitad , el medio cuadrado de un gráfico de hipercubo.; 5. Cubo parcial , un subgrafo de un hipercubo que preserva la distancia.; 6. El cubo de un gráfico $G$ es la potencia del gráfico $G 3$ .; 7. Gráfico cúbico , otro nombre para un gráfico $de 3$ regulares, uno en el que cada vértice tiene tres aristas incidentes.; 8. Ciclos cuboconectados , un gráfico cúbico formado reemplazando cada vértice de un hipercubo por un ciclo.
cortar
conjunto de corte: Un corte es una partición de los vértices de un gráfico en dos subconjuntos, o el conjunto (también conocido como conjunto de cortes) de aristas que abarcan dicha partición, si ese conjunto no está vacío. Se dice que una arista abarca la partición si tiene puntos finales en ambos subconjuntos. Por tanto, la eliminación de un conjunto de cortes de un gráfico conectado lo desconecta.
punto de corte: Ver punto de articulación.
cortar espacio: El espacio de corte de un gráfico es un GF (2) : espacio vectorial que tiene los conjuntos de corte del gráfico como elementos y la diferencia simétrica de conjuntos como su operación de suma de vectores.
ciclo: 1. Un ciclo puede ser una especie de gráfico o una especie de caminata. Como recorrido, puede ser un recorrido cerrado (también denominado recorrido) o, más habitualmente, un recorrido cerrado sin vértices repetidos y, en consecuencia, aristas (también denominado ciclo simple). En el último caso se suele considerar como un gráfico, es decir, las elecciones del primer vértice y la dirección normalmente se consideran sin importancia; es decir, las permutaciones cíclicas y las inversiones del recorrido producen el mismo ciclo. Los tipos especiales importantes de ciclo incluyen los ciclos hamiltonianos , los ciclos inducidos , los ciclos periféricos y el ciclo más corto, que define la circunferencia de un gráfico. Un $k$ -ciclo es un ciclo de longitud $k$ ; por ejemplo, un ciclo $de 2$ es un digon y un ciclo $de 3$ es un triángulo. Un gráfico de ciclo es un gráfico que en sí mismo es un ciclo simple; un gráfico de ciclo con $n$ vértices comúnmente se denota como $C n$ .; 2. El espacio de ciclos es un espacio vectorial generado por ciclos simples en un gráfico, a menudo sobre el campo de 2 elementos pero también sobre otros campos.

D

TROZO DE CUERO: Abreviatura de gráfico acíclico dirigido , un gráfico dirigido sin ciclos dirigidos.
cubierta: El conjunto múltiple de gráficos se formó a partir de un solo gráfico $G$ eliminando un solo vértice de todas las formas posibles, especialmente en el contexto de la conjetura de reconstrucción . Una plataforma de borde se forma de la misma manera eliminando un solo borde de todas las formas posibles. Las gráficas de una baraja también se llaman cartas . Véase también crítico (gráficos que tienen una propiedad que no está en manos de ninguna tarjeta) e hipográficos (gráficos que no tienen una propiedad que no está en manos de todas las tarjetas).
descomposición: Consulte descomposición de árboles, descomposición de caminos o descomposición de ramas.
degenerar
degeneración: Un gráfico $k$ -degenerado es un gráfico no dirigido en el que cada subgrafo inducido tiene un grado mínimo como máximo $k$ . La degeneración de un gráfico es la $k$ más pequeña para la cual es $k$ -degenerado. Un orden de degeneración es un ordenamiento de los vértices tal que cada vértice tiene un grado mínimo en el subgrafo inducido del mismo y en todos los vértices posteriores; en un orden de degeneración de un $k$ -gráfico degenerado, cada vértice tiene como máximo $k$ vecinos posteriores. La degeneración también se conoce como número $k$ -core, ancho y vinculación, y uno más la degeneración también se llama número de coloración o número de Szekeres-Wilf. $Los gráficos k$ -degenerados también se han llamado gráficos $k -inductivos.$
grado: 1. El grado de un vértice en un gráfico es su número de aristas incidentes. ^[2] El grado de un gráfico $G$ (o su grado máximo) es el máximo de los grados de sus vértices, a menudo denotado $Δ(G)$ ; el grado mínimo de $G$ es el mínimo de sus grados de vértice, a menudo denotado $δ (G)$ . El grado a veces se llama valencia ; el grado de $v$ en $G$ puede denotarse $como d G (v)$ , $d (G)$ o $deg(v)$ . El grado total es la suma de los grados de todos los vértices; Según el lema del apretón de manos , es un número par. La secuencia de grados es la colección de grados de todos los vértices, ordenados de mayor a menor. En un gráfico dirigido, se puede distinguir el grado de entrada (número de aristas entrantes) y el grado de salida (número de aristas salientes). ^[2]; 2. El grado de homomorfismo de un grafo es sinónimo de su número de Hadwiger , el orden de la camarilla menor más grande.
Δ, δ: $Δ(G)$ (usando la letra griega delta) es el grado máximo de un vértice en $G$ , y $δ (G)$ es el grado mínimo; ver grado.
densidad: En un gráfico de n nodos, la densidad es la relación entre el número de aristas del gráfico y el número de aristas en un gráfico completo en n nodos. Ver gráfico denso .
profundidad: La profundidad de un nodo en un árbol enraizado es el número de aristas en el camino desde la raíz hasta el nodo. Por ejemplo, la profundidad de la raíz es 0 y la profundidad de cualquiera de sus nodos adyacentes es 1. Es el nivel de un nodo menos uno. Sin embargo, tenga en cuenta que algunos autores utilizan profundidad como sinónimo del nivel de un nodo. ^[9]
diámetro: El diámetro de un gráfico conectado es la longitud máxima de un camino más corto . Es decir, es el máximo de las distancias entre pares de vértices del gráfico. Si el gráfico tiene pesos en sus bordes, entonces su diámetro ponderado mide la longitud del camino por la suma de los pesos de los bordes a lo largo de un camino, mientras que el diámetro no ponderado mide la longitud del camino por el número de bordes. Para gráficos desconectados, las definiciones varían: el diámetro puede definirse como infinito, o como el diámetro más grande de un componente conectado, o puede no estar definido.
diamante: El gráfico de diamante es un gráfico no dirigido con cuatro vértices y cinco aristas.
desconectado: Fuertemente conectado. (No confundir con desconectado)
excavar: Un digon es un ciclo simple de longitud dos en un gráfico dirigido o un multigrafo. Los digones no pueden aparecer en gráficos simples no dirigidos ya que requieren repetir el mismo borde dos veces, lo que viola la definición de simple .
dígrafo: Sinónimo de gráfico dirigido . ^[2]
dipata: Ver camino dirigido.
predecesor directo: La cola de una arista dirigida cuya cabeza es el vértice dado.
sucesor directo: La cabeza de una arista dirigida cuya cola es el vértice dado.
dirigido: Un grafo dirigido es aquel en el que las aristas tienen una dirección distinguida, de un vértice a otro. ^[2] En un gráfico mixto , una arista dirigida es nuevamente aquella que tiene una dirección distinguida; Los bordes dirigidos también pueden denominarse arcos o flechas.
arco dirigido: Ver flecha.
borde dirigido: Ver flecha.
línea dirigida: Ver flecha.
camino dirigido: Un camino en el que todas las aristas tienen la misma dirección. Si un camino dirigido va del vértice $x$ al vértice $y$ , $x$ es un predecesor de $y$ , $y$ es un sucesor de $x$ , y se dice que $y$ es alcanzable desde $x$ .
dirección: 1. La relación asimétrica entre dos vértices adyacentes en un gráfico, representada como una flecha.; 2. La relación asimétrica entre dos vértices en un camino dirigido.
desconectar: Causa de desconexión.
desconectado: No conectado.
desarticular: 1. Dos subgrafos son disjuntos de aristas si no comparten aristas, y disjuntos de vértice si no comparten vértices.; 2. La unión disjunta de dos o más grafos es un grafo cuyos conjuntos de vértices y aristas son las uniones disjuntas de los conjuntos correspondientes.
número de disociación: Un subconjunto de vértices en un gráfico G se llama disociación si induce un subgrafo con grado máximo 1.
distancia: La distancia entre dos vértices cualesquiera en un gráfico es la longitud del camino más corto que tiene los dos vértices como puntos finales.
domático: Una partición domática de un gráfico es una partición de los vértices en conjuntos dominantes. El número domático del gráfico es el número máximo de conjuntos dominantes en dicha partición.
dominante: Un conjunto dominante es un conjunto de vértices que incluye o es adyacente a cada vértice del gráfico; No debe confundirse con una cobertura de vértices, un conjunto de vértices que incide en todos los bordes del gráfico. Los tipos especiales importantes de conjuntos dominantes incluyen conjuntos dominantes independientes (conjuntos dominantes que también son conjuntos independientes) y conjuntos dominantes conectados (conjuntos dominantes que indujeron subgrafos conectados). Un conjunto dominante de un solo vértice también puede denominarse vértice universal. El número de dominación de un gráfico es el número de vértices en el conjunto dominante más pequeño.
doble: Una gráfica dual de una gráfica plana $G$ es una gráfica que tiene un vértice para cada cara de $G.$

mi

mi: $E (G)$ es el conjunto de aristas de $G$ ; ver conjunto de bordes.
oreja: Una oreja de un gráfico es un camino cuyos puntos finales pueden coincidir pero en el que por lo demás no hay repeticiones de vértices o aristas.
descomposición del oído: Una descomposición de oreja es una partición de los bordes de un gráfico en una secuencia de orejas, cada uno de cuyos puntos finales (después del primero) pertenece a una oreja anterior y cada uno de cuyos puntos interiores no pertenecen a ninguna oreja anterior. Una oreja abierta es un camino simple (una oreja sin vértices repetidos), y una descomposición de oreja abierta es una descomposición de oreja en la que cada oreja después de la primera está abierta; un grafo tiene descomposición en oído abierto si y sólo si es biconexo. Una oreja es impar si tiene un número impar de aristas, y una descomposición de oreja impar es una descomposición de oreja en la que cada oreja es impar; un gráfico tiene una descomposición de oído impar si y sólo si es factor crítico.
excentricidad: La excentricidad de un vértice es la mayor distancia entre él y cualquier otro vértice.
borde: Una arista es (junto con los vértices) una de las dos unidades básicas a partir de las cuales se construyen los gráficos. Cada arista tiene dos (o en hipergráficos, más) vértices a los que está unido, llamados puntos finales. Los bordes pueden ser dirigidos o no dirigidos; Los bordes no dirigidos también se llaman líneas y los bordes dirigidos también se llaman arcos o flechas. En un gráfico simple no dirigido , una arista puede representarse como el conjunto de sus vértices, y en un gráfico simple dirigido puede representarse como un par ordenado de sus vértices. Una arista que conecta los vértices xey $a$ $veces$ se escribe $xy$ .
corte de borde: Un conjunto de aristas cuya eliminación desconecta el gráfico. Un corte de un solo borde se llama puente, istmo o borde de corte.
conjunto de bordes: El conjunto de aristas de un gráfico dado $G$ , a veces denotado por $E (G)$ .
gráfico sin bordes: El gráfico sin aristas o el gráfico totalmente desconectado en un conjunto dado de vértices es el gráfico que no tiene aristas. A veces se le llama gráfico vacío, pero este término también puede referirse a un gráfico sin vértices.
incrustar: Una incrustación de gráfico es una representación topológica de un gráfico como un subconjunto de un espacio topológico con cada vértice representado como un punto, cada borde representado como una curva que tiene los puntos finales del borde como puntos finales de la curva y ninguna otra intersección entre vértices o bordes. Una gráfica plana es una gráfica que tiene tal incrustación en el plano euclidiano, y una gráfica toroidal es una gráfica que tiene tal incrustación en un toroide. El género de un gráfico es el género mínimo posible de una variedad bidimensional en la que se puede incrustar.
gráfico vacío: 1. Un gráfico sin aristas en un conjunto de vértices no vacíos.; 2. El gráfico de orden cero , un gráfico sin vértices ni aristas.
fin: Un final de un gráfico infinito es una clase de equivalencia de rayos, donde dos rayos son equivalentes si hay un tercer rayo que incluye infinitos vértices de ambos.
punto final: Uno de los dos vértices unidos por una determinada arista, o uno del primer o último vértice de un paseo, sendero o sendero. El primer punto final de una arista dirigida determinada se llama cola y el segundo punto final se llama cabeza .
enumeración: La enumeración de gráficos es el problema de contar los gráficos de una clase determinada de gráficos, en función de su orden. De manera más general, los problemas de enumeración pueden referirse a problemas de contar una determinada clase de objetos combinatorios (como camarillas, conjuntos independientes, coloraciones o árboles de expansión), o de enumerar algorítmicamente todos esos objetos.
Euleriano: Un camino euleriano es un recorrido que utiliza cada borde de un gráfico exactamente una vez. Un circuito euleriano (también llamado ciclo euleriano o recorrido de Euler) es un recorrido cerrado que utiliza cada borde exactamente una vez. Un gráfico euleriano es un gráfico que tiene un circuito euleriano. Para un gráfico no dirigido, esto significa que el gráfico es conexo y cada vértice tiene grado par. Para un gráfico dirigido, esto significa que el gráfico está fuertemente conectado y cada vértice tiene un grado de entrada igual al grado de salida. En algunos casos, el requisito de conectividad se flexibiliza y un gráfico que cumple sólo los requisitos de grado se denomina eulerian.
incluso: Divisible por dos; por ejemplo, un ciclo par es un ciclo cuya duración es par.
expansor: Un gráfico de expansión es un gráfico cuya expansión de bordes, expansión de vértices o expansión espectral está acotada desde cero.
expansión: 1. La expansión de aristas, número isoperimétrico o constante de Cheeger de un gráfico $G$ es la relación mínima, sobre subconjuntos $S$ de como máximo la mitad de los vértices de $G$ , entre el número de aristas que salen de $S$ y el número de vértices en $S.$; 2. La expansión de vértice, número isoperimétrico de vértice o ampliación de un gráfico $G$ es la relación mínima, sobre subconjuntos $S$ de como máximo la mitad de los vértices de $G$ , del número de vértices fuera pero adyacentes a $S$ y el número de vértices en $S$ .; 3. La expansión de vecino único de un gráfico $G$ es la relación mínima, sobre subconjuntos de como máximo la mitad de los vértices de $G$ , del número de vértices fuera de $S$ pero adyacentes a un vértice único en $S$ y el número de vértices en $S.$; 4. La expansión espectral de un gráfico $d -regular$ $G$ es la brecha espectral entre el valor propio más grande $d$ de su matriz de adyacencia y el segundo valor propio más grande.; 5. Una familia de gráficas tiene expansión acotada si todos sus $r$ -menores poco profundos tienen una proporción de aristas a vértices acotada por una función de $r$ , y expansión polinómica si la función de $r$ es un polinomio.

F

rostro: En un gráfico plano o incrustación de gráfico , un componente conectado del subconjunto del plano o superficie de la incrustación que está separado del gráfico. Para una incrustación en el plano, todas las caras menos una estarán delimitadas; la única cara excepcional que se extiende hasta el infinito se llama cara exterior.
factor: Un factor de un gráfico es un subgrafo abarcador: un subgrafo que incluye todos los vértices del gráfico. El término se utiliza principalmente en el contexto de subgrafos regulares: un $k$ -factor es un factor que es $k$ -regular. En particular, un factor $1$ es lo mismo que una coincidencia perfecta. Un gráfico de factores críticos es un gráfico en el que al eliminar cualquier vértice se produce un gráfico con un factor $1$ .
factorización: La factorización de un gráfico es una partición de los bordes del gráfico en factores; una $k$ -factorización es una partición en $k$ -factores. Por ejemplo, una factorización $1$ es una coloración de bordes con la propiedad adicional de que cada vértice incide en un borde de cada color.
familia: Un sinónimo de clase.
finito: Un grafo es finito si tiene un número finito de vértices y un número finito de aristas. Muchas fuentes suponen que todos los gráficos son finitos sin decirlo explícitamente. Un gráfico es localmente finito si cada vértice tiene un número finito de aristas incidentes. Un gráfico infinito es un gráfico que no es finito: tiene infinitos vértices, infinitas aristas o ambos.
primer orden: La lógica de primer orden de los gráficos es una forma de lógica en la que las variables representan los vértices de un gráfico y existe un predicado binario para probar si dos vértices son adyacentes. Debe distinguirse de la lógica de segundo orden, en la que las variables también pueden representar conjuntos de vértices o aristas.
-solapa: Para un conjunto de vértices $X$ , un $X$ -flap es un componente conectado del subgrafo inducido formado al eliminar $X$ . La terminología de solapa se usa comúnmente en el contexto de paraísos , funciones que asignan pequeños conjuntos de vértices a sus solapas. Véase también el puente de un ciclo, que es un aleteo de los vértices del ciclo o un acorde del ciclo.
prohibido: Una caracterización de grafo prohibido es una caracterización de una familia de grafos como los grafos que no tienen otros grafos determinados como subgrafos, subgrafos inducidos o menores. Si $H$ es uno de los grafos que no aparece como subgrafo, subgrafo inducido o menor, entonces se dice que $H$ está prohibido.
gráfico de forzamiento: Un gráfico forzado es un gráfico $H$ tal que evaluar la densidad de subgrafos de $H$ en los gráficos de una secuencia de gráficos $G (n)$ es suficiente para probar si esa secuencia es cuasi aleatoria.
bosque: Un bosque es un gráfico no dirigido sin ciclos (una unión disjunta de árboles sin raíces), o un gráfico dirigido formado como una unión disjunta de árboles con raíces.
Frucht: 1. Robert Frucht; 2. El gráfico de Frucht , uno de los dos gráficos cúbicos más pequeños sin simetrías no triviales.; 3. Teorema de Frucht de que todo grupo finito es el grupo de simetrías de un grafo finito.
lleno: Sinónimo de inducido.
grafico funcional: Un gráfico funcional es un gráfico dirigido donde cada vértice tiene grado uno. De manera equivalente, un gráfico funcional es un pseudobosque dirigido máximo.

GRAMO

GRAMO: Una variable que se utiliza a menudo para indicar un gráfico.
género: El género de un gráfico es el género mínimo de una superficie sobre la que se puede incrustar; ver incrustación.
geodésico: Como sustantivo, una geodésica es sinónimo de camino más corto . Cuando se usa como adjetivo, significa relacionado con los caminos más cortos o las distancias de camino más cortas.
gigante: En la teoría de grafos aleatorios , una componente gigante es una componente conexa que contiene una fracción constante de los vértices de la gráfica. En los modelos estándar de gráficos aleatorios, normalmente hay como máximo un componente gigante.
circunferencia: La circunferencia de un gráfico es la longitud de su ciclo más corto.
grafico: El objeto fundamental de estudio de la teoría de grafos, un sistema de vértices conectados de dos en dos por aristas. A menudo se subdivide en grafos dirigidos o grafos no dirigidos según si las aristas tienen una orientación o no. Los gráficos mixtos incluyen ambos tipos de aristas.
avaro: Producido por un algoritmo codicioso . Por ejemplo, una coloración voraz de un gráfico es una coloración producida al considerar los vértices en alguna secuencia y asignar a cada vértice el primer color disponible.
grötzsch: 1. Herbert Grötzsch; 2. El gráfico de Grötzsch , el gráfico sin triángulos más pequeño que requiere cuatro colores en cualquier coloración adecuada.; 3. El teorema de Grötzsch de que los gráficos planos sin triángulos siempre se pueden colorear con un máximo de tres colores.
número sucio: 1. El número de Grundy de un gráfico es el número máximo de colores producidos por una coloración codiciosa , con un orden de vértices mal elegido.

h

h: Una variable que se utiliza a menudo para denotar un gráfico, especialmente cuando ya se ha denotado otro gráfico con $G.$
H -coloración: Una coloración $H de un gráfico$ $G$ (donde $H$ también es un gráfico) es un homomorfismo de $H$ a $G.$
libre de H: Un gráfico está libre de $H$ si no tiene un subgrafo inducido isomorfo a $H$ , es decir, si $H$ es un subgrafo inducido prohibido. Los gráficos libres $de H$ son la familia de todos los gráficos (o, a menudo, todos los gráficos finitos) que son libres de $H.$ ^[10] Por ejemplo, las gráficas sin triángulos son las gráficas que no tienen una gráfica triangular como subgrafía. La propiedad de estar libre $de H$ es siempre hereditaria. Un gráfico es $H$ -libre de menores si no tiene un isomorfo menor a $H$ .
hadwiger: 1. Hugo Hadwiger; 2. El número de Hadwiger de una gráfica es el orden del mayor menor completo de la gráfica. También se le llama número de camarilla de contracción o grado de homomorfismo.; 3. La conjetura de Hadwiger es la conjetura de que el número de Hadwiger nunca es menor que el número cromático.
hamiltoniano: Una ruta hamiltoniana o un ciclo hamiltoniano es una ruta de expansión simple o un ciclo de expansión simple: cubre todos los vértices del gráfico exactamente una vez. Un gráfico es hamiltoniano si contiene un ciclo hamiltoniano y trazable si contiene una trayectoria hamiltoniana.
refugio: Un $k$ - refugio es una función que asigna cada conjunto $X$ de menos de $k$ vértices a una de sus solapas, a menudo satisfaciendo condiciones de consistencia adicionales. El orden de un refugio es el número $k$ . Havens se puede utilizar para caracterizar el ancho del árbol de gráficos finitos y los extremos y los números de Hadwiger de gráficos infinitos.
altura: 1. La altura de un nodo en un árbol enraizado es el número de aristas en un camino más largo, que se aleja de la raíz (es decir, sus nodos tienen una profundidad estrictamente creciente), que comienza en ese nodo y termina en una hoja.; 2. La altura de un árbol enraizado es la altura de su raíz. Es decir, la altura de un árbol es el número de aristas de un camino más largo posible, alejándose de la raíz, que comienza en la raíz y termina en una hoja.; 3. La altura de un gráfico acíclico dirigido es la longitud máxima de una ruta dirigida en este gráfico.
hereditario: Una propiedad hereditaria de los gráficos es una propiedad que está cerrada bajo subgrafos inducidos: si $G$ tiene una propiedad hereditaria, entonces también la debe tener cada subgrafo inducido de $G.$ Compare monótono (cerrado bajo todos los subgrafos) o cerrado menor (cerrado bajo menores).
hexágono: Un ciclo simple que consta exactamente de seis aristas y seis vértices.
agujero: Un agujero es un ciclo inducido de longitud cuatro o más. Un agujero impar es un agujero de longitud impar. Un anti-agujero es un subgrafo inducido de orden cuatro cuyo complemento es un ciclo; de manera equivalente, es un agujero en el gráfico del complemento. Esta terminología se utiliza principalmente en el contexto de gráficos perfectos, que se caracterizan por el fuerte teorema del grafo perfecto por ser gráficos sin agujeros impares ni antiagujeros impares. Las gráficas sin agujeros son las mismas que las gráficas cordales .
equivalencia homomórfica: Dos gráficos son homomórficamente equivalentes si existen dos homomorfismos, uno de cada gráfico al otro gráfico.
homomorfismo: 1. Un homomorfismo de gráfico es un mapeo del conjunto de vértices de un gráfico al conjunto de vértices de otro gráfico que asigna vértices adyacentes a vértices adyacentes. Este tipo de mapeo entre gráficos es el que se usa más comúnmente en los enfoques de teoría de categorías de la teoría de grafos. Una coloración adecuada de un gráfico puede describirse de manera equivalente como un homomorfismo de un gráfico completo.; 2. El grado de homomorfismo de un grafo es sinónimo de su número de Hadwiger , el orden de la camarilla menor más grande.
hiperarco: Un hiperborde dirigido que tiene un conjunto de origen y destino.
hiperborde: Un borde en un hipergráfico, que tiene cualquier número de puntos finales, en contraste con el requisito de que los bordes de los gráficos tengan exactamente dos puntos finales.
hipercubo: Un gráfico de hipercubo es un gráfico formado a partir de los vértices y aristas de un hipercubo geométrico .
hipergrafo: Un hipergráfico es una generalización de un gráfico en el que cada borde (llamado hiperborde en este contexto) puede tener más de dos puntos finales.
hipo-: Este prefijo, en combinación con una propiedad de gráfico, indica un gráfico que no tiene la propiedad pero que cada subgrafo formado al eliminar un solo vértice sí tiene la propiedad. Por ejemplo, un gráfico hipohamiltoniano es aquel que no tiene un ciclo hamiltoniano, pero para el cual cada eliminación de un vértice produce un subgrafo hamiltoniano. Comparar crítico, usado para gráficos que tienen una propiedad pero para los cuales cada eliminación de un vértice no la tiene. ^[11]

I

en grado: El número de aristas entrantes en un gráfico dirigido; ver grado.
incidencia: Una incidencia en un gráfico es un par vértice-arista tal que el vértice es un punto final de la arista.
matriz de incidencia: La matriz de incidencia de un gráfico es una matriz cuyas filas están indexadas por los vértices del gráfico y cuyas columnas están indexadas por las aristas, con un uno en la celda para la fila $i$ y la columna $j$ cuando el vértice $i$ y la arista $j$ son incidentes, y una cero en caso contrario.
incidente: La relación entre una arista y uno de sus puntos finales. ^[2]
incomparabilidad: Un gráfico de incomparabilidad es el complemento de un gráfico de comparabilidad ; ver comparabilidad.
independiente: 1. Un conjunto independiente es un conjunto de vértices que induce un subgrafo sin aristas. También se le puede llamar conjunto estable o coclique. El número de independencia $α (G)$ es el tamaño del conjunto independiente máximo .; 2. En la matroide gráfica de un gráfico, un subconjunto de aristas es independiente si el subgrafo correspondiente es un árbol o un bosque. En la matroide bicircular , un subconjunto de aristas es independiente si el subgrafo correspondiente es un pseudobosque .
indiferencia: Un gráfico de indiferencia es otro nombre para un gráfico de intervalo adecuado o un gráfico de intervalo unitario; ver apropiado.
inducido: Un subgrafo inducido o subgrafo completo de un gráfico es un subgrafo formado a partir de un subconjunto de vértices y de todas las aristas que tienen ambos puntos finales en el subconjunto. Los casos especiales incluyen caminos inducidos y ciclos inducidos , subgrafos inducidos que son caminos o ciclos.
inductivo: Sinónimo de degenerar.
infinito: Un gráfico infinito es aquel que no es finito; ver finito.
interno: Un vértice de un camino o de un árbol es interno si no es una hoja; es decir, si su grado es mayor que uno. Dos caminos son internamente disjuntos (algunos lo llaman independientes ) si no tienen ningún vértice en común, excepto el primero y el último.
intersección: 1. La intersección de dos grafos es su mayor subgrafo común, el grafo formado por los vértices y aristas que pertenecen a ambos grafos.; 2. Un gráfico de intersección es un gráfico cuyos vértices corresponden a conjuntos u objetos geométricos, con un borde entre dos vértices exactamente cuando los dos conjuntos u objetos correspondientes tienen una intersección no vacía. Se pueden definir varias clases de gráficos como gráficos de intersección de ciertos tipos de objetos, por ejemplo, gráficos cordales (gráficos de intersección de subárboles de un árbol), gráficos circulares (gráficos de intersección de cuerdas de un círculo), gráficos de intervalo (gráficos de intersección de intervalos). de una línea), gráficos de líneas (gráficos de intersección de los bordes de un gráfico) y gráficos de camarillas (gráficos de intersección de los camarillas máximas de un gráfico). Cada gráfico es un gráfico de intersección para alguna familia de conjuntos, y esta familia se llama representación de intersección del gráfico. El número de intersección de un gráfico $G$ es el número total mínimo de elementos en cualquier representación de intersección de $G.$
intervalo: 1. Una gráfica de intervalos es una gráfica de intersección de intervalos de una recta .; 2. El intervalo $[u, v]$ en un gráfico es la unión de todos los caminos más cortos de $u$ a $v$ .; 3. El espesor del intervalo es sinónimo de ancho de ruta.
invariante: Sinónimo de propiedad.
flecha invertida: Una flecha con dirección opuesta a otra flecha. La flecha $(y, x)$ es la flecha invertida de la flecha $(x, y)$ .
aislado: Un vértice aislado de un gráfico es un vértice cuyo grado es cero, es decir, un vértice sin aristas incidentes. ^[2]
isomórfico: Dos grafos son isomorfos si existe un isomorfismo entre ellos; ver isomorfismo.
isomorfismo: Un isomorfismo de gráfico es una incidencia uno a uno que preserva la correspondencia de los vértices y aristas de un gráfico con los vértices y aristas de otro gráfico. Se dice que dos grafos relacionados de esta manera son isomórficos.
isoperimétrico: Ver expansión.
istmo: Sinónimo de puente, en el sentido de arista cuya eliminación desconecta el grafo.

k

k: Para conocer la notación de gráficos completos, gráficos bipartitos completos y gráficos multipartitos completos, consulte completo.
k: $κ (G)$ (usando la letra griega kappa) es el orden de la camarilla máxima en $G$ ; ver camarilla.
núcleo: El núcleo de un gráfico dirigido es un conjunto de vértices que es a la vez estable y absorbente.
nudo: Una sección ineludible de un gráfico dirigido. Véase nudo (matemáticas) y teoría de nudos .

l

l: $L (G)$ es la gráfica lineal de $G$ ; ver línea.
etiqueta: 1. Información asociada a un vértice o arista de un gráfico. Un gráfico etiquetado es un gráfico cuyos vértices o aristas tienen etiquetas. Los términos etiquetados con vértices o etiquetados con bordes se pueden utilizar para especificar qué objetos de un gráfico tienen etiquetas. El etiquetado de gráficos se refiere a varios problemas diferentes de asignación de etiquetas a gráficos sujetos a ciertas restricciones. Véase también coloración de gráficos , en el que las etiquetas se interpretan como colores.; 2. En el contexto de la enumeración de gráficos , se dice que los vértices de un gráfico están etiquetados si todos se distinguen entre sí. Por ejemplo, esto se puede hacer realidad fijando una correspondencia uno a uno entre los vértices y los números enteros desde 1 hasta el orden del gráfico. Cuando se etiquetan los vértices, los gráficos que son isomórficos entre sí (pero con diferentes ordenamientos de los vértices) se cuentan como objetos separados. Por el contrario, cuando los vértices no están etiquetados, los gráficos que son isomorfos entre sí no se cuentan por separado.
hoja: 1. Un vértice de hoja o vértice colgante (especialmente en un árbol) es un vértice cuyo grado es $1$ . Un borde de hoja o un borde colgante es el borde que conecta el vértice de una hoja con su único vecino.; 2. Una potencia de hoja de un árbol es un gráfico cuyos vértices son las hojas del árbol y cuyas aristas conectan hojas cuya distancia en el árbol es como máximo un umbral dado.
longitud: En un gráfico no ponderado, la longitud de un ciclo, camino o caminata es el número de aristas que utiliza. En un gráfico ponderado, puede ser la suma de los pesos de los bordes que utiliza. La longitud se utiliza para definir la ruta más corta , la circunferencia (longitud del ciclo más corta) y la ruta más larga entre dos vértices en un gráfico.
nivel: 1. Esta es la profundidad de un nodo más 1, aunque algunos ^[12] la definen como sinónimo de profundidad . El nivel de un nodo en un árbol raíz es el número de nodos en la ruta desde la raíz hasta el nodo. Por ejemplo, la raíz tiene el nivel 1 y cualquiera de sus nodos adyacentes tiene el nivel 2.; 2. Un conjunto de todos los nodos que tienen el mismo nivel o profundidad. ^[12]
línea: Sinónimo de ventaja no dirigida. La gráfica lineal $L (G)$ de una gráfica $G$ es una gráfica con un vértice para cada arista de $G$ y una arista para cada par de aristas que comparten un punto final en $G$ .
enlace: Sinónimo de degeneración.
lista: 1. Una lista de adyacencia es una representación informática de gráficos para su uso en algoritmos de gráficos.; 2. La coloración de listas es una variación de la coloración de gráficos en la que cada vértice tiene una lista de colores disponibles.
local: Una propiedad local de un gráfico es una propiedad que está determinada únicamente por las vecindades de los vértices del gráfico. Por ejemplo, un gráfico es localmente finito si todas sus vecindades son finitas.
bucle: Un bucle o autobucle es una arista cuyos puntos finales son el mismo vértice. Forma un ciclo de longitud $1$ . Estos no están permitidos en gráficos simples.

METRO

aumento: Sinónimo de expansión de vértices.
pareo: Una coincidencia es un conjunto de aristas en las que no hay dos que compartan ningún vértice. Un vértice coincide o está saturado si es uno de los puntos finales de una arista en la coincidencia. Una coincidencia perfecta o una coincidencia completa es una coincidencia que coincide con cada vértice; también se le puede llamar factor 1 y solo puede existir cuando el orden es par. Una coincidencia casi perfecta, en un gráfico con orden impar, es aquella que satura todos los vértices menos uno. Una coincidencia máxima es una coincidencia que utiliza tantas aristas como sea posible; el número coincidente $α'(G)$ de un gráfico $G$ es el número de aristas en una coincidencia máxima. Una coincidencia máxima es una coincidencia a la que no se pueden agregar aristas adicionales.
máximo: 1. Un subgrafo del gráfico $G$ dado es máximo para una propiedad particular si tiene esa propiedad pero ningún otro supergrafo del mismo que también sea un subgrafo de $G$ también tiene la misma propiedad. Es decir, es un elemento maximal de los subgrafos con la propiedad. Por ejemplo, una camarilla máxima es un subgrafo completo que no se puede expandir a un subgrafo completo más grande. La palabra "máximo" debe distinguirse de "máximo": un subgrafo máximo siempre es máximo, pero no necesariamente al revés.; 2. Un gráfico simple con una propiedad dada es máximo para esa propiedad si no es posible agregarle más aristas (manteniendo el vértice establecido sin cambios) preservando al mismo tiempo la simplicidad del gráfico y la propiedad. Así, por ejemplo, un gráfico plano máximo es un gráfico plano tal que agregarle más aristas crearía un gráfico no plano.
máximo: Un subgrafo de un gráfico dado $G$ es máximo para una propiedad particular si es el subgrafo más grande (por orden o tamaño) entre todos los subgrafos con esa propiedad. Por ejemplo, una camarilla máxima es cualquiera de las camarillas más grandes en un gráfico determinado.
mediana: 1. Una mediana de un triple de vértices, un vértice que pertenece a los caminos más cortos entre todos los pares de vértices, especialmente en gráficos de mediana y gráficos modulares .; 2. Una gráfica de mediana es una gráfica en la que cada tres vértices tiene una mediana única.
meyniel: 1. Henri Meyniel, teórico de grafos francés.; 2. Un gráfico de Meyniel es un gráfico en el que cada ciclo impar de longitud cinco o más tiene al menos dos cuerdas.
mínimo: Un subgrafo de un gráfico dado es mínimo para una propiedad particular si tiene esa propiedad pero ningún subgrafo adecuado también tiene la misma propiedad. Es decir, es un elemento mínimo de los subgrafos con la propiedad.
corte mínimo: Un corte cuyo conjunto de cortes tiene un peso total mínimo, posiblemente restringido a cortes que separan un par de vértices designados; se caracterizan por el teorema de corte mínimo de flujo máximo .
menor: Un gráfico $H$ es menor de otro gráfico $G$ si $H$ se puede obtener eliminando aristas o vértices de $G$ y contrayendo aristas en $G.$ Es un menor poco profundo si se puede formar como menor de tal manera que todos los subgrafos de $G$ que se contrajeron para formar los vértices de $H$ tengan un diámetro pequeño. $H$ es un menor topológico de $G$ si $G$ tiene un subgrafo que es una subdivisión de $H.$ Una gráfica está libre de $H$ -menor si no tiene $H$ como menor. Una familia de gráficos está cerrada por menores si está cerrada por menores; El teorema de Robertson-Seymour caracteriza a las familias cerradas por menores como si tuvieran un conjunto finito de menores prohibidos.
mezclado: Un gráfico mixto es un gráfico que puede incluir aristas tanto dirigidas como no dirigidas.
modular: 1. Gráfico modular , un gráfico en el que cada triplete de vértices tiene al menos un vértice mediano que pertenece a los caminos más cortos entre todos los pares del triplete.; 2. Descomposición modular , una descomposición de un gráfico en subgrafos dentro de los cuales todos los vértices se conectan con el resto del gráfico de la misma manera.; 3. Modularidad de un agrupamiento de gráficos, la diferencia entre el número de aristas entre grupos y su valor esperado.
monótono: Una propiedad monótona de los gráficos es una propiedad que está cerrada bajo los subgrafos: si $G$ tiene una propiedad hereditaria, entonces también la debe tener cada subgrafo de $G.$ Compare hereditario (cerrado bajo subgrafos inducidos) o menor-cerrado (cerrado bajo menores).
gráfico de moore: Un gráfico de Moore es un gráfico regular en el que el límite de Moore se cumple exactamente. El límite de Moore es una desigualdad que relaciona el grado, el diámetro y el orden de una gráfica, demostrada por Edward F. Moore . Cada gráfico de Moore es una jaula.
multigrafo: Un multigrafo es un gráfico que permite múltiples adyacencias (y, a menudo, bucles automáticos); un gráfico que no tiene por qué ser simple.
adyacencia múltiple: Una adyacencia múltiple o arista múltiple es un conjunto de más de una arista que tiene todos los mismos puntos finales (en la misma dirección, en el caso de gráficos dirigidos). Un gráfico con múltiples aristas a menudo se denomina multigrafo.
multiplicidad: La multiplicidad de una arista es el número de aristas en una adyacencia múltiple. La multiplicidad de un gráfico es la multiplicidad máxima de cualquiera de sus aristas.

norte

norte: 1. Para conocer la notación de barrios abiertos y cerrados, consulte barrio.; $2. A menudo se utiliza una n$ minúscula (especialmente en informática) para indicar el número de vértices en un gráfico determinado.
vecino
vecino: Un vértice que es adyacente a un vértice dado.
vecindario
vecindario: La vecindad abierta (o vecindad) de un vértice $v$ es el subgrafo inducido por todos los vértices que son adyacentes a $v$ . La vecindad cerrada se define de la misma manera pero también incluye al propio $v$ . La vecindad abierta de $v$ en $G$ se puede denotar $NG (v)$ o $N (v) , y la vecindad$ $cerrada$ se puede denotar $NG [v]$ o $N [v$ $]$ $.$ Cuando no se especifica el carácter abierto o cerrado de un barrio, se supone que está abierto.
red: Un gráfico en el que los atributos (por ejemplo, nombres) están asociados con los nodos y/o bordes.
nodo: Un sinónimo de vértice.
sin borde: Una no arista o una antiarista es un par de vértices que no son adyacentes; los bordes del gráfico de complemento.
gráfico nulo: Ver gráfico vacío.

oh

extraño: 1. Un ciclo impar es un ciclo cuya duración es impar. La circunferencia impar de un gráfico no bipartito es la longitud de su ciclo impar más corto. Un agujero impar es un caso especial de ciclo impar: uno que es inducido y tiene cuatro o más vértices.; 2. Un vértice impar es un vértice cuyo grado es impar. Según el lema del apretón de manos, todo gráfico finito no dirigido tiene un número par de vértices impares.; 3. Un oído impar es una ruta simple o un ciclo simple con un número impar de aristas, que se utiliza en descomposiciones de oído impar de gráficos de factores críticos; ver oreja.; 4. Una cuerda impar es una arista que conecta dos vértices que están separados por una distancia impar en un ciclo par. Los acordes impares se utilizan para definir grafos fuertemente cordales .; 5. Un gráfico impar es un caso especial de un gráfico de Kneser , que tiene un vértice para cada $(n - 1)$ subconjunto de elementos de un conjunto de $(2 n - 1)$ elementos, y una arista que conecta dos subconjuntos cuando sus conjuntos correspondientes son desarticular.
abierto: 1. Ver barrio.; 2. Ver caminar.
orden: 1. El orden de un gráfico $G$ es el número de sus vértices, $| V (G)|$ . La variable $n$ se utiliza a menudo para esta cantidad. Véase también tamaño, el número de aristas.; 2. Un tipo de lógica de gráficos ; ver primer orden y segundo orden.; 3. Un orden u ordenamiento de un gráfico es una disposición de sus vértices en una secuencia, especialmente en el contexto del ordenamiento topológico (un orden de un gráfico acíclico dirigido en el que cada arista va desde un vértice anterior a un vértice posterior en el orden ) y orden de degeneración (un orden en el que cada vértice tiene un grado mínimo en el subgrafo inducido del mismo y en todos los vértices posteriores).; 4. Para conocer el orden de un refugio o una zarza, consulte refugio y zarza.
orientación
orientado: 1. La orientación de un gráfico no dirigido es una asignación de direcciones a sus bordes, convirtiéndolo en un gráfico dirigido. Un gráfico orientado es aquel al que se le ha asignado una orientación. Así, por ejemplo, un poliárbol es un árbol orientado; se diferencia de un árbol dirigido (una arborescencia) en que no existe ningún requisito de coherencia en las direcciones de sus bordes. Otros tipos especiales de orientación incluyen torneos , orientaciones de gráficas completas; orientaciones fuertes , orientaciones que están fuertemente conectadas; orientaciones acíclicas , orientaciones que son acíclicas; Orientaciones eulerianas , orientaciones que son eulerianas; y orientaciones transitivas , orientaciones que son transitivamente cerradas.; 2. Grafo orientado, utilizado por algunos autores como sinónimo de grafo dirigido .
fuera de grado: Ver grado.
exterior: Ver cara.
plano exterior: Un gráfico plano exterior es un gráfico que se puede incrustar en el plano (sin cruces) de modo que todos los vértices estén en la cara exterior del gráfico.

PAG

padre: En un árbol enraizado, un padre de un vértice $v$ es vecino de $v$ a lo largo del borde entrante, el que se dirige hacia la raíz.
camino: Un camino puede ser un paseo o un paseo sin vértices repetidos y, en consecuencia, aristas (también llamado camino simple), dependiendo de la fuente. Casos especiales importantes incluyen caminos inducidos y caminos más cortos .
descomposición del camino: Una descomposición de ruta de un gráfico $G$ es una descomposición de árbol cuyo árbol subyacente es una ruta. Su ancho se define de la misma manera que para las descomposiciones de árboles, como uno menos que el tamaño de la bolsa más grande. El ancho mínimo de cualquier descomposición de camino de $G$ es el ancho de camino de $G$ .
ancho de ruta: El ancho de ruta de un gráfico $G$ es el ancho mínimo de una descomposición de ruta de $G$ . También se puede definir en términos del número de camarilla de la finalización de un intervalo de $G.$ Siempre está entre el ancho de banda y el ancho del árbol de $G.$ También se conoce como espesor de intervalo, número de separación de vértices o número de búsqueda de nodos.
colgante: Ver hoja.
perfecto: 1. Un gráfico perfecto es un gráfico en el que, en cada subgrafo inducido, el número cromático es igual al número de camarilla. El teorema de la gráfica perfecta y el teorema de la gráfica perfecta fuerte son dos teoremas sobre gráficas perfectas, el primero demuestra que sus complementos también son perfectos y el segundo demuestra que son exactamente las gráficas sin agujeros impares ni antiagujeros.; 2. Un gráfico perfectamente ordenable es un gráfico cuyos vértices se pueden ordenar de tal manera que un algoritmo de coloración codicioso con este orden coloree de manera óptima cada subgrafo inducido. Las gráficas perfectamente ordenables son una subclase de las gráficas perfectas.; 3. Una coincidencia perfecta es una coincidencia que satura cada vértice; ver coincidencia.; 4. Una factorización 1 perfecta es una partición de los bordes de un gráfico en coincidencias perfectas de modo que cada dos coincidencias formen un ciclo hamiltoniano.
periférico: 1. Un ciclo periférico o ciclo sin separación es un ciclo con como máximo un puente.; 2. Un vértice periférico es un vértice cuya excentricidad es máxima. En un árbol, ésta debe ser una hoja.
Petersen: 1. Julius Petersen (1839-1910), teórico de grafos danés.; 2. El gráfico de Petersen , un gráfico de 10 vértices y 15 aristas que se utiliza frecuentemente como contraejemplo.; 3. Teorema de Petersen de que todo grafo cúbico sin puente tiene una correspondencia perfecta.
plano: Un gráfico plano es un gráfico que está incrustado en el plano euclidiano. Un gráfico plano es un gráfico plano para el cual ya se ha arreglado una incrustación particular. Un gráfico $k$ -planar es aquel que se puede dibujar en el plano con como máximo $k$ cruces por arista.
poliárbol: Un poliárbol es un árbol orientado; de manera equivalente, un gráfico acíclico dirigido cuyo gráfico no dirigido subyacente es un árbol.
fuerza: 1. Una potencia gráfica $G k$ de un gráfico $G$ es otra gráfica en el mismo conjunto de vértices; dos vértices son adyacentes en $G k$ cuando están a una distancia máxima $k$ en $G$ . El poder de una hoja es un concepto estrechamente relacionado, derivado del poder de un árbol tomando el subgrafo inducido por las hojas del árbol.; 2. El análisis de gráficos de potencia es un método para analizar redes complejas mediante la identificación de camarillas, bicliques y estrellas dentro de la red.; 3. Las leyes de potencia en las distribuciones de grados de redes libres de escala son un fenómeno en el que el número de vértices de un grado dado es proporcional a una potencia del grado.
predecesor: Un vértice que precede a un vértice dado en un camino dirigido.
adecuado: 1. Un subgrafo adecuado es un subgrafo que elimina al menos un vértice o arista en relación con todo el gráfico; para gráficos finitos, los subgrafos propios nunca son isomorfos al gráfico completo, pero para gráficos infinitos pueden serlo.; 2. Una coloración adecuada es una asignación de colores a los vértices de un gráfico (una coloración) que asigna diferentes colores a los puntos finales de cada arista; ver color.; 3. Un gráfico de intervalo adecuado o un gráfico de arco circular adecuado es un gráfico de intersección de una colección de intervalos o arcos circulares (respectivamente) de modo que ningún intervalo o arco contenga otro intervalo o arco. Los gráficos de intervalos propios también se denominan gráficos de intervalos unitarios (porque siempre se pueden representar mediante intervalos unitarios) o gráficos de indiferencia.
propiedad: Una propiedad de un gráfico es algo que puede ser verdadero para algunos gráficos y falso para otros, y que depende sólo de la estructura del gráfico y no de información incidental como las etiquetas. Las propiedades de los gráficos pueden describirse de manera equivalente en términos de clases de gráficos (los gráficos que tienen una propiedad determinada). De manera más general, una propiedad de gráfico también puede ser una función de gráficos que nuevamente es independiente de información incidental, como el tamaño, el orden o la secuencia de grados de un gráfico; Esta definición más general de una propiedad también se llama invariante del gráfico.
pseudobosque: Un pseudobosque es un gráfico no dirigido en el que cada componente conectado tiene como máximo un ciclo, o un gráfico dirigido en el que cada vértice tiene como máximo un borde saliente.
pseudografo: Un pseudografo es un gráfico o multigrafo que permite bucles automáticos.

q

gráfico cuasilineal: Un gráfico cuasi lineal o un gráfico cobipartito local es un gráfico en el que la vecindad abierta de cada vértice se puede dividir en dos camarillas. Estos gráficos son siempre libres de garras e incluyen como caso especial los gráficos de líneas . Se utilizan en la teoría de la estructura de gráficos sin garras.
secuencia gráfica cuasi aleatoria: Una secuencia de gráficos cuasi aleatorios es una secuencia de gráficos que comparte varias propiedades con una secuencia de gráficos aleatorios generada según el modelo de gráficos aleatorios de Erdős-Rényi .
carcaj: Un carcaj es un multigrafo dirigido, como se utiliza en la teoría de categorías . Los bordes de un carcaj se llaman flechas.

R

radio: El radio de una gráfica es la excentricidad mínima de cualquier vértice.
Ramanujan: Un gráfico de Ramanujan es un gráfico cuya expansión espectral es lo más grande posible. Es decir, es un gráfico $d$ -regular, tal que el segundo valor propio más grande de su matriz de adyacencia es como máximo . $2{\sqrt {d-1}}$
rayo: Un rayo, en un gráfico infinito, es una trayectoria simple infinita con exactamente un punto final. Los extremos de un gráfico son clases de equivalencia de rayos.
accesibilidad: La capacidad de pasar de un vértice a otro dentro de un gráfico.
accesible: Tiene una accesibilidad afirmativa. Se dice que un vértice $y$ es accesible desde un vértice $x$ si existe un camino de $x$ a $y$ .
reconocible: En el contexto de la conjetura de la reconstrucción , una propiedad gráfica es reconocible si su verdad puede determinarse a partir del conjunto del gráfico. Se sabe que muchas propiedades de los gráficos son reconocibles. Si la conjetura de la reconstrucción es cierta, todas las propiedades del gráfico son reconocibles.
reconstrucción: La conjetura de la reconstrucción establece que cada gráfico no dirigido $G$ está determinado únicamente por su plataforma , un conjunto múltiple de gráficos formado eliminando un vértice de $G$ de todas las formas posibles. En este contexto, la reconstrucción es la formación de un gráfico a partir de su plataforma.
rectángulo: Un ciclo simple que consta exactamente de cuatro aristas y cuatro vértices.
regular: Una gráfica es $d$ -regular cuando todos sus vértices tienen grado $d$ . Una gráfica regular es una gráfica que es $d$ -regular para algún $d$ .
torneo regular: Un torneo normal es un torneo en el que el grado de entrada es igual al grado de salida para todos los vértices.
contrarrestar: Ver transponer.
raíz: 1. Un vértice designado en un gráfico, particularmente en árboles dirigidos y gráficos con raíces .; 2. La operación inversa a una potencia de gráfico : una $k$ -ésima raíz de un gráfico $G$ es otro gráfico en el mismo conjunto de vértices tal que dos vértices son adyacentes en $G$ si y solo si tienen una distancia como máximo $k$ en la raíz.

S

saturado: Ver coincidencia.
número de búsqueda: El número de búsqueda de nodo es sinónimo de ancho de ruta.
segundo orden: La lógica de segundo orden de los gráficos es una forma de lógica en la que las variables pueden representar vértices, aristas, conjuntos de vértices y (a veces) conjuntos de aristas. Esta lógica incluye predicados para probar si un vértice y una arista son incidentes, así como si un vértice o una arista pertenecen a un conjunto. Debe distinguirse de la lógica de primer orden, en la que las variables sólo pueden representar vértices.
auto-bucle: Sinónimo de bucle.
vértice separador: Ver punto de articulación.
numero de separacion: El número de separación de vértices es sinónimo de ancho de ruta.
hermano: En un árbol enraizado, un hermano de un vértice $v$ es un vértice que tiene el mismo vértice padre que $v$ .
simple: 1. Un gráfico simple es un gráfico sin bucles y sin múltiples adyacencias. Es decir, cada arista conecta dos puntos finales distintos y no hay dos aristas que tengan los mismos puntos finales. Una arista simple es una arista que no forma parte de una adyacencia múltiple. En muchos casos, se supone que los gráficos son simples a menos que se especifique lo contrario.; 2. Un camino simple o un ciclo simple es un camino o ciclo que no tiene vértices repetidos y, en consecuencia, no tiene aristas repetidas.
hundir: Un sumidero, en un gráfico dirigido, es un vértice sin aristas de salida (el grado de salida es igual a 0).
tamaño: El tamaño de un gráfico $G$ es el número de sus aristas, $| mi (sol)|$ . ^[13] La variable $m$ se utiliza a menudo para esta cantidad. Véase también orden , el número de vértices.
red del mundo pequeño: Una red de mundo pequeño es un gráfico en el que la mayoría de los nodos no son vecinos entre sí, pero se puede llegar a la mayoría de los nodos desde todos los demás mediante una pequeña cantidad de saltos o pasos. Específicamente, una red de mundo pequeño se define como un gráfico donde la distancia típica L entre dos nodos elegidos al azar (el número de pasos requeridos) crece proporcionalmente al logaritmo del número de nodos N en la red ^[14].
sarcasmo: Un snark es un gráfico cúbico simple, conectado, sin puentes y con un índice cromático igual a 4.
fuente: Una fuente, en un gráfico dirigido, es un vértice sin aristas entrantes (el grado de entrada es igual a 0).
espacio: En teoría de grafos algebraicos , varios espacios vectoriales sobre el campo binario pueden estar asociados con un gráfico. Cada uno tiene conjuntos de aristas o vértices para sus vectores, y una diferencia simétrica de conjuntos como operación de suma de vectores. El espacio de aristas es el espacio de todos los conjuntos de aristas y el espacio de vértices es el espacio de todos los conjuntos de vértices. El espacio de corte es un subespacio del espacio de borde que tiene los conjuntos de corte del gráfico como elementos. El espacio cíclico tiene como elementos los subgrafos que abarcan Euler.
llave: Una llave inglesa es un gráfico (generalmente escaso) cuyas distancias de ruta más cortas se aproximan a las de un gráfico denso u otro espacio métrico. Las variaciones incluyen llaves geométricas , gráficos cuyos vértices son puntos en un espacio geométrico; llaves de árbol , árboles que abarcan de un gráfico cuyas distancias se aproximan a las distancias del gráfico, y llaves de gráfico, subgrafos dispersos de un gráfico denso cuyas distancias se aproximan a las distancias del gráfico original. Una llave codiciosa es una llave gráfica construida mediante un algoritmo codicioso, generalmente uno que considera todos los bordes desde el más corto al más largo y mantiene los que son necesarios para preservar la aproximación de la distancia.
abarcando: Un subgrafo se extiende cuando incluye todos los vértices del gráfico dado. Los casos importantes incluyen árboles de expansión , subgrafos de expansión que son árboles y coincidencias perfectas , subgrafos de expansión que son coincidencias. Un subgrafo de expansión también puede denominarse factor , especialmente (pero no solo) cuando es regular.
escaso: Un gráfico disperso es aquel que tiene pocas aristas en relación con su número de vértices. En algunas definiciones, la misma propiedad también debería ser cierta para todos los subgrafos del gráfico dado.
espectral
espectro: El espectro de un gráfico es el conjunto de valores propios de su matriz de adyacencia. La teoría de grafos espectrales es la rama de la teoría de grafos que utiliza espectros para analizar gráficos. Véase también expansión espectral.
dividir: 1. Un gráfico dividido es un gráfico cuyos vértices se pueden dividir en una camarilla y un conjunto independiente. Una clase relacionada de gráficas, las gráficas de doble división, se utilizan en la prueba del teorema del grafo perfecto fuerte.; 2. Una división de un gráfico arbitrario es una partición de sus vértices en dos subconjuntos no vacíos, de modo que los bordes que abarcan este corte forman un subgrafo bipartito completo. Las divisiones de un gráfico se pueden representar mediante una estructura de árbol llamada descomposición dividida . Una división se denomina división fuerte cuando no está atravesada por ninguna otra división. Una división se llama no trivial cuando ambos lados tienen más de un vértice. Un gráfico se llama primo cuando no tiene divisiones no triviales.
cuadrado: 1. El cuadrado de un gráfico $G$ es la potencia del gráfico $G 2$ ; en la otra dirección, $G$ es la raíz cuadrada de $G 2$ . El semicuadrado de un gráfico bipartito es el subgrafo de su cuadrado inducido por un lado de la bipartición.; 2. Un gráfico cuadrado es un gráfico plano que se puede dibujar de modo que todas las caras acotadas tengan 4 ciclos y todos los vértices de grado ≤ 3 pertenezcan a la cara exterior.; 3. Un gráfico de cuadrícula cuadrada es un gráfico de celosía definido a partir de puntos en el plano con coordenadas enteras conectadas por aristas de longitud unitaria.
estable: Un conjunto estable es sinónimo de conjunto independiente.
estrella: Una estrella es un árbol con un vértice interno; de manera equivalente, es un gráfico bipartito completo $K 1, n$ para algunos $n \geq 2$ . El caso especial de una estrella de tres hojas se llama garra.
fortaleza: La fuerza de un gráfico es la relación mínima entre el número de aristas eliminadas del gráfico y los componentes creados, sobre todas las eliminaciones posibles; es análogo a la tenacidad, basada en la eliminación de vértices.
fuerte: 1. Para conocer una conectividad sólida y componentes fuertemente conectados de gráficos dirigidos, consulte conectado y componente. Una orientación fuerte es una orientación que está fuertemente conectada; ver orientación.; 2. Para conocer el teorema del gráfico perfecto fuerte , consulte perfecto.; 3. Un gráfico fuertemente regular es un gráfico regular en el que cada dos vértices adyacentes tiene el mismo número de vecinos compartidos y cada dos vértices no adyacentes tienen el mismo número de vecinos compartidos.; 4. Un gráfico fuertemente cordal es un gráfico cordal en el que cada ciclo par de longitud seis o más tiene una cuerda impar.; 5. Un gráfico fuertemente perfecto es un gráfico en el que cada subgrafo inducido tiene un conjunto independiente que cumple con todas las camarillas máximas. Los gráficos de Meyniel también se denominan "gráficos muy fuertemente perfectos" porque en ellos cada vértice pertenece a un conjunto independiente.
subbosque: Un subgrafo de un bosque.
subgrafo: Un subgrafo de un grafo $G$ es otro grafo formado a partir de un subconjunto de los vértices y aristas de $G.$ El subconjunto de vértices debe incluir todos los puntos finales del subconjunto de aristas, pero también puede incluir vértices adicionales. Un subgrafo abarcador es aquel que incluye todos los vértices del gráfico; un subgrafo inducido es aquel que incluye todas las aristas cuyos puntos finales pertenecen al subconjunto de vértices.
subárbol: Un subárbol es un subgrafo conectado de un árbol. A veces, para árboles enraizados, los subárboles se definen como un tipo especial de subgrafo conectado, formado por todos los vértices y aristas accesibles desde un vértice elegido.
sucesor: Un vértice que viene después de un vértice dado en un camino dirigido.
superconcentrador: Un superconcentrador es un gráfico con dos subconjuntos de vértices $I$ y $O$ designados y de igual tamaño , de modo que por cada dos subconjuntos $S$ de igual tamaño de $I$ y $T$ $O$ existe una familia de caminos disjuntos que conectan cada vértice en $S$ con un vértice en $T.$ _ Algunas fuentes requieren además que un superconcentrador sea un grafo acíclico dirigido, con $I$ como fuente y $O$ como sumidero.
supergrafo: Un gráfico formado agregando vértices, aristas o ambos a un gráfico determinado. Si $H$ es un subgrafo de $G$ , entonces $G$ es un supergrafo de $H.$

t

theta: 1. Un gráfico theta es la unión de tres caminos internamente separados (simples) que tienen los mismos dos vértices finales distintos. ^[15]; 2. El gráfico theta de una colección de puntos en el plano euclidiano se construye construyendo un sistema de conos que rodean cada punto y agregando un borde por cono, hasta el punto cuya proyección sobre un rayo central del cono es más pequeña.; 3. El número de Lovász o función theta de Lovász de un gráfico es una invariante del gráfico relacionada con el número de camarilla y el número cromático que se puede calcular en tiempo polinómico mediante programación semidefinida.
gráfico de Thomsen: El gráfico de Thomsen es un nombre para el gráfico bipartito completo . $K_{3,3}$
topológico: 1. Un gráfico topológico es una representación de los vértices y aristas de un gráfico mediante puntos y curvas en el plano (no necesariamente evitando los cruces).; 2. La teoría de grafos topológicos es el estudio de las incrustaciones de grafos.; 3. La clasificación topológica es el problema algorítmico de organizar un gráfico acíclico dirigido en un orden topológico, una secuencia de vértices tal que cada arista va desde un vértice anterior a un vértice posterior en la secuencia.
totalmente desconectado: Sinónimo de sin bordes.
recorrido: Un sendero cerrado, un paseo que comienza y termina en un mismo vértice y no tiene aristas repetidas. Los recorridos de Euler son recorridos que utilizan todos los bordes del gráfico; ver Euleriano.
torneo: Un torneo es una orientación de un gráfico completo; es decir, es un gráfico dirigido tal que cada dos vértices están conectados exactamente por un borde dirigido (que va sólo en una de las dos direcciones entre los dos vértices).
rastreable: Un gráfico trazable es un gráfico que contiene una trayectoria hamiltoniana.
camino: Un paseo sin aristas repetidas.
transitivo: Relativo a la propiedad transitiva . El cierre transitivo de un gráfico dirigido dado es un gráfico en el mismo conjunto de vértices que tiene un borde de un vértice a otro siempre que el gráfico original tenga un camino que conecte los mismos dos vértices. Una reducción transitiva de un gráfico es un gráfico mínimo que tiene el mismo cierre transitivo; Los gráficos acíclicos dirigidos tienen una reducción transitiva única. Una orientación transitiva es una orientación de un gráfico que es su propio cierre transitivo; existe sólo para gráficos de comparabilidad .
transponer: La gráfica transpuesta de una gráfica dirigida dada es una gráfica en los mismos vértices, con cada arista en dirección invertida. También se le puede llamar lo contrario o lo contrario de la gráfica.
árbol: 1. Un árbol es un gráfico no dirigido que es a la vez conexo y acíclico, o un gráfico dirigido en el que existe un recorrido único desde un vértice (la raíz del árbol) hasta todos los vértices restantes.; 2. Un $k$ -árbol es un gráfico formado pegando $(k + 1)$ -camarillas en $k$ -camarillas compartidas. Un árbol en el sentido ordinario es un árbol $1$ según esta definición.
descomposición del árbol: Una descomposición en árbol de un gráfico $G$ es un árbol cuyos nodos están etiquetados con conjuntos de vértices de $G$ ; estos conjuntos se llaman bolsas. Para cada vértice $v$ , las bolsas que contienen $v$ deben inducir un subárbol del árbol, y para cada arista $uv$ debe existir una bolsa que contenga tanto $u$ como $v$ . El ancho de la descomposición de un árbol es uno menos que el número máximo de vértices en cualquiera de sus bolsas; el ancho del árbol de $G$ es el ancho mínimo de cualquier descomposición de árbol de $G$ .
ancho del árbol: El ancho de árbol de un gráfico $G$ es el ancho mínimo de una descomposición de árbol de $G$ . También se puede definir en términos del número de camarilla de una terminación cordal de $G$ , el orden de un refugio de $G$ o el orden de una zarza de $G.$
triángulo: Un ciclo de longitud tres en un gráfico. Un gráfico sin triángulos es un gráfico no dirigido que no tiene subgráficos triangulares.
trivial: Un gráfico trivial es un gráfico con 0 o 1 vértices. ^[16] Un gráfico con 0 vértices también se llama gráfico nulo .
Turan: 1. Pál Turán; 2. Un grafo de Turán es un grafo multipartito completo equilibrado.; 3. El teorema de Turán establece que los gráficos de Turán tienen el número máximo de aristas entre todos los gráficos libres de camarillas de un orden determinado.; 4. El problema de la fábrica de ladrillos de Turán pide el número mínimo de cruces en un dibujo de un grafo bipartito completo.
mellizo: Dos vértices $u,v$ son verdaderos gemelos si tienen la misma vecindad cerrada: $N G [u] = N G [v]$ (esto implica que $u$ y $v$ son vecinos), y son falsos gemelos si tienen la misma vecindad abierta: $N G (u) = N G (v))$ (esto implica $que u$ y $v$ no son vecinos).

Ud.

vértice unario: En un árbol enraizado, un vértice unario es un vértice que tiene exactamente un vértice hijo.
no dirigido: Un gráfico no dirigido es un gráfico en el que los dos puntos finales de cada arista no se distinguen entre sí. Véase también dirigida y mixta . En un gráfico mixto , una arista no dirigida es nuevamente aquella en la que los puntos finales no se distinguen entre sí.
uniforme: Un hipergrafo es $k$ -uniforme cuando todas sus aristas tienen $k$ puntos finales, y uniforme cuando es $k$ -uniforme para algunos $k$ . Por ejemplo, los gráficos ordinarios son lo mismo que los hipergráficos $biformes$ .
universal: 1. Un gráfico universal es un gráfico que contiene como subgrafos todos los gráficos de una familia de gráficos determinada, o todos los gráficos de un tamaño u orden determinado dentro de una familia de gráficos determinada.; 2. Un vértice universal (también llamado vértice o vértice dominante) es un vértice adyacente a todos los demás vértices del gráfico. Por ejemplo, los gráficos de rueda y los gráficos de umbral conectados siempre tienen un vértice universal.; 3. En la lógica de las gráficas , un vértice que está universalmente cuantificado en una fórmula puede denominarse vértice universal para esa fórmula.
gráfico no ponderado: Un gráfico a cuyos vértices y aristas no se les han asignado pesos; lo opuesto a un gráfico ponderado.
gráfico de utilidad: El gráfico de utilidad es un nombre para el gráfico bipartito completo . $K_{3,3}$

V

V: Ver conjunto de vértices .
valencia: Sinónimo de grado .
vértice: Un vértice (vértices en plural) es (junto con las aristas) una de las dos unidades básicas a partir de las cuales se construyen los gráficos. Los vértices de los gráficos a menudo se consideran objetos atómicos, sin estructura interna.
corte de vértice
conjunto separador: Un conjunto de vértices cuya eliminación desconecta el gráfico. Un corte de un vértice se denomina punto de articulación o vértice de corte.
conjunto de vértices: El conjunto de vértices de un gráfico dado $G$ , a veces denotado por $V (G)$ .
vértices: Ver vértice .
vising: 1. Vadim G. Vizing; 2. Teorema de Vizing según el cual el índice cromático es como máximo un grado más que el máximo.; 3. Conjetura de Vizing sobre el número de dominación de los productos cartesianos de grafos.
volumen: La suma de los grados de un conjunto de vértices.

W.

$W.$: La letra $W$ se utiliza en notación para gráficos de ruedas y gráficos de molino de viento . La notación no está estandarizada.
wagner: 1. Klaus Wagner; 2. El gráfico de Wagner , una escalera de Möbius de ocho vértices.; 3. Teorema de Wagner que caracteriza los grafos planos por sus menores prohibidos.; 4. Teorema de Wagner que caracteriza las gráficas libres menores $K 5 .$
caminar: Un paseo es una secuencia finita o infinita de aristas que une una secuencia de vértices . Los paseos a veces también se llaman cadenas . ^[17] Un camino es abierto si su primer y último vértice son distintos, y cerrado si se repiten.
débilmente conectado: Un gráfico dirigido se llama débilmente conexo si al reemplazar todas sus aristas dirigidas con aristas no dirigidas se produce un gráfico conexo (no dirigido).
peso: Un valor numérico, asignado como etiqueta a un vértice o borde de un gráfico. El peso de un subgrafo es la suma de los pesos de los vértices o aristas dentro de ese subgrafo.
gráfico ponderado: Un gráfico a cuyos vértices o aristas se les han asignado pesos. Un gráfico ponderado por vértices tiene pesos en sus vértices y un gráfico ponderado por bordes tiene pesos en sus bordes.
bien coloreado: Un gráfico bien coloreado es un gráfico cuyos colores codiciosos utilizan el mismo número de colores.
bien cubierto: Un gráfico bien cubierto es un gráfico cuyos conjuntos independientes máximos son del mismo tamaño.
rueda: Un gráfico de rueda es un gráfico formado agregando un vértice universal a un ciclo simple.
ancho: 1. Sinónimo de degeneración.; 2. Para conocer otras invariantes de gráficos conocidas como ancho, consulte ancho de banda, ancho de rama, ancho de camarilla, ancho de ruta y ancho de árbol.; 3. El ancho de una descomposición de árbol o descomposición de camino es uno menos que el tamaño máximo de una de sus bolsas, y puede usarse para definir el ancho de árbol y el ancho de camino.; 4. El ancho de un gráfico acíclico dirigido es la cardinalidad máxima de una anticadena.
molino: Un gráfico de molino de viento es la unión de una colección de camarillas, todas del mismo orden entre sí, con un vértice compartido que pertenece a todas las camarillas y todos los demás vértices y aristas distintos.

Ver también

Referencias

^ Farber, M.; Hahn, G.; Demonios, P .; Miller, DJ (1986), "Sobre el número acromático de gráficos", Journal of Combinatorial Theory, Serie B , 40 (1): 21–39, doi : 10.1016/0095-8956(86)90062-6.
^ abcdefgh Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), "B.4 Graphs", Introducción a los algoritmos (2 ed.), MIT Press y McGraw-Hill, págs. 1080-1084.
^ Grünbaum, B. (1973), "Coloraciones acíclicas de gráficos planos", Israel Journal of Mathematics , 14 (4): 390–408, doi : 10.1007/BF02764716.
^ Cormen et al. (2001), pág. 529.
^ Diestel, Reinhard (2017), "1.1 Gráficos", Teoría de grafos , Textos de Posgrado en Matemáticas, vol. 173 (5ª ed.), Berlín, Nueva York: Springer-Verlag, pág. 3, doi :10.1007/978-3-662-53622-3, ISBN 978-3-662-53621-6.
^ Woodall, DR (1973), "El número vinculante de un gráfico y su número de Anderson", J. Combin. Teoría Ser. B , 15 (3): 225–255, doi : 10.1016/0095-8956(73)90038-5
^ van der Holst, Hein (marzo de 2009), "Un algoritmo de tiempo polinomial para encontrar una incrustación sin enlaces de un gráfico", Journal of Combinatorial Theory, Serie B , Elsevier BV, 99 (2): 512–530, doi :10.1016 /j.jctb.2008.10.002
^ Sudakov, Benny; Volec, Jan (2017), "Copias de gráficos con pocas cerezas correctamente coloreadas y en forma de arcoíris", Journal of Combinatorial Theory, Serie B , 122 (1): 391–416, arXiv : 1504.06176 , doi : 10.1016/j.jctb.2016.07 .001.
^ profundidad, NIST
^ Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), "Capítulo 7: Subgrafo prohibido", Clases de gráficos: una encuesta, Monografías de SIAM sobre aplicaciones y matemáticas discretas, págs. 105-121, ISBN 978-0-89871-432-6
^ Mitchem, John (1969), "Hipopropiedades en gráficos", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Michigan, 1968) , Lecture Notes in Mathematics, vol. 110, Springer, págs. 223–230, doi :10.1007/BFb0060121, ISBN 978-3-540-04629-5, señor 0253932.
^ nivel abdominal, NIST
^ Harris, John M. (2000), Combinatoria y teoría de grafos, Nueva York: Springer-Verlag, p. 5, ISBN 978-0-387-98736-1
^ Watts, Duncan J.; Strogatz, Steven H. (junio de 1998), "Dinámica colectiva de redes de 'mundos pequeños'", Nature , 393 (6684): 440–442, Bibcode :1998Natur.393..440W, doi :10.1038/30918, PMID 9623998 , S2CID 4429113
^ Bondy, JA (1972), "La" teoría de grafos "del alfabeto griego", Teoría de grafos y aplicaciones (Proc. Conf., Western Michigan Univ., Kalamazoo, Michigan, 1972; dedicado a la memoria de JWT Youngs) , Apuntes de conferencias sobre matemáticas, vol. 303, Springer, págs. 43–54, doi :10.1007/BFb0067356, ISBN 978-3-540-06096-3, SEÑOR 0335362
^ Diestel, Reinhard (2017), Teoría de grafos, Textos de posgrado en matemáticas, vol. 173, Berlín, Heidelberg: Springer Berlin Heidelberg, pág. 2, doi :10.1007/978-3-662-53622-3, ISBN 978-3-662-53621-6
^ "Teoría de grafos de cadenas", britannica.com , consultado el 25 de marzo de 2018

Busque el Apéndice: Glosario de teoría de grafos en Wikcionario, el diccionario gratuito.