Glosario de teoría de grafos

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

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

Símbolos

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

A

absorbente: Un conjunto absorbente de un grafo dirigido es un conjunto de vértices tales que para cualquier vértice de , existe una arista desde hacia un vértice de . ${\estilo de visualización A}$ ${\estilo de visualización G}$ $v\en G\setmenos A$ ${\estilo de visualización v}$ ${\estilo de visualización A}$
acromático: El número acromático de un grafo es el número máximo de colores en una coloración completa. ^[1]
acíclico: 1. Un grafo es acíclico si no tiene ciclos. Un grafo acíclico no dirigido es lo mismo que un bosque . Un grafo dirigido acíclico, que es un dígrafo sin ciclos dirigidos, a menudo se denomina grafo 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. 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]
alfa: Para un grafo $G$ , $α (G)$ (usando la letra griega alpha) es su número de independencia (ver independiente), y $α'(G)$ es su número correspondiente (ver correspondencia).
alterno: En un grafo con una coincidencia, una ruta alterna es una ruta cuyos bordes se alternan entre bordes coincidentes y no coincidentes. Un ciclo alternante es, de manera similar, un ciclo cuyos bordes se alternan entre bordes coincidentes y no coincidentes. Una ruta de aumento es una ruta alterna que comienza y termina en vértices no saturados. Una coincidencia mayor se puede encontrar como la diferencia simétrica de la ruta coincidente y la ruta de aumento; una coincidencia es máxima si y solo si no tiene una ruta de aumento.
anticadena: En un grafo acíclico dirigido , un subconjunto $S$ de vértices que no son comparables entre sí, es decir, para ninguno de ellos en $S$ , existe 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 no arista , un par de vértices no adyacentes.
anti-triángulo: Un conjunto independiente de tres vértices, el complemento de un triángulo.
ápex: 1. Un grafo de vértice es un grafo en el que se puede eliminar un vértice, dejando un subgrafo plano. El vértice eliminado se llama vértice. Un grafo de $k$ -vértices es un grafo que se puede convertir en plano eliminando $k$ vértices.; 2. Sinónimo de vértice universal , un 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 grafo dirigido. Una flecha $(x, y)$ tiene una cola $x$ , una punta $y$ y una dirección $de x a 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 conexo cuya eliminación desconectaría el gráfico.
-ario: Un árbol k -ario es un árbol con raíz en el que cada vértice interno no tiene más de $k$ hijos. Un árbol 1-ario es simplemente un camino. Un árbol 2-ario también se denomina árbol binario , aunque ese término se refiere más apropiadamente a árboles 2-arios 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 trayectoria alterna; ver alternancia.
automorfismo: Un automorfismo de gráfico es una simetría de un gráfico, un isomorfismo del gráfico hacia sí mismo.

B

bolsa: Uno de los conjuntos de vértices en una descomposición de á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 de uno del otro.
ancho de banda: El ancho de banda de un grafo $G$ es el mínimo, sobre todos los ordenamientos de vértices de $G$ , de la longitud de la arista más larga (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 una completitud de intervalo adecuada de $G$ , elegida para minimizar el tamaño de la camarilla.
biclicúlo: Sinónimo de gráfico bipartito completo o subgráfico bipartito completo; ver completo.
biconectado: Generalmente es sinónimo de $2$ -conexo por vértice , pero a veces incluye K ₂ aunque no esté 2-conexo. Véase conexo; para componentes biconexos , véase componente.
número de enlace: La relación más pequeña posible entre el número de vecinos de un subconjunto propio de vértices y el tamaño del subconjunto. ^[6]
bipartito: Un grafo bipartito es un grafo 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 pueden estar conectados a vértices del otro conjunto. Dicho de otra manera, un grafo bipartito es un grafo sin ciclos impares; equivalentemente, es un grafo que se puede colorear adecuadamente con dos colores. Los grafos 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 grafo sea conexo, puede que no tenga una coloración única de 2 colores.
birregular: Un gráfico birregular es un gráfico bipartito en el que solo hay dos grados de vértice diferentes, uno para cada conjunto de la bipartición de vértices.
bloquear: 1. Un bloque de un grafo $G$ es un subgrafo maximalista que puede ser un vértice aislado, una arista de puente o un subgrafo biconexo. Si un bloque es biconexo, cada par de vértices que lo componen pertenece a un ciclo común. Cada arista de un grafo pertenece exactamente a un bloque.; 2. El grafo de bloques de un grafo $G$ es otro grafo cuyos vértices son los bloques de $G$ , con una arista que une dos vértices cuando los bloques correspondientes comparten un punto de articulación; es decir, es el grafo de intersección de los bloques de $G$ . El grafo de bloques de cualquier grafo es un bosque.; 3. El grafo de corte por bloques (o de punto de corte por bloques) de un grafo $G$ es un grafo bipartito en el que un conjunto de partes 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 grafo de punto de corte por bloques es un árbol. $Estilo de visualización b_{i}$ $B_{i}$; 4. Un grafo de bloques (también llamado árbol de clique si está conectado, y a veces erróneamente llamado árbol de Husimi) es un grafo cuyos bloques son todos grafos completos. Un bosque es un grafo de bloques; por lo tanto, en particular, el grafo de bloques de cualquier grafo es un grafo de bloques, y cada grafo de bloques puede construirse como el grafo de bloques de un grafo.
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 propio tiene la misma propiedad.
libro: 1. Un libro , gráfico de libro o libro triangular es un gráfico tripartito completo $K 1,1, n$ ; una colección de $n$ triángulos unidos en 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 por un borde compartido; el producto cartesiano de una estrella con un borde.; 3. Una incrustación de libro es una incrustación de un gráfico en un libro topológico, un espacio formado mediante la unión de 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 denomina el lomo de la incrustación, y que los bordes de la incrustación se encuentren dentro de un solo semiplano, una de las páginas del libro.
límite: 1. En una incrustación de gráficos , un recorrido de límites es el subgráfico que contiene todos los bordes y vértices incidentes de una cara.
zarza: Una zarza es una colección de subgrafos conectados que se tocan entre sí, donde dos subgrafos se tocan si comparten un vértice o cada uno incluye un extremo de una arista. 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 grafo 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 no es igual a dos. ^[7]
descomposición de ramas: Una descomposición en rama 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 en 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 en rama de $G$ .
Ancho de rama: Véase descomposición de ramas.
puente: 1. Un puente , istmo o arista cortada es una arista cuya eliminación desconectaría el grafo. Un grafo sin puentes es aquel que no tiene puentes; equivalentemente, un grafo con dos aristas conexas.; 2. Un puente de un subgrafo H es un subgrafo maximal conexo separado del resto del grafo por H . Es decir, es un subgrafo maximal que es disjunto con H en sus aristas y en el que cada dos vértices y aristas pertenecen a un camino que es internamente disjunto con H . H puede ser un conjunto de vértices. Una cuerda es un puente de una arista. En la prueba de planaridad , H es un ciclo y un ciclo periférico es un ciclo con como máximo un puente; debe ser un límite de cara en cualquier incrustación plana de su grafo.; 3. Un puente de un ciclo también puede significar un camino que conecta dos vértices de un ciclo pero que es más corto que cualquiera de los caminos del ciclo que conectan los mismos dos vértices. Un grafo con puente es un grafo en el que cada ciclo de cuatro o más vértices tiene un puente.
Sin puente: Un gráfico sin puentes o sin istmos es un gráfico que no tiene aristas de puente (es decir, istmos); es decir, cada componente conectado es un gráfico con 2 aristas conectadas .
mariposa: 1. El gráfico de la 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 grafo utilizado como arquitectura de red en computación distribuida, estrechamente relacionado con los ciclos cubo-conexos .

do

do: $C n$ es un gráfico de ciclo $de n$ vértices; véase ciclo.
cactus: Un grafo de cactus , árbol de cactus, cactus o árbol de Husimi es un grafo conexo en el que cada arista pertenece a un máximo de un ciclo. Sus bloques son ciclos o aristas simples. Si, además, cada vértice pertenece a dos bloques como máximo, entonces se denomina cactus de Navidad.
jaula: Una jaula es un grafo regular con el menor orden posible para su circunferencia.
canónico
canonización: Una forma canónica de un grafo es un invariante tal que dos grafos tienen invariantes iguales si y solo si son isomorfos. Las formas canónicas también pueden denominarse invariantes canónicos o invariantes completos, y a veces se definen solo para los grafos dentro de una familia particular de grafos. 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 baraja, el conjunto múltiple de todas las cartas de un gráfico.
Ancho de tallado: 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 aristas.
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.
centroide: Un centroide de un árbol es un vértice $v$ tal que si tiene su raíz en $v$ , ningún otro vértice tiene un tamaño de subárbol mayor que la mitad del tamaño del árbol.
cadena: 1. Sinónimo de caminar.; 2. Al aplicar métodos de topología algebraica a grafos, un elemento de un complejo de cadenas , es decir, un conjunto de vértices o un conjunto de aristas.
Cheeger constante: Ver expansión.
cereza: Una cereza es un camino de 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 con raíz, un hijo de un vértice $v$ es un vecino de $v$ a lo largo de un borde saliente, que se dirige lejos de la raíz.
acorde
acorde: 1. Una cuerda de un ciclo es una arista que no pertenece al ciclo, para la cual ambos puntos finales 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 triángulos.; 3. Un grafo fuertemente cordal es un grafo cordal en el que cada ciclo de longitud seis o más tiene un acorde impar.; 4. Un grafo bipartito cordal no es cordal (a menos que sea un bosque); es un grafo bipartito en el que cada ciclo de seis o más vértices tiene una cuerda, por lo que los únicos ciclos inducidos son 4-ciclos.; 5. Una cuerda de un círculo es un segmento de línea que conecta dos puntos en el círculo; el gráfico de intersección de una colección de cuerdas se llama gráfico circular .
cromático: Que tiene que ver con la coloración; véase 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 adecuada de los bordes de $G$ .
Elegible
Capacidad de elección: Un grafo es $k$ -elegible si tiene una lista de colores siempre que cada vértice tenga una lista de $k$ colores disponibles. La capacidad de elección del grafo es el $k$ más pequeño para el cual es $k$ -elegible.
círculo: Un gráfico circular es el gráfico de intersección de las cuerdas de un círculo.
circuito: Un circuito puede hacer referencia a un camino cerrado o a un elemento del espacio de ciclos (un subgrafo de expansión euleriano). El rango de circuito de un grafo es la dimensión de su espacio de ciclos.
circunferencia: La circunferencia de un grafo es la longitud de su ciclo simple más largo. El grafo es hamiltoniano si y solo si su circunferencia es igual a su orden.
clase: 1. Una clase de grafos o familia de grafos es una colección (normalmente infinita) de grafos, que a menudo se define como los grafos que tienen 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 deben extraer de un conjunto particular y definir que las aristas sean conjuntos de dos vértices), las clases de grafos normalmente no son conjuntos cuando se formalizan 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 , sobre la coloración de aristas de grafos simples, se dice que un grafo 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, todos los grafos simples son de clase uno o de clase dos.
garra: Una garra es un árbol con un vértice interno y tres hojas, o equivalentemente el grafo bipartito completo $K 1,3$ . Un grafo sin garra es un grafo 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 es parte de ningún conjunto (o subgrafo) más grande. Una $k$ -camarilla es una camarilla de orden $k$ . El número de camarilla $ω (G)$ de un grafo $G$ es el orden de su camarilla más grande. El grafo de camarilla de un grafo G es el grafo de intersección de las camarillas máximas en G . Véase también biclique, un subgrafo bipartito completo.
árbol de camarilla: Un sinónimo de gráfico de bloques.
ancho de camarilla: El ancho de camarilla de un grafo $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 grafos etiquetados, agregan una arista que conecta todos los pares de vértices con etiquetas dadas o reetiquetan todos los vértices con una etiqueta dada. Los grafos con un ancho de camarilla de como máximo $2$ son exactamente los cografos .
cerrado: 1. Un vecindario cerrado es aquel que incluye su vértice central; ver vecindario.; 2. Un paseo cerrado es aquel que empieza y termina en el mismo vértice; ver paseo.; 3. Un gráfico es transitivamente cerrado si es igual a su propio cierre transitivo; ver transitivo.; 4. Una propiedad de grafo está cerrada bajo alguna operación sobre grafos si, siempre que el argumento o los argumentos de la operación tienen la propiedad, entonces 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 menores cerradas están cerradas bajo menores.
cierre: 1. Para el cierre transitivo de un gráfico dirigido, véase transitivo.; 2. Un cierre de un grafo dirigido es un conjunto de vértices que no tienen aristas salientes hacia vértices fuera del cierre. Por ejemplo, un sumidero es un cierre de un solo 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 grafos complementarios . Por ejemplo, un cografo es un grafo 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 propia) o una camarilla (como en una 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 dado de colores o, equivalentemente, una partición de los vértices en subconjuntos, llamados "clases de color", cada uno de los cuales está asociado con uno de los colores.; 2. Algunos autores utilizan el término "coloración", sin ninguna calificación, para referirse a una coloración adecuada, que asigna colores diferentes a los puntos finales de cada arista. En la coloración de grafos, el objetivo es encontrar una coloración adecuada que utilice la menor cantidad posible de colores; por ejemplo, los grafos bipartitos son los grafos que tienen coloraciones con solo dos colores, y el teorema de los cuatro colores establece que todo grafo plano puede colorearse con un máximo de cuatro colores. Se dice que un grafo tiene $k$ colores si ha sido coloreado (adecuadamente) con $k$ colores, y que es $k$ -coloreable o $k$ -cromático si esto es posible.; 3. Se han estudiado muchas variaciones de coloración, incluyendo la coloración de aristas (colorear aristas de modo que no haya dos aristas con el mismo punto final que compartan un color), la coloración de lista (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), la co-coloración (cada clase de color induce un conjunto independiente o una camarilla), la coloración completa (cada dos clases de color comparten una arista) y la coloración total (tanto las aristas como los vértices están coloreados).; 4. El número de coloración de un gráfico es uno más la degeneración . Se llama así porque al aplicar un algoritmo de coloración voraz a un ordenamiento de degeneración del gráfico se utilizan como máximo esta cantidad de colores.
comparabilidad: Un grafo no dirigido es un grafo de comparabilidad si sus vértices son elementos de un conjunto parcialmente ordenado y dos vértices son adyacentes cuando son comparables en el orden parcial. De manera equivalente, un grafo de comparabilidad es un grafo que tiene una orientación transitiva. Muchas otras clases de grafos pueden definirse como grafos de comparabilidad de tipos especiales de orden parcial.
complementar: El grafo complementario de un grafo simple $G$ es otro grafo en el mismo conjunto de vértices que $G$ , con una arista por cada dos vértices que no sean 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 grafo completo con $n$ vértices se denota a menudo $K n$ . Un grafo bipartito completo es aquel en el que cada dos vértices en lados opuestos de la partición de vértices son adyacentes. Un grafo bipartito completo con $a$ vértices en un lado de la partición y $b$ vértices en el otro lado se denota a menudo $K a, b$ . La misma terminología y notación también se ha extendido a grafos multipartitos completos , grafos 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 este grafo se denota $K a, b, c, ...$ .; 2. Una compleción de un grafo dado es un supergrafo que tiene alguna propiedad deseada. Por ejemplo, una compleción cordal es un supergrafo que es un grafo cordal.; 3. Una coincidencia completa es sinónimo de una coincidencia perfecta ; ver coincidencia.; 4. Una coloración completa es una coloración propia en la que cada par de colores se utiliza para los puntos finales de al menos una arista. 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 grafo 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 una forma canónica, un invariante que tiene valores diferentes para gráficos no isomorfos.
componente: Un componente conexo de un grafo es un subgrafo conexo maximalista. El término también se utiliza para subgrafos maximalistas o subconjuntos de los vértices de un grafo que tienen un orden superior de conectividad, incluidos los componentes biconexos , los componentes triconexos y los componentes fuertemente conexos .
condensación: La condensación de un grafo dirigido $G$ es un grafo acíclico dirigido con un vértice para cada componente fuertemente conectado de $G$ y una arista que conecta pares de componentes que contienen los dos puntos finales de al menos una arista en $G.$
cono: Un gráfico que contiene un vértice universal .
conectar: Causa estar conectado.
conectado: Un grafo conexo es aquel en el que cada par de vértices forma los puntos finales de un camino. Las formas superiores de conectividad incluyen la conectividad fuerte en grafos dirigidos (para cada dos vértices hay caminos de uno al otro en ambas direcciones), grafos conexos por k vértices (eliminar menos de $k$ vértices no puede desconectar el grafo) y grafos conexos por k aristas (eliminar menos de $k$ aristas no puede desconectar el grafo).
componente conectado: Sinónimo de componente.
contracción: La contracción de aristas es una operación elemental que elimina una arista de un grafo mientras fusiona los dos vértices que unía previamente. La contracción de vértices (a veces llamada identificación de vértices) es similar, pero los dos vértices no están necesariamente conectados por una arista. La contracción de trayectoria ocurre en el conjunto de aristas de una trayectoria que se contraen para formar una única arista entre los puntos finales de la trayectoria. La operación inversa de la contracción de aristas es la división de vértices.
conversar: El gráfico inverso es un sinónimo del gráfico transpuesto; ver transposición.
centro: 1. Un $k$ -núcleo es el subgrafo inducido que se forma 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. Véase degeneración.; 2. Un núcleo es un grafo $G$ tal que todo homomorfismo de grafo de $G$ a sí mismo es un isomorfismo.; 3. El núcleo de un grafo $G$ es un grafo minimal $H$ tal que existen homomorfismos de $G$ a $H$ y viceversa. $H$ es único salvo 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 emparejamientos de grafos, el núcleo de un grafo es un aspecto de su descomposición de Dulmage-Mendelsohn , formado como la unión de todos los emparejamientos máximos.
co-árbol: 1. El complemento de un árbol de expansión .; 2. Una estructura de árbol con raíz 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 ancestro común más bajo 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 grafo. Una cobertura de aristas es un conjunto de aristas que inciden en cada vértice de un grafo. Un conjunto de subgrafos de un grafo cubre ese grafo si su unión (tomada por vértices y por aristas) es igual al grafo.
crítico: Un grafo crítico para una propiedad dada es un grafo que tiene la propiedad pero de modo que cada subgrafo formado al eliminar un único vértice no tiene la propiedad. Por ejemplo, un grafo crítico en cuanto a factores es uno que tiene una correspondencia 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 correspondencia perfecta en sí mismo. Compárese con hipo- , utilizado para grafos 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 cúbico , el gráfico de ocho vértices que consta de los vértices y las aristas de un cubo.; 2. Gráfico de hipercubo , una generalización de mayor dimensión del gráfico cúbico.; 3. Gráfico cúbico plegado , formado a partir de un hipercubo añadiendo vértices opuestos conectados.; 4. Gráfico cúbico reducido a la mitad , el medio cuadrado de un gráfico hipercubo.; 5. Cubo parcial , un subgrafo que preserva la distancia de un hipercubo.; 6. El cubo de un grafo $G$ es la potencia del grafo $G 3$ .; 7. Grafo cúbico , otro nombre para un gráfico $3$ -regular, uno en el que cada vértice tiene tres aristas incidentes.; 8. Ciclos conexos con cubos , un gráfico cúbico formado al reemplazar 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 grafo en dos subconjuntos, o el conjunto (también conocido como conjunto de corte) 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 lo tanto, la eliminación de un conjunto de corte de un grafo conexo lo desconecta.
punto de corte: Ver punto de articulación.
espacio de corte: El espacio de corte de un gráfico es un espacio vectorial GF (2) que tiene los conjuntos de corte del gráfico como sus elementos y la diferencia simétrica de conjuntos como su operación de adición vectorial.
ciclo: 1. Un ciclo puede ser un tipo de grafo o un tipo de paseo. Como paseo puede ser un paseo cerrado (también llamado tour) o más usualmente un paseo cerrado sin vértices repetidos y en consecuencia aristas (también llamado ciclo simple). En el último caso usualmente se lo considera como un grafo, es decir, las elecciones del primer vértice y dirección usualmente se consideran poco importantes; es decir, las permutaciones cíclicas y las inversiones del paseo producen el mismo ciclo. Los tipos especiales importantes de ciclo incluyen ciclos hamiltonianos , ciclos inducidos , ciclos periféricos y el ciclo más corto, que define la circunferencia de un grafo. Un $k$ -ciclo es un ciclo de longitud $k$ ; por ejemplo, un $2-$ ciclo es un dígono y un $3$ -ciclo es un triángulo. Un grafo de ciclo es un grafo que es en sí mismo un ciclo simple; un grafo de ciclo con $n$ vértices es comúnmente denotado $C n$ .; 2. El espacio de ciclos es un espacio vectorial generado por los 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 ningún ciclo dirigido.
cubierta: El multiconjunto de grafos formado a partir de un único grafo $G$ eliminando un único vértice de todas las formas posibles, especialmente en el contexto de la conjetura de reconstrucción . Una baraja de aristas se forma de la misma manera eliminando una única arista de todas las formas posibles. Los grafos de una baraja también se denominan cartas . Véase también crítico (grafos que tienen una propiedad que no se cumple en ninguna carta) e hipo- (grafos que no tienen una propiedad que se cumple en todas las cartas).
descomposición: Véase descomposición de árbol, descomposición de ruta o descomposición de rama.
degenerar
degeneración: Un grafo $k$ -degenerado es un grafo no dirigido en el que cada subgrafo inducido tiene un grado mínimo como máximo $de k$ . La degeneración de un grafo es el $k$ más pequeño para el cual es $k$ -degenerado. Un ordenamiento por degeneración es un ordenamiento de los vértices de modo que cada vértice tenga un grado mínimo en su subgrafo inducido y en todos los vértices posteriores; en un ordenamiento por degeneración de un grafo $k$ -degenerado, cada vértice tiene como máximo $k$ vecinos posteriores. La degeneración también se conoce como número de núcleo $k$ , ancho y ligamiento, y uno más la degeneración también se denomina número de coloración o número de Szekeres-Wilf. Los grafos $k$ -degenerados también se han denominado grafos $k -inductivos.$
grado: 1. El grado de un vértice en un grafo es su número de aristas incidentes. ^[2] El grado de un grafo $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 los grados de sus vértices, a menudo denotado $δ (G)$ . El grado a veces se llama valencia ; el grado de $v$ en $G$ puede denotarse $d G (v)$ , $d (G)$ o $deg(v)$ . El grado total es la suma de los grados de todos los vértices; por el lema de handshaking es un número par. La secuencia de grados es la colección de grados de todos los vértices, en orden ordenado del mayor al menor. En un grafo 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 un sinónimo de su número de Hadwiger , el orden del menor de los grupos más grandes.
Δ, δ: $Δ(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 grafo de n nodos, la densidad es la relación entre el número de aristas del grafo y el número de aristas de un grafo completo de n nodos. Véase grafo denso .
profundidad: La profundidad de un nodo en un árbol con raíz 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, hay que tener en cuenta que algunos autores utilizan la profundidad como sinónimo del nivel de un nodo. ^[9]
diámetro: El diámetro de un grafo conexo 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 en el grafo. Si el grafo tiene pesos en sus aristas, entonces su diámetro ponderado mide la longitud del camino por la suma de los pesos de las aristas a lo largo de un camino, mientras que el diámetro no ponderado mide la longitud del camino por el número de aristas. Para los grafos desconectados, las definiciones varían: el diámetro puede definirse como infinito, o como el diámetro más grande de un componente conexo, o puede ser indefinido.
diamante: El gráfico de diamante es un gráfico no dirigido con cuatro vértices y cinco aristas.
desconectado: Fuertemente conectado. (No debe confundirse con desconectado)
Digón: Un dígono es un ciclo simple de longitud dos en un grafo dirigido o un multigrafo. Los dígonos no pueden aparecer en grafos simples no dirigidos, ya que requieren repetir la misma arista dos veces, lo que viola la definición de grafo simple .
dígrafo: Sinónimo de gráfico dirigido . ^[2]
dipath: Ver ruta dirigida.
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 gráfico dirigido es aquel en el que las aristas tienen una dirección diferenciada, de un vértice a otro. ^[2] En un gráfico mixto , una arista dirigida es nuevamente aquella que tiene una dirección diferenciada; las aristas dirigidas también pueden denominarse arcos o flechas.
arco dirigido: Ver flecha.
borde dirigido: Ver flecha.
línea dirigida: Ver flecha.
camino dirigido: 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 predecesor de $y$ , $y$ es 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 una trayectoria dirigida.
desconectar: Provocar desconexión.
desconectado: No conectado.
desarticular: 1. Dos subgrafos son disjuntos en aristas si no comparten aristas, y disjuntos en vértices 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 grafo G se denomina 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 grafo es una partición de los vértices en conjuntos dominantes. El número domático del grafo 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 grafo; no debe confundirse con una cubierta de vértices, un conjunto de vértices que es incidente en todas las aristas del grafo. Los tipos especiales importantes de conjuntos dominantes incluyen conjuntos dominantes independientes (conjuntos dominantes que también son conjuntos independientes) y conjuntos dominantes conexos (conjuntos dominantes que inducen subgrafos conexos). Un conjunto dominante de un solo vértice también puede llamarse vértice universal. El número de dominación de un grafo es el número de vértices en el conjunto dominante más pequeño.
dual: Un gráfico dual de un gráfico plano $G$ es un gráfico que tiene un vértice para cada cara de $G.$

mi

mi: $E (G)$ es el conjunto de aristas de $G$ ; ver conjunto de aristas.
oreja: Una oreja de un grafo 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 de la oreja: Una descomposición en orejas es una partición de los bordes de un grafo en una secuencia de orejas, cada uno de cuyos puntos finales (después de la primera) pertenecen 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 en orejas abiertas es una descomposición en orejas en la que cada oreja después de la primera es abierta; un grafo tiene una descomposición en orejas abiertas si y solo si es biconectado. Una oreja es impar si tiene un número impar de aristas, y una descomposición en orejas impares es una descomposición en orejas en la que cada oreja es impar; un grafo tiene una descomposición en orejas impares si y solo si es factor crítico.
excentricidad: La excentricidad de un vértice es la distancia más lejana 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 grafos. Cada arista tiene dos (o en los hipergrafos, más) vértices a los que está unida, llamados sus puntos finales. Las aristas pueden ser dirigidas o no dirigidas; las aristas no dirigidas también se denominan líneas y las aristas dirigidas también se denominan arcos o flechas. En un grafo simple no dirigido , una arista puede representarse como el conjunto de sus vértices, y en un grafo simple dirigido puede representarse como un par ordenado de sus vértices. Una arista que conecta los vértices $x$ e $y$ a veces se escribe $xy$ .
corte de borde: Conjunto de aristas cuya eliminación desconecta el grafo. Un corte de una arista se denomina puente, istmo o arista cortada.
conjunto de bordes: El conjunto de aristas de un gráfico dado $G$ , a veces denotado por $E (G)$ .
gráfico sin aristas: El grafo sin aristas o totalmente desconectado en un conjunto dado de vértices es el grafo que no tiene aristas. A veces se lo llama grafo vacío, pero este término también puede referirse a un grafo sin vértices.
incrustación: Una incrustación de grafo es una representación topológica de un grafo como un subconjunto de un espacio topológico en el que cada vértice se representa como un punto, cada arista se representa como una curva que tiene los extremos de la arista como extremos de la curva y no hay otras intersecciones entre vértices o aristas. Un grafo plano es un grafo que tiene una incrustación de este tipo en el plano euclidiano, y un grafo toroidal es un grafo que tiene una incrustación de este tipo en un toro. El género de un grafo 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 no vacío de vértices.; 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 arista dada, o uno de los primeros o últimos vértices de un paseo, sendero o camino. El primer punto final de una arista dirigida dada se llama cola y el segundo punto final se llama cabeza .
enumeración: La enumeración de grafos es el problema de contar los grafos en una clase dada de grafos, en función de su orden. En términos más generales, los problemas de enumeración pueden referirse a problemas de contar una cierta 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 arista de un grafo exactamente una vez. Un circuito euleriano (también llamado ciclo euleriano o recorrido euleriano) es un recorrido cerrado que utiliza cada arista exactamente una vez. Un grafo euleriano es un grafo que tiene un circuito euleriano. Para un grafo no dirigido, esto significa que el grafo está conectado y cada vértice tiene un grado par. Para un grafo dirigido, esto significa que el grafo 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 relaja y un grafo que cumple solo los requisitos de grado se llama euleriano.
incluso: Divisible por dos; por ejemplo, un ciclo par es un ciclo cuya longitud es par.
expansor: Un gráfico expansor es un gráfico cuya expansión de aristas, expansión de vértices o expansión espectral está limitada a partir de cero.
expansión: 1. La expansión de aristas, número isoperimétrico o constante de Cheeger de un grafo $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 aristas que salen de $S$ al número de vértices en $S$ .; 2. La expansión de vértices, el número isoperimétrico de vértices o la magnificación de un grafo $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 exteriores pero adyacentes a $S$ al número de vértices en $S$ .; 3. La expansión vecina única de un grafo $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$ al número de vértices en $S$ .; 4. La expansión espectral de un grafo $d -regular$ $G$ es la brecha espectral entre el mayor valor propio $d$ de su matriz de adyacencia y el segundo mayor valor propio.; 5. Una familia de grafos tiene expansión acotada si todos sus $r$ -menores superficiales tienen una relació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 grafo plano o incrustación de grafos , un componente conexo del subconjunto del plano o superficie de la incrustación que es disjunto del grafo. Para una incrustación en el plano, todas las caras excepto una estarán acotadas; la única cara excepcional que se extiende hasta el infinito se denomina cara exterior.
factor: Un factor de un grafo es un subgrafo de expansión: un subgrafo que incluye todos los vértices del grafo. El término se utiliza principalmente en el contexto de subgrafos regulares: un factor $k$ es un factor que es $k$ -regular. En particular, un factor $1$ es lo mismo que una coincidencia perfecta. Un grafo con factor crítico es un grafo en el que al eliminar cualquier vértice se obtiene un grafo con un factor $1$ .
factorización: Una factorización de grafos es una partición de los bordes del grafo en factores; una factorización $k$ 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 sobre 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 grafos son finitos sin decirlo explícitamente. Un grafo es localmente finito si cada vértice tiene un número finito de aristas incidentes. Un grafo infinito es un grafo que no es finito: tiene infinitos vértices, infinitos aristas o ambos.
primer orden: La lógica de primer orden de grafos es una forma de lógica en la que las variables representan vértices de un grafo y existe un predicado binario para comprobar 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 flap se utiliza comúnmente en el contexto de havens , funciones que asignan pequeños conjuntos de vértices a sus flaps. Véase también el puente de un ciclo, que es un flap de los vértices del ciclo o una cuerda del ciclo.
prohibido: Una caracterización de grafo prohibido es una caracterización de una familia de 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, se dice que $H$ está prohibido.
gráfico de fuerza: Un gráfico forzado es un gráfico $H$ tal que evaluar la densidad de subgráficos de $H$ en los gráficos de una secuencia de gráficos $G(n)$ es suficiente para probar si esa secuencia es cuasialeatoria.
bosque: Un bosque es un gráfico no dirigido sin ciclos (una unión disjunta de árboles sin raíz) o un gráfico dirigido formado como una unión disjunta de árboles con raíz.
Fructo: 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 que establece que todo grupo finito es el grupo de simetrías de un grafo finito.
lleno: Sinónimo de inducido.
gráfico funcional: Un grafo funcional es un grafo dirigido en el que cada vértice tiene un grado de salida de 1. De manera equivalente, un grafo funcional es un pseudobosque dirigido maximalista.

GRAMO

GRAMO: Una variable que a menudo se utiliza para denotar 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, geodésica es sinónimo de camino más corto . Cuando se usa como adjetivo, significa que está relacionado con los caminos más cortos o las distancias de los caminos más cortos.
gigante: En la teoría de grafos aleatorios , un componente gigante es un componente conexo que contiene una fracción constante de los vértices del grafo. En los modelos estándar de grafos 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.
gráfico: Objeto fundamental de estudio en teoría de grafos, un sistema de vértices conectados de a pares por aristas. A menudo se subdividen en grafos dirigidos o grafos no dirigidos según si las aristas tienen orientación o no. Los grafos mixtos incluyen ambos tipos de aristas.
avaro: Producido por un algoritmo voraz . 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.
Gruñón: 1. Herbert Groötzsch; 2. El gráfico de Grötzsch , el gráfico libre de triángulos más pequeño que requiere cuatro colores para cualquier coloración adecuada.; 3. Teorema de Grötzsch que establece que los grafos planares sin triángulos siempre pueden colorearse con tres colores como máximo.
Número Grundy: 1. El número de Grundy de un gráfico es el número máximo de colores producidos por una coloración voraz , con un orden de vértices mal elegido.

yo

yo: Una variable que a menudo se utiliza para denotar un gráfico, especialmente cuando otro gráfico ya ha sido denotado por $G.$
Coloración H: Una coloración $H$ de un grafo $G$ (donde $H$ también es un grafo) es un homomorfismo de $H$ a $G.$
Libre de H: Un grafo es $H$ -libre si no tiene un subgrafo inducido isomorfo a $H$ , es decir, si $H$ es un subgrafo inducido prohibido. Los grafos $H$ -libres son la familia de todos los grafos (o, a menudo, todos los grafos finitos) que son $H$ -libres. ^[10] Por ejemplo, los grafos libres de triángulos son los grafos que no tienen un grafo triangular como subgrafo. La propiedad de ser $H$ -libre es siempre hereditaria. Un grafo es $H$ -libre de menores si no tiene un menor isomorfo a $H$ .
hadwiger: 1. Hugo Hadwiger; 2. El número de Hadwiger de un grafo es el orden del menor completo más grande del grafo. También se denomina número de clique 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: Un camino hamiltoniano o un ciclo hamiltoniano es un camino o ciclo de expansión simple: cubre todos los vértices del grafo exactamente una vez. Un grafo es hamiltoniano si contiene un ciclo hamiltoniano y trazable si contiene un camino hamiltoniano.
refugio: Un $k$ - haven es una función que asigna cada conjunto $X$ de menos de $k$ vértices a una de sus solapas, satisfaciendo a menudo condiciones de consistencia adicionales. El orden de un haven es el número $k$ . Los havens se pueden utilizar para caracterizar el ancho de árbol de grafos finitos y los extremos y números de Hadwiger de grafos 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 lo más largo posible, que se aleja 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 trayectoria dirigida en este gráfico.
hereditario: Una propiedad hereditaria de los grafos es una propiedad que está cerrada bajo subgrafos inducidos: si $G$ tiene una propiedad hereditaria, entonces también debe tenerla cada subgrafo inducido de $G.$ Compárese con monótono (cerrado bajo todos los subgrafos) o menor-cerrado (cerrado bajo menores).
hexágono: Un ciclo simple que consta de exactamente 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 antiagujero es un subgrafo inducido de orden cuatro cuyo complemento es un ciclo; equivalentemente, es un agujero en el grafo del complemento. Esta terminología se utiliza principalmente en el contexto de grafos perfectos, que se caracterizan por el teorema del grafo perfecto fuerte como los grafos sin agujeros impares o antiagujeros impares. Los grafos sin agujeros son los mismos que los grafos cordales .
equivalencia homomórfica: Dos grafos son homomórficamente equivalentes si existen dos homomorfismos, uno de cada grafo al otro grafo.
homomorfismo: 1. Un homomorfismo de grafos es una aplicación del conjunto de vértices de un grafo al conjunto de vértices de otro grafo que aplica vértices adyacentes a vértices adyacentes. Este tipo de aplicación entre grafos es la que se utiliza con más frecuencia en los enfoques de teoría de categorías para la teoría de grafos. Una coloración adecuada de grafos puede describirse de manera equivalente como un homomorfismo de un grafo completo.; 2. El grado de homomorfismo de un grafo es un sinónimo de su número de Hadwiger , el orden del menor de los grupos más grandes.
hiperarco: Un hiperborde dirigido que tiene un conjunto de origen y destino.
hiperborde: Un borde en un hipergrafo, 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 los bordes de un hipercubo geométrico .
hipergrafo: Un hipergrafo 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 grafo, indica un grafo que no tiene la propiedad pero que cada subgrafo formado al eliminar un solo vértice sí tiene la propiedad. Por ejemplo, un grafo hipohamiltoniano es uno que no tiene un ciclo hamiltoniano, pero para el cual cada eliminación de un vértice produce un subgrafo hamiltoniano. Compárese con crítico, utilizado para grafos 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 un cero en caso contrario.
incidente: La relación entre un borde 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 lo puede llamar conjunto estable o coclique. El número de independencia $α (G)$ es el tamaño del conjunto independiente máximo .; 2. En el matroide gráfico de un grafo, un subconjunto de aristas es independiente si el subgrafo correspondiente es un árbol o un bosque. En el 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; consulte adecuado.
inducido: Un subgrafo inducido o subgrafo completo de un grafo 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. Entre los casos especiales se incluyen los caminos inducidos y los ciclos inducidos , subgrafos inducidos que son caminos o ciclos.
inductivo: Sinónimo de degenerado.
infinito: Un gráfico infinito es aquel que no es finito; ver finito.
interno: Un vértice de un camino o á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 gráficos es su subgráfico común más grande, el gráfico formado por los vértices y las aristas que pertenecen a ambos gráficos.; 2. Un grafo de intersección es un grafo cuyos vértices corresponden a conjuntos u objetos geométricos, con una arista entre dos vértices exactamente cuando los dos conjuntos u objetos correspondientes tienen una intersección no vacía. Varias clases de grafos pueden definirse como los grafos de intersección de ciertos tipos de objetos, por ejemplo, grafos cordales (grafos de intersección de subárboles de un árbol), grafos circulares (grafos de intersección de cuerdas de un círculo), grafos de intervalo (grafos de intersección de intervalos de una línea), grafos lineales (grafos de intersección de las aristas de un grafo) y grafos de clique (grafos de intersección de los cliques máximos de un grafo). Cada grafo es un grafo de intersección para alguna familia de conjuntos, y esta familia se llama representación de intersección del grafo. El número de intersección de un grafo $G$ es el número total mínimo de elementos en cualquier representación de intersección de $G$ .
intervalo: 1. Un gráfico de intervalo es un gráfico de intersección de intervalos de una línea .; 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 grosor del intervalo es sinónimo de ancho de ruta.
invariante: Un 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 grafo es un vértice cuyo grado es cero, es decir, un vértice sin aristas incidentes. ^[2]
isomorfo: Dos grafos son isomorfos si existe un isomorfismo entre ellos; ver isomorfismo.
isomorfismo: Un isomorfismo de grafos es una incidencia biunívoca que preserva la correspondencia de los vértices y aristas de un grafo con los vértices y aristas de otro grafo. Dos grafos relacionados de esta manera se denominan isomorfos.
isoperimétrico: Ver expansión.
istmo: Sinónimo de puente, en el sentido de arista cuya eliminación desconecta el grafo.

Yo

unirse: La unión de dos grafos se forma a partir de su unión disjunta, añadiendo una arista de cada vértice de un grafo a cada vértice del otro. Equivalentemente, es el complemento de la unión disjunta de los complementos.

K

K: Para 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: Un núcleo de un gráfico dirigido es un conjunto de vértices que es a la vez estable y absorbente.
nudo: Sección ineludible de un grafo dirigido. Véase nudo (matemáticas) y teoría de nudos .

yo

yo: $L (G)$ es el gráfico 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 etiquetado en el vértice o etiquetado en la arista pueden usarse 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 la que las etiquetas se interpretan como colores.; 2. En el contexto de la enumeración de grafos , se dice que los vértices de un grafo están etiquetados si todos son distinguibles entre sí. Por ejemplo, esto se puede hacer que sea cierto fijando una correspondencia biunívoca entre los vértices y los números enteros desde 1 hasta el orden del grafo. Cuando los vértices están etiquetados, los grafos que son isomorfos entre sí (pero con diferentes órdenes de vértices) se cuentan como objetos separados. Por el contrario, cuando los vértices no están etiquetados, los grafos 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.$ Una arista de hoja o arista colgante es la arista que conecta un vértice de hoja con su único vecino.; 2. Una potencia de hojas de un árbol es un grafo cuyos vértices son las hojas del árbol y cuyos bordes 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 la cantidad de aristas que utiliza. En un gráfico ponderado, puede ser la suma de los pesos de las aristas que utiliza. La longitud se utiliza para definir la ruta más corta , la circunferencia (la longitud del ciclo más corto) y la ruta más larga entre dos vértices de 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 con raíz es el número de nodos en la ruta desde la raíz hasta el nodo. Por ejemplo, la raíz tiene nivel 1 y cualquiera de sus nodos adyacentes tiene nivel 2.; 2. Conjunto de todos los nodos que tienen el mismo nivel o profundidad. ^[12]
línea: Sinónimo de arista no dirigida. El grafo lineal $L (G)$ de un grafo $G$ es un grafo 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: Un 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 grafo es una propiedad que está determinada únicamente por los alrededores de los vértices del grafo. Por ejemplo, un grafo es localmente finito si todos sus alrededores son finitos.
bucle: Un bucle o bucle propio es una arista cuyos extremos son el mismo vértice. Forma un ciclo de longitud $1.$ No se permiten en grafos simples.

METRO

aumento: Sinónimo de expansión de vértice.
pareo: Un emparejamiento es un conjunto de aristas en el que no hay dos que compartan ningún vértice. Un vértice está emparejado o saturado si es uno de los puntos finales de una arista en el emparejamiento. Un emparejamiento perfecto o emparejamiento completo es un emparejamiento que coincide con todos los vértices; también puede llamarse 1-factor, y solo puede existir cuando el orden es par. Un emparejamiento casi perfecto, en un grafo con orden impar, es uno que satura todos los vértices menos uno. Un emparejamiento máximo es un emparejamiento que utiliza tantas aristas como sea posible; el número de emparejamiento $α'(G)$ de un grafo $G$ es el número de aristas en un emparejamiento máximo. Un emparejamiento máximo es un emparejamiento al que no se pueden agregar aristas adicionales.
máximo: 1. Un subgrafo de un grafo dado $G$ es maximal para una propiedad particular si posee esa propiedad pero ningún otro supergrafo de él que también sea un subgrafo de $G$ posee la misma propiedad. Es decir, es un elemento maximal de los subgrafos con la propiedad. Por ejemplo, una camarilla maximal es un subgrafo completo que no se puede expandir a un subgrafo completo mayor. La palabra "maximal" debe distinguirse de "máximo": un subgrafo máximo siempre es maximal, pero no necesariamente al revés.; 2. Un grafo simple con una propiedad dada es máximo para esa propiedad si no es posible agregarle más aristas (manteniendo el conjunto de vértices sin cambios) mientras se preserva tanto la simplicidad del grafo como la propiedad. Así, por ejemplo, un grafo plano maximal es un grafo plano tal que agregarle más aristas crearía un grafo no plano.
máximo: Un subgrafo de un grafo $G$ dado 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 grafo dado.
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 medianos y gráficos modulares .; 2. Un gráfico mediano es un gráfico en el 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 grafo dado es mínimo para una propiedad particular si posee esa propiedad pero ningún subgrafo propio de él posee también la misma propiedad. Es decir, es un elemento mínimo de los subgrafos con la propiedad.
corte minimo: Un corte cuyo conjunto de cortes tiene un peso total mínimo, posiblemente restringido a cortes que separan un par designado de vértices; se caracterizan por el teorema de corte mínimo de flujo máximo .
menor: Un grafo $H$ es un menor de otro grafo $G$ si $H$ se puede obtener eliminando aristas o vértices de $G$ y contrayendo aristas en $G$ . Es un menor superficial si se puede formar como un menor de tal manera que los subgrafos de $G$ que se contrajeron para formar vértices de $H$ tengan todos 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$ . Un grafo es $H$ -libre de menores si no tiene $a H$ como menor. Una familia de grafos es cerrada con menores si está cerrada bajo menores; el teorema de Robertson-Seymour caracteriza a las familias cerradas con menores como si tuvieran un conjunto finito de menores prohibidos.
mezclado: Un gráfico mixto es un gráfico que puede incluir aristas dirigidas y no dirigidas.
modular: 1. Grafo modular , un grafo en el que cada triple de vértices tiene al menos un vértice mediano que pertenece a los caminos más cortos entre todos los pares del triple.; 2. Descomposición modular , una descomposición de un gráfico en subgráficos dentro de los cuales todos los vértices se conectan al resto del gráfico de la misma manera.; 3. Modularidad de un agrupamiento de gráficos, la diferencia del número de aristas entre clústeres respecto de su valor esperado.
monótono: Una propiedad monótona de los grafos es una propiedad que está cerrada bajo subgrafos: si $G$ tiene una propiedad monótona, entonces también debe tenerla cada subgrafo de $G.$ Compárese con hereditario (cerrado bajo subgrafos inducidos) o menor-cerrado (cerrado bajo menores).
Gráfica de Moore: Un grafo de Moore es un grafo regular para el cual se cumple exactamente el límite de Moore. El límite de Moore es una desigualdad que relaciona el grado, el diámetro y el orden de un grafo, demostrada por Edward F. Moore . Todo grafo de Moore es una jaula.
multigrafo: Un multigrafo es un grafo que permite múltiples adyacencias (y, a menudo, bucles propios); un grafo que no necesita ser simple.
adyacencia múltiple: Una adyacencia múltiple o arista múltiple es un conjunto de más de una arista que tienen todos los mismos puntos finales (en la misma dirección, en el caso de grafos dirigidos). Un grafo con múltiples aristas se suele denominar multigrafo.
multiplicidad: La multiplicidad de una arista es el número de aristas en una adyacencia múltiple. La multiplicidad de un grafo es la multiplicidad máxima de cualquiera de sus aristas.

norte

norte: 1. Para la notación de vecindarios abiertos y cerrados, véase vecindario.; $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: El entorno abierto (o vecindad) de un vértice $v$ es el subgrafo inducido por todos los vértices adyacentes a $v$ . El entorno cerrado se define de la misma manera, pero también incluye al propio $v$ . El entorno abierto de $v$ en $G$ puede denotarse $como N G (v)$ o $N (v)$ , y el entorno cerrado puede denotarse como $N G [v]$ o $N [v]$ . Cuando no se especifica la apertura o el cierre de un entorno, se supone que es 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: Un no borde o antiborde es un par de vértices que no son adyacentes; los bordes del gráfico complementario.
gráfico nulo: Ver gráfico vacío.

Oh

extraño: 1. Un ciclo impar es un ciclo cuya longitud es impar. La circunferencia impar de un grafo no bipartito es la longitud de su ciclo impar más corto. Un agujero impar es un caso especial de un 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. Por el lema del apretón de manos, todo grafo finito no dirigido tiene un número par de vértices impares.; 3. Una oreja impar es una ruta simple o un ciclo simple con un número impar de aristas, utilizado en descomposiciones de orejas impares 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. Las cuerdas impares se utilizan para definir grafos fuertemente cordales .; 5. Un grafo impar es un caso especial de un grafo de Kneser , que tiene un vértice para cada subconjunto de $(n - 1)$ elementos de un conjunto de $(2n - 1)$ elementos, y una arista que conecta dos subconjuntos cuando sus conjuntos correspondientes son disjuntos.
abierto: 1. Ver barrio.; 2. Ver caminar.
orden: 1. El orden de un grafo $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 grafo es una disposición de sus vértices en una secuencia, especialmente en el contexto del ordenamiento topológico (un orden de un grafo acíclico dirigido en el que cada arista va de un vértice anterior a un vértice posterior en el orden) y el ordenamiento de degeneración (un orden en el que cada vértice tiene un grado mínimo en el subgrafo inducido de él y todos los vértices posteriores).; 4. Para el orden de un refugio o zarza, véase refugio y zarza.
orientación
orientado: 1. La orientación de un grafo no dirigido es la asignación de direcciones a sus aristas, lo que lo convierte en un grafo dirigido. Un grafo 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 hay ningún requisito de consistencia en las direcciones de sus aristas. Otros tipos especiales de orientación incluyen las orientaciones de grafos completos, las orientaciones fuertes , las orientaciones que están fuertemente conectadas; las orientaciones acíclicas , las orientaciones que son acíclicas; las orientaciones eulerianas , las orientaciones que son eulerianas; y las orientaciones transitivas , las orientaciones que están transitivamente cerradas.; 2. Grafo orientado, utilizado por algunos autores como sinónimo de grafo dirigido .
grado de salida: Ver grado.
exterior: Ver cara.
plano exterior: Un gráfico exterior-planar 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 con raíz, un padre de un vértice $v$ es un 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, sin aristas (también llamado camino simple), según la fuente. Algunos casos especiales importantes son los caminos inducidos y los caminos más cortos .
descomposición de trayectoria: Una descomposición de ruta de un grafo $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 árbol, como uno menos que el tamaño de la bolsa más grande. El ancho mínimo de cualquier descomposición de ruta de $G$ es el ancho de ruta de $G.$
ancho de ruta: El ancho de ruta de un grafo $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 clique de una completitud de intervalo de $G.$ Siempre se encuentra entre el ancho de banda y el ancho de árbol de $G.$ También se lo conoce como grosor de intervalo, número de separación de vértices o número de búsqueda de nodos.
colgante: Ver hoja.
perfecto: 1. Un grafo perfecto es un grafo en el que, en cada subgrafo inducido, el número cromático es igual al número de clique. El teorema del grafo perfecto y el teorema del grafo perfecto fuerte son dos teoremas sobre grafos perfectos; el primero demuestra que sus complementos también son perfectos y el segundo demuestra que son exactamente los grafos sin agujeros impares ni antiagujeros.; 2. Un grafo perfectamente ordenable es un grafo cuyos vértices pueden ordenarse de tal manera que un algoritmo de coloración voraz con este ordenamiento coloree de manera óptima cada subgrafo inducido. Los grafos perfectamente ordenables son una subclase de los grafos perfectos.; 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 forman un ciclo hamiltoniano.
periférico: 1. Un ciclo periférico o ciclo no separativo 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, 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 que establece que todo grafo cúbico sin puente tiene un emparejamiento perfecto.
plano: Un grafo plano es un grafo que tiene una incrustación en el plano euclidiano. Un grafo plano es un grafo plano para el cual ya se ha fijado una incrustación particular. Un grafo $k$ -planar es uno que se puede dibujar en el plano con un máximo $de k$ cruces por arista.
poliárbol: Un poliárbol es un árbol orientado; equivalentemente, un gráfico acíclico dirigido cuyo gráfico no dirigido subyacente es un árbol.
fuerza: 1. Una potencia de grafo $G k$ de un grafo $G$ es otro grafo en el mismo conjunto de vértices; dos vértices son adyacentes en $G k$ cuando están a una distancia de como máximo $k$ en $G$ . Una potencia de hoja es un concepto estrechamente relacionado, derivado de una potencia de un árbol al tomar 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, biclícuotas 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 viene antes de un vértice dado en una trayectoria dirigida.
adecuado: 1. Un subgrafo propio es un subgrafo que elimina al menos un vértice o arista en relación con todo el grafo; para grafos finitos, los subgrafos propios nunca son isomorfos a todo el grafo, pero para grafos 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 propio o un gráfico de arco circular propio es un gráfico de intersección de un conjunto de intervalos o arcos circulares (respectivamente) de modo que ningún intervalo o arco contiene otro intervalo o arco. Los gráficos de intervalo propio también se denominan gráficos de intervalo unitario (porque siempre se pueden representar mediante intervalos unitarios) o gráficos de indiferencia.
propiedad: Una propiedad de un grafo es algo que puede ser verdadero en el caso de algunos grafos y falso en el de otros, y que depende únicamente de la estructura del grafo y no de información incidental como las etiquetas. Las propiedades de un grafo pueden describirse de manera equivalente en términos de clases de grafos (los grafos que tienen una propiedad dada). De manera más general, una propiedad de un grafo también puede ser una función de los grafos que es, a su vez, independiente de información incidental, como el tamaño, el orden o la secuencia de grados de un grafo; esta definición más general de una propiedad también se denomina invariante del grafo.
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.
seudónimo: Un pseudografo es un grafo o multigrafo que permite bucles propios.

Q

gráfico cuasi-lineal: Un grafo cuasi-lineal o grafo localmente co-bipartito es un grafo en el que el entorno abierto de cada vértice puede dividirse en dos grupos. Estos grafos son siempre libres de garras e incluyen como caso especial los grafos lineales . Se utilizan en la teoría de la estructura de grafos libres de garras.
secuencia de grafos cuasialeatorios: Una secuencia de gráficos cuasialeatorios es una secuencia de gráficos que comparte varias propiedades con una secuencia de gráficos aleatorios generados según el modelo de gráficos aleatorios de Erdős–Rényi .
carcaj: Un carcaj es un multigrafo dirigido, como se usa en la teoría de categorías . Los bordes de un carcaj se llaman flechas.

R

radio: El radio de un gráfico es la excentricidad mínima de cualquier vértice.
Ramanujan: Un grafo de Ramanujan es un grafo cuya expansión espectral es lo más grande posible. Es decir, es un grafo $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 grafo infinito, es un camino infinito simple con exactamente un punto final. Los extremos de un grafo son clases de equivalencia de rayos.
Accesibilidad: La capacidad de llegar de un vértice a otro dentro de un gráfico.
accesible: Tiene una alcanzabilidad afirmativa. Se dice que un vértice $y$ es alcanzable desde un vértice $x$ si existe un camino desde $x$ hasta $y$ .
reconocible: En el contexto de la conjetura de reconstrucción , una propiedad de un grafo es reconocible si su verdad puede determinarse a partir de la estructura del grafo. Se sabe que muchas propiedades de grafos son reconocibles. Si la conjetura de reconstrucción es verdadera, todas las propiedades de grafos son reconocibles.
reconstrucción: La conjetura de reconstrucción establece que cada grafo no dirigido $G$ está determinado de forma única por su mazo , un multiconjunto de grafos formados eliminando un vértice de $G$ de todas las formas posibles. En este contexto, la reconstrucción es la formación de un grafo a partir de su mazo.
rectángulo: Un ciclo simple que consta exactamente de cuatro aristas y cuatro vértices.
regular: Un grafo es $d$ -regular cuando todos sus vértices tienen grado $d$ . Un grafo regular es un grafo que es $d$ -regular para algún $grado d$ .
torneo regular: Un torneo regular 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íz .; 2. La operación inversa a una potencia de grafo : una raíz $k$ -ésima de un grafo $G$ es otro grafo en el mismo conjunto de vértices tal que dos vértices son adyacentes en $G$ si y sólo si tienen distancia como máximo $k$ en la raíz.

S

saturado: Ver coincidencia.
buscando numero: El número de búsqueda de nodo es un sinónimo de ancho de ruta.
segundo orden: La lógica de segundo orden de los grafos 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 comprobar 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 solo pueden representar vértices.
bucle propio: Sinónimo de bucle.
vértice separador: Ver punto de articulación.
número de separación: El número de separación de vértices es un sinónimo de ancho de ruta.
hermano: En un árbol con raíz, un hermano de un vértice $v$ es un vértice que tiene el mismo vértice padre que $v$ .
simple: 1. Un grafo simple es un grafo sin bucles y sin múltiples adyacencias. Es decir, cada arista conecta dos extremos distintos y no hay dos aristas que tengan los mismos extremos. Una arista simple es una arista que no forma parte de una adyacencia múltiple. En muchos casos, se supone que los grafos 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 salientes (el grado de salida es igual a 0).
tamaño: El tamaño de un grafo $G$ es el número de sus aristas, $| E (G)|$ . ^[13] La variable $m$ se utiliza a menudo para esta cantidad. Véase también orden , el número de vértices.
red de 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 cualquier otro nodo mediante una pequeña cantidad de saltos o pasos. En concreto, una red de mundo pequeño se define como un gráfico en el que la distancia típica L entre dos nodos elegidos al azar (la cantidad de pasos necesarios) crece proporcionalmente al logaritmo de la cantidad de nodos N en la red ^[14].
sarcasmo: Un snark es un gráfico cúbico simple, conexo y sin puente 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 la teoría de grafos algebraicos , varios espacios vectoriales sobre el cuerpo binario pueden estar asociados con un grafo. Cada uno tiene conjuntos de aristas o vértices para sus vectores, y la diferencia simétrica de conjuntos como su operación de suma vectorial. 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 aristas que tiene los conjuntos de corte del grafo como sus elementos. El espacio de ciclo tiene los subgrafos de expansión euleriana como sus elementos.
llave: Un spanner es un grafo (normalmente disperso) cuyas distancias de ruta más cortas se aproximan a las de un grafo denso u otro espacio métrico. Las variaciones incluyen spanners geométricos , grafos cuyos vértices son puntos en un espacio geométrico; spanners de árbol , árboles de expansión de un grafo cuyas distancias se aproximan a las distancias del grafo, y spanners de grafo, subgrafos dispersos de un grafo denso cuyas distancias se aproximan a las distancias del grafo original. Un spanner voraz es un spanner de grafo construido mediante un algoritmo voraz, generalmente uno que considera todas las aristas desde la más corta a la más larga y conserva las que se necesitan para preservar la aproximación de la distancia.
abarcando: Un subgrafo es generador cuando incluye todos los vértices del grafo dado. Algunos casos importantes son los árboles generadores , los subgrafos generadores que son árboles y los emparejamientos perfectos , los subgrafos generadores que son emparejamientos. Un subgrafo generador también puede denominarse factor , especialmente (pero no solo) cuando es regular.
escaso: Un grafo 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 grafo dado.
espectral
espectro: El espectro de un grafo es el conjunto de valores propios de su matriz de adyacencia. La teoría espectral de grafos es la rama de la teoría de grafos que utiliza los espectros para analizar grafos. Véase también expansión espectral.
dividir: 1. Un grafo dividido es un grafo cuyos vértices se pueden dividir en un grupo y un conjunto independiente. Una clase relacionada de grafos, los grafos divididos doblemente, se utilizan en la demostración del teorema fuerte del grafo perfecto.; 2. Una división de un grafo arbitrario es una partición de sus vértices en dos subconjuntos no vacíos, de modo que las aristas que abarcan este corte forman un subgrafo bipartito completo. Las divisiones de un grafo se pueden representar mediante una estructura de árbol llamada descomposición de divisiones . Una división se denomina división fuerte cuando no está atravesada por ninguna otra división. Una división se denomina no trivial cuando ambos lados tienen más de un vértice. Un grafo se denomina primo cuando no tiene divisiones no triviales.; 3. La división de vértices (a veces llamada escisión de vértices) es una operación gráfica elemental que divide un vértice en dos, donde estos dos nuevos vértices son adyacentes a los vértices a los que estaba adyacente el vértice original. La operación inversa de la división de vértices es la contracción de vértices.
cuadrado: 1. El cuadrado de un grafo $G$ es la potencia del grafo $G 2$ ; en la otra dirección, $G$ es la raíz cuadrada de $G 2$ . El semicuadrado de un grafo bipartito es el subgrafo de su cuadrado inducido por un lado de la bipartición.; 2. Un cuadrángulo es un grafo plano que se puede dibujar de modo que todas las caras delimitadas sean 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 reticular 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 un conjunto independiente.
estrella: Una estrella es un árbol con un vértice interno; equivalentemente, es un grafo bipartito completo $K 1, n$ para algún $n \geq 2$ . El caso especial de una estrella con 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áloga a la tenacidad, basada en las eliminaciones de vértices.
fuerte: 1. Para conocer la conectividad fuerte y los componentes fuertemente conectados de los grafos dirigidos, véase conectado y componente. Una orientación fuerte es una orientación que está fuertemente conectada; véase orientación.; 2. Para el teorema del grafo perfecto fuerte , véase perfecto.; 3. Un gráfico fuertemente regular es un gráfico regular en el que cada dos vértices adyacentes tienen el mismo número de vecinos compartidos y cada dos vértices no adyacentes tienen el mismo número de vecinos compartidos.; 4. Un grafo fuertemente cordal es un grafo cordal en el que cada ciclo par de longitud seis o más tiene una cuerda impar.; 5. Un grafo fuertemente perfecto es un grafo en el que cada subgrafo inducido tiene un conjunto independiente que cumple con todos los cliques maximales. Los grafos de Meyniel también se denominan "grafos muy fuertemente perfectos" porque en ellos cada vértice pertenece a dicho 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 las 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 de expansión es aquel que incluye todos los vértices del grafo; 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, en el caso de los árboles con raíz, los subárboles se definen como un tipo especial de subgrafo conectado, formado por todos los vértices y aristas a los que se puede llegar desde un vértice elegido.
sucesor: Un vértice que viene después de un vértice dado en una trayectoria dirigida.
superconcentrador: Un superconcentrador es un grafo con dos subconjuntos designados e iguales de vértices $I$ y $O$ , de modo que por cada dos subconjuntos iguales de $S$ 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 sus fuentes y $O$ como sus sumideros.
supergrafo: Un gráfico formado al sumar vértices, aristas o ambos a un gráfico dado. Si $H$ es un subgrafo de $G$ , entonces $G$ es un supergrafo de $H$ .

yo

teta: 1. Un gráfico theta es la unión de tres caminos internamente disjuntos (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 una arista por cono, hasta el punto cuya proyección sobre un rayo central del cono sea más pequeña.; 3. El número de Lovász o función theta de Lovász de un grafo es un invariante gráfico relacionado con el número de clique y el número cromático que se puede calcular en tiempo polinomial 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 ordenació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 de un vértice anterior a un vértice posterior en la secuencia.
totalmente desconectado: Sinónimo de sin bordes.
recorrido: Un recorrido cerrado, un recorrido que comienza y termina en el mismo vértice y no tiene aristas repetidas. Los recorridos de Euler son recorridos que utilizan todas las aristas del grafo; véase 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 por exactamente una arista dirigida (que va en solo 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 grafo dirigido dado es un grafo en el mismo conjunto de vértices que tiene una arista de un vértice a otro siempre que el grafo original tenga un camino que conecte los mismos dos vértices. Una reducción transitiva de un grafo es un grafo minimal que tiene el mismo cierre transitivo; los grafos acíclicos dirigidos tienen una reducción transitiva única. Una orientación transitiva es una orientación de un grafo que es su propio cierre transitivo; existe solo para grafos de comparabilidad .
transponer: El grafo transpuesto de un grafo dirigido dado es un grafo con los mismos vértices, con cada arista invertida en su dirección. También se lo puede llamar el inverso del grafo.
á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 árbol k es un grafo formado al unir $(k + 1)$ grupos de grupos en grupos de grupos $k$ compartidos . 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 grafo $G$ es un árbol cuyos nodos están etiquetados con conjuntos de vértices de $G$ ; estos conjuntos se denominan bolsas. Para cada vértice $v$ , las bolsas que contienen $a v$ deben inducir un subárbol del árbol, y para cada arista $uv$ debe existir una bolsa que contenga tanto $a u$ como $a v$ . El ancho de una descomposición en á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 en árbol de $G$ .
ancho del árbol: El ancho de árbol de un grafo $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 completitud 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 grafo. Un grafo sin triángulos es un grafo no dirigido que no tiene ningún subgrafo triangular.
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 denomina gráfico nulo .
Turan: 1. Pal Turán; 2. Un gráfico de Turán es un gráfico multipartito completo equilibrado.; 3. El teorema de Turán establece que los grafos de Turán tienen el número máximo de aristas entre todos los grafos libres de camarillas de un orden dado.; 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 el mismo vecindario cerrado: $N G [u] = N G [v]$ (esto implica que $u$ y $v$ son vecinos), y son falsos gemelos si tienen el mismo vecindario abierto: $N G (u) = N G (v))$ (esto implica que $u$ y $v$ no son vecinos).

tú

vértice unario: En un árbol con raíz, un vértice unario es un vértice que tiene exactamente un vértice hijo.
Sin dirección: Un grafo no dirigido es un grafo en el que los dos puntos finales de cada arista no se distinguen entre sí. Véase también dirigido y mixto . En un grafo 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 algún $k$ . Por ejemplo, los grafos ordinarios son lo mismo que los hipergrafos $2$ -uniformes.
universal: 1. Un gráfico universal es un gráfico que contiene como subgráficos todos los gráficos de una familia dada de gráficos, o todos los gráficos de un tamaño u orden dado dentro de una familia dada de gráficos.; 2. Un vértice universal (también llamado vértice dominante o ápice) es un vértice que se encuentra 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 gráficos , un vértice que está cuantificado universalmente en una fórmula puede llamarse vértice universal para esa fórmula.
gráfico no ponderado: Un gráfico cuyos vértices y aristas no tienen pesos asignados; lo opuesto de 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 (en plural, vértices) es (junto con las aristas) una de las dos unidades básicas a partir de las cuales se construyen los grafos. Los vértices de los grafos suelen considerarse objetos atómicos, sin estructura interna.
corte de vértice
conjunto separador: Conjunto de vértices cuya eliminación desconecta el grafo. 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 .
Vistiendo: 1. Vadim G. Vizing; 2. Teorema de Vizing según el cual el índice cromático es como máximo uno más que el grado máximo.; 3. Conjetura de Vizing sobre el número dominante de productos cartesianos de grafos.
volumen: La suma de los grados de un conjunto de vértices.

Yo

$Yo$: La letra $W$ se utiliza en la notación de gráficos de ruedas y de molinos de viento . La notación no está estandarizada.
Wagner: 1. Klaus Wagner; 2. El grafo de Wagner , una escalera de Möbius de ocho vértices.; 3. Teorema de Wagner que caracteriza a los grafos planares por sus menores prohibidos.; 4. Teorema de Wagner que caracteriza los grafos libres $de K 5$ menores.
caminar: Un paseo es una secuencia finita o infinita de aristas que une una secuencia de vértices . A los paseos también se les llama a veces cadenas . ^[17] Un paseo es abierto si su primer y último vértice son distintos, y cerrado si se repiten.
débilmente conectado: Un gráfico dirigido se denomina débilmente conexo si al reemplazar todos sus bordes dirigidos por bordes no dirigidos se produce un gráfico conexo (no dirigido).
peso: Valor numérico asignado como etiqueta a un vértice o arista de un gráfico. El peso de un subgráfico es la suma de los pesos de los vértices o aristas dentro de ese subgráfico.
gráfico ponderado: Un gráfico cuyos vértices o aristas tienen pesos asignados. Un gráfico ponderado por vértices tiene pesos en sus vértices y un gráfico ponderado por aristas tiene pesos en sus aristas.
bien coloreado: Un gráfico bien coloreado es un gráfico en el que todos sus coloridos codiciosos utilizan el mismo número de colores.
bien cubierto: Un gráfico bien cubierto es un gráfico cuyos conjuntos independientes máximos tienen todos el 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 otros invariantes de gráficos conocidos 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 de una descomposición de ruta es uno menos que el tamaño máximo de una de sus bolsas, y puede usarse para definir el ancho del árbol y el ancho de la ruta.; 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 son distintos.

Véase también

Referencias

^ Farber, M.; Hahn, G.; Hell, P.; Miller, DJ (1986), "Sobre el número acromático de grafos", 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 grafos planares", 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 de enlace de un gráfico y su número de Anderson", J. Combin. Theory 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 , 99 (2), Elsevier BV: 512–530, doi :10.1016/j.jctb.2008.10.002
^ Sudakov, Benny; Volec, Jan (2017), "Copias de grafos coloreadas correctamente y en arco iris con pocas cerezas", 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 grafos: una encuesta, Monografías SIAM sobre matemáticas discretas y aplicaciones, págs. 105-121, ISBN 978-0-89871-432-6
^ Mitchem, John (1969), "Hipopropiedades en grafos", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) , Lecture Notes in Mathematics, vol. 110, Springer, págs. 223-230, doi :10.1007/BFb0060121, ISBN 978-3-540-04629-5, Sr. 0253932.
^ nivel ab , NIST
^ Harris, John M. (2000), Combinatoria y teoría de grafos, Nueva York: Springer-Verlag, pág. 5, ISBN 978-0-387-98736-1
^ Watts, Duncan J.; Strogatz, Steven H. (junio de 1998), "Dinámica colectiva de redes de 'mundo pequeño'", 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, Mich., 1972; dedicado a la memoria de JWT Youngs) , Lecture Notes in Mathematics, vol. 303, Springer, pp. 43–54, doi :10.1007/BFb0067356, ISBN 978-3-540-06096-3, Sr. 0335362
^ Diestel, Reinhard (2017), Teoría de grafos, Textos de posgrado en matemáticas, vol. 173, Berlín, Heidelberg: Springer Berlin Heidelberg, p. 2, doi :10.1007/978-3-662-53622-3, ISBN 978-3-662-53621-6
^ "Teoría de cadenas y grafos", britannica.com , consultado el 25 de marzo de 2018

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