Glosario de teoría de grafos

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 de dos en dos 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 prima se usa a menudo para modificar la notación de los invariantes de grafos, de modo que se aplique al grafo de líneas en lugar del grafo dado. Por ejemplo, $α (G)$ es el número de independencia de un grafo; $α'(G)$ es el número de correspondencia del grafo, que es igual al número de independencia de su grafo de líneas. 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 de líneas.

A

absorbente: Un conjunto fascinante $A$ de un grafo dirigido $G$ es un conjunto de vértices tal que para cualquier vértice $v\in G\setminus A$ , hay un borde de $v$ hacia un vértice de $A$ .
acromático: El número acromático de un gráfico es el número máximo de colores en una coloración completa. ^{[ 1 ]}
acíclico: 1. 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 digrafo sin ciclos dirigidos, se suele llamar grafo acíclico dirigido , especialmente en informática. ^[²^]; 2. Una coloración acíclica de un grafo no dirigido es una coloración propia en la que cada dos clases de color inducen un bosque. ^[³^]
matriz de adyacencia: La matriz de adyacencia de un grafo es una matriz cuyas filas y columnas están indexadas por los vértices del grafo, con un uno en la celda de la fila $i$ y la columna $j$ cuando los vértices $i$ y $j$ son adyacentes, y un cero en caso contrario. ^{[ 4 ]}
adyacente: 1. La relación entre dos vértices que son ambos extremos de la misma arista. ^[²^]; 2. La relación entre dos aristas distintas que comparten un vértice final. ^[⁵^]
α: Para un grafo $G$ , $α (G)$ (usando la letra griega alfa) es su número de independencia (ver independiente ), y $α'(G)$ es su número de coincidencia (ver coincidencia ).
alterno: En un grafo con un emparejamiento, un camino alternante es aquel cuyas aristas se alternan entre emparejadas y no emparejadas. De manera similar, un ciclo alternante es aquel cuyas aristas se alternan entre emparejadas y no emparejadas. Un camino de aumento es un camino alternante que comienza y termina en vértices no saturados. Un emparejamiento mayor se puede encontrar como la diferencia simétrica entre el emparejamiento y el camino de aumento; un emparejamiento es máximo si y solo si no tiene un camino de aumento.
anticadena: En un grafo dirigido acíclico , un subconjunto $S$ de vértices que son incomparables por pares, es decir, para cualquier $x\leq y$ En $S$ , no hay un camino dirigido de $x$ a $y$ ni de $y$ a $x$ . Inspirado en la noción de anticadenas en conjuntos parcialmente ordenados .
anti-borde: Sinónimo de no-arista , un par de vértices no adyacentes.
antitriángulo: Un conjunto independiente de tres vértices, el complemento de un triángulo.
ápex: 1. Un grafo con vértice es aquel en el que se puede eliminar un vértice, dejando un subgrafo planar . El vértice eliminado se denomina vértice. Un grafo $con k$ vértices es aquel que puede hacerse planar 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; véase árbol .
arco: Ver borde .
flecha: Un par ordenado de vértices , como una arista en un grafo dirigido . Una flecha $(x, y)$ tiene un origen $x$ , un destino $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 grafo conexo cuya eliminación desconectaría el grafo. De forma más general, un vértice cuya eliminación aumenta el número de componentes .
-ario: Un árbol $k$ -ario es un árbol con raíz en el que cada vértice interno tiene como máximo $k$ hijos. Un árbol 1-ario es simplemente un camino. Un árbol 2-ario también se denomina árbol binario , aunque este término se refiere más propiamente a los á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 es completo si cada vértice interno tiene exactamente $k$ hijos.
aumentando: Un tipo especial de camino alterno; véase alterno .
automorfismo: Un automorfismo de grafo es una simetría de un grafo, un isomorfismo del grafo en sí mismo.

B

bolsa: Uno de los conjuntos de vértices en una descomposición en árbol .
equilibrado: Un grafo bipartito o multipartito está equilibrado si cada par de subconjuntos de su partición de vértices tienen tamaños que no difieren en más de una unidad entre sí.
pelota: Una bola (también conocida como bola de vecindad o bola de distancia) es el conjunto de todos los vértices que se encuentran a una distancia máxima de r de un vértice. De forma más formal, para un vértice v y un radio r dados, la bola B(v,r) consta de todos los vértices cuya distancia de camino más corto a v es menor o igual a r.
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 extremos). También es uno menos que el tamaño de la camarilla máxima en una completación de intervalos propia de $G$ , elegida para minimizar el tamaño de la camarilla.
bicicleta: Sinónimo de grafo bipartito completo o subgrafo bipartito completo; véase completo .
biconectado: Generalmente es sinónimo de $2-$ vértice-conexo , pero a veces incluye K ₂ aunque no sea 2-conexo. Véase conectado ; para componentes biconexas , véase componente .
número de enlace: La menor proporción 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 aquel cuyos vértices pueden dividirse en dos conjuntos disjuntos, de manera que los vértices de un conjunto no estén conectados entre sí, pero sí con los vértices del otro. Dicho de otro modo, un grafo bipartito es un grafo sin ciclos impares; equivalentemente, es un grafo que puede colorearse correctamente con dos colores. Los grafos bipartitos suelen representarse como $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, es posible que no tenga una única coloración con dos colores.
biregular: Un grafo birregular es un grafo 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 maximal que puede ser un vértice aislado, una arista puente o un subgrafo 2-conexo. Si un bloque es 2-conexo, cada par de vértices que lo componen pertenece a un ciclo común. Cada arista de un grafo pertenece a un único 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 conecta 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 de bloques (o punto de corte de bloques) de un grafo $G$ es un grafo bipartito donde un conjunto de particiones consta de los vértices de corte de $G$ , y el otro tiene un vértice $b_{i}$ para cada bloque $B_{i}$ de $G.$ Cuando $G$ está conectado, su grafo de puntos de corte de bloques es un árbol.; 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 todo 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 grafo, para el cual ningún subconjunto propio tiene la misma propiedad.
libro: 1. Un libro , grafo de libro o libro triangular es un grafo tripartito completo $K$ $1,1,$ $n$ ; una colección de $n$ triángulos unidos por una arista común.; 2. Otro tipo de grafo, también llamado libro o libro cuadrilátero, es una colección de $4$ ciclos unidos por una arista común; el producto cartesiano de una estrella con una arista.; 3. Una incrustación de libro es una incrustación de un grafo en un libro topológico, un espacio formado al unir un conjunto de semiplanos a lo largo de una línea común. Por lo general, se requiere que los vértices de la incrustación estén sobre la línea, que se denomina columna vertebral de la incrustación, y que las aristas de la incrustación se encuentren dentro de un único semiplano, una de las páginas del libro.
límite: 1. En una incrustación de grafos , un recorrido de frontera es el subgrafo que contiene todos los bordes y vértices incidentes a una cara .
zarza: Un zarzal es una colección de subgrafos conectados que se tocan entre sí. Dos subgrafos se tocan si comparten un vértice o si cada uno incluye un extremo de una arista. El orden de un zarzal es el tamaño mínimo 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 zarzals.
rama: Un camino de vértices de grado dos, que termina en vértices cuyo grado es distinto de dos. ^{[ 7 ]}
descomposición de ramas: Una descomposición en ramas de $G$ es una agrupación jerárquica de las aristas de $G$ , representada por un árbol binario sin raíz cuyas hojas están etiquetadas por las aristas de $G.$ El ancho de una descomposición en ramas es el máximo, sobre las aristas $e$ de este árbol binario, del número de vértices compartidos entre los subgrafos determinados por las aristas 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 ramas de $G.$
ancho de rama: Ver descomposición en ramas .
puente: 1. Un puente , istmo o arista de corte es una arista cuya eliminación desconectaría el grafo. Un grafo sin puentes es aquel que no tiene puentes; equivalentemente, un grafo conexo por 2 aristas.; 2. Un puente de un subgrafo H es un subgrafo conexo maximal separado del resto del grafo por H. Es decir, es un subgrafo maximal disjunto de H por aristas y en el que cada par de vértices y aristas pertenecen a un camino disjunto internamente de 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 planar de su grafo.; 3. Un puente de ciclo también puede referirse a 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 esos mismos dos vértices. Un grafo puenteado es un grafo en el que cada ciclo de cuatro o más vértices tiene un puente.
sin puente: Un grafo sin puentes o sin istmos es un grafo que no tiene aristas de puente (es decir, istmos); es decir, cada componente conexa es un grafo conexo por 2 aristas .
mariposa: 1. El grafo 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 relacionada con los ciclos conectados por cubos .

do

do: $C n$ es un grafo cíclico $de n$ vértices; véase ciclo .
cactus: Un grafo cactus , árbol cactus o árbol 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, se denomina cactus navideño.
jaula: Una jaula es un grafo regular con el orden más pequeño 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 se conocen como invariantes canónicos o invariantes completos, y a veces se definen únicamente para los grafos de una familia particular. La canonización de grafos es el proceso de calcular una forma canónica.
tarjeta: Un grafo formado a partir de un grafo dado mediante la eliminación de un vértice, especialmente en el contexto de la conjetura de reconstrucción . Véase también mazo , el multiconjunto de todas las cartas de un grafo.
ancho de tallado: El concepto de anchura de grafo es una noción de anchura de grafo análoga a la anchura de rama, pero utilizando agrupaciones jerárquicas de vértices en lugar de agrupaciones jerárquicas de aristas.
oruga: Un árbol oruga o simplemente oruga es un árbol en el que los nodos internos forman un camino.
centro: El centro de un grafo es el conjunto de vértices de mínima excentricidad .
centroide: El centroide de un árbol es un vértice $v$ tal que, si se enraíza 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 cadena , es decir, un conjunto de vértices o un conjunto de aristas.
Cheeger constante: Ver expansión .
cereza: Una cereza es un camino con 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ático 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 una arista saliente, es decir, una arista que se dirige en dirección opuesta a la raíz.
acorde
cordal: 1. Una cuerda de un ciclo es una arista que no pertenece al ciclo, cuyos dos extremos pertenecen al ciclo.; 2. Un grafo cordal es un grafo en el que cada ciclo de cuatro o más vértices tiene una cuerda, por lo que los únicos ciclos inducidos son triángulos.; 3. Un grafo fuertemente cordal es un grafo cordal en el que cada ciclo de longitud seis o más tiene una cuerda impar.; 4. Un grafo bipartito cordal no es cordal (a menos que sea un bosque); es un 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 ciclos de 4 vértices.; 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 un conjunto de cuerdas se llama gráfico de círculo .
cromático: Relacionado con la coloración; véase color . La teoría cromática de grafos 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 en una coloración propia de $G$ . $χ'(G)$ es el índice cromático de $G$ , el número mínimo de colores necesarios en una coloración propia de aristas de $G$ .
seleccionable
capacidad de elección: Un grafo es $k$ -elegible si tiene una coloración por lista siempre que cada vértice tenga una lista de $k$ colores disponibles. La elegibilidad del grafo es el menor valor de $k$ 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 referirse a una ruta cerrada o a un elemento del espacio de ciclos (un subgrafo generador euleriano). El rango de circuito de un grafo es la dimensión de su espacio de ciclos.
circunferencia: La circunferencia de una gráfica es la longitud de su ciclo simple más largo. La gráfica es hamiltoniana 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 (generalmente infinita) de grafos, a menudo definida como aquellos que poseen alguna propiedad específica. Se utiliza el término "clase" en lugar de "conjunto" porque, a menos que se impongan restricciones especiales (como restringir los vértices a un conjunto particular y definir las aristas como conjuntos de dos vértices), las clases de grafos no suelen ser conjuntos cuando se formalizan mediante la teoría de conjuntos.; 2. Una clase de color de un grafo 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 en 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 garras 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 dicho conjunto). A veces, una camarilla se define como un conjunto maximal de vértices mutuamente adyacentes (o subgrafo completo maximal), que no forma parte de ningún conjunto (o subgrafo) mayor de este tipo. 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 camarillas de un grafo G es el grafo de intersección de las camarillas maximales en G. Véase también biclique , un subgrafo bipartito completo.
árbol de camarilla: Un sinónimo de gráfico de bloques .
ancho de la camarilla: El ancho de clique 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, añaden 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 clique como máximo $2$ son exactamente los cografos .
cerrado: 1. Un vecindario cerrado es aquel que incluye su vértice central; véase vecindario .; 2. Un camino cerrado es aquel que comienza y termina en el mismo vértice; véase camino .; 3. Un grafo es transitivamente cerrado si es igual a su propio cierre transitivo; véase transitivo .; 4. Una propiedad de grafo es cerrada bajo alguna operación sobre grafos si, siempre que el argumento o los argumentos de la operación tengan dicha propiedad, entonces el resultado también la tiene. Por ejemplo, las propiedades hereditarias son cerradas bajo subgrafos inducidos; las propiedades monótonas son cerradas bajo subgrafos; y las propiedades cerradas bajo menores son cerradas bajo menores.
cierre: 1. Para el cierre transitivo de un grafo 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 consiste en 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; un cocolorado es un coloreado en el que cada vértice induce un conjunto independiente (como en el coloreado propio) o una camarilla (como en el coloreado del complemento).
color
colorante: 1. La coloración de un grafo consiste en etiquetar los vértices de un grafo mediante elementos de un conjunto de colores determinado, o, equivalentemente, en particionar los vértices en subconjuntos, denominados "clases de color", cada uno de los cuales está asociado a uno de los colores.; 2. Algunos autores utilizan el término «coloración», sin especificar cuál, para referirse a una coloración propiamente dicha, que asigna colores distintos a los extremos de cada arista. En la coloración de grafos, el objetivo es encontrar una coloración propia que utilice la menor cantidad de colores posible; por ejemplo, los grafos bipartitos son aquellos cuyas coloraciones se pueden realizar con solo dos colores, y el teorema de los cuatro colores establece que todo grafo planar puede colorearse con un máximo de cuatro colores. Se dice que un grafo está $k$ -coloreado si se ha coloreado (propiamente) con $k$ colores, y $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 las aristas de manera que no haya dos aristas con el mismo punto final que compartan un color), la coloración de listas (coloración propia donde cada vértice está restringido a un subconjunto de los colores disponibles), la coloración acíclica (cada subgrafo de 2 colores es acíclico), la cocoloració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 grafo es uno más la degeneración . Se denomina así porque al aplicar un algoritmo de coloración voraz a un ordenamiento degenerado del grafo se utilizan como máximo esta cantidad de colores.
gráfico de desplazamientos: Un grafo conmutativo de un grupo o, más generalmente, de un semigrupo , es un grafo no dirigido en el que los vértices son elementos del grupo/semigrupo y existe una arista entre cualquier par de elementos que conmutan (es decir, existe una arista entre los vértices $x$ e y $si$ y solo si $xy = yx$ ).
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 dicho orden parcial. De forma equivalente, un grafo de comparabilidad es un grafo con orientación transitiva. Muchas otras clases de grafos pueden definirse como grafos de comparabilidad de tipos especiales de orden parcial.
complementar: La gráfica complementaria ${\bar {G}}$ 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 son adyacentes en $G.$
completo: 1. Un grafo completo es aquel en el que cada par de vértices son adyacentes: todas las aristas que podrían existir están presentes. Un grafo completo con $n$ vértices se suele denotar $K$ $n$ . Un grafo bipartito completo es aquel en el que cada par de 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 suele denotar $K$ $a$ $,$ $b$ . La misma terminología y notación también se ha extendido a los 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 subconjuntos diferentes son adyacentes; si el número de vértices en los subconjuntos es $a$ $,$ $b$ $,$ $c$ $, ...$ entonces este grafo se denota $K$ $a$ $,$ $b$ $,$ $c$ $, ...$ .; 2. Una completación de un grafo dado es un supergrafo que posee alguna propiedad deseada. Por ejemplo, una completación cordal es un supergrafo que es un grafo cordal.; 3. Un emparejamiento completo es sinónimo de un emparejamiento perfecto ; véase emparejamiento .; 4. Una coloración completa es aquella en la que cada par de colores se utiliza para los extremos 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 grafo es sinónimo de una forma canónica, un invariante que tiene valores diferentes para grafos no isomorfos.
componente: Un componente conexo de un grafo es un subgrafo conexo maximal. El término también se utiliza para subgrafos maximales o subconjuntos de vértices de un grafo que tienen un orden de conectividad superior, incluyendo componentes biconexos , triconexos y fuertemente conexos .
condensación: La condensación de un grafo dirigido $G$ es un grafo dirigido acíclico con un vértice por cada componente fuertemente conexa 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 grafo que contiene un vértice universal .
conectar: Causa de estar conectado .
conectado: Un grafo conexo es aquel en el que cada par de vértices forma los extremos de un camino. Las formas superiores de conectividad incluyen la conectividad fuerte en grafos dirigidos (para cada dos vértices existen caminos de uno al otro en ambas direcciones), los grafos con $k$ vértices conectados (eliminar menos de $k$ vértices no desconecta el grafo) y los grafos $con k$ aristas conectadas (eliminar menos de $k$ aristas no desconecta 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 fusionando 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 necesariamente están conectados por una arista. La contracción de caminos se produce cuando el conjunto de aristas de un camino se contraen para formar una sola arista entre los extremos del camino. La operación inversa a la contracción de aristas es la división de vértices.
conversar: El grafo recíproco es sinónimo del grafo transpuesto; véase transposición .
centro: 1. Un $k$ -núcleo es el subgrafo inducido formado al eliminar todos los vértices de grado menor que $k$ , y todos los vértices cuyo grado se vuelve menor que $k$ después de eliminaciones anteriores. Véase degeneración .; 2. Un núcleo es un grafo $G$ tal que todo homomorfismo de grafos de $G$ a sí mismo es un isomorfismo.; 3. El núcleo de un grafo $G$ es un grafo mínimo $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 , formada como la unión de todos los emparejamientos máximos.
cotree: 1. El complemento de un árbol de expansión .; 2. Una estructura de árbol enraizada utilizada para describir un cografo , en la que cada vértice del cografo es una hoja del árbol, cada nodo interno del árbol está etiquetado con 0 o 1, y dos vértices del cografo son adyacentes si y solo si su ancestro común más bajo en el árbol está etiquetado con 1.
cubrir: Una cobertura de vértices es un conjunto de vértices incidentes a cada arista de un grafo. Una cobertura de aristas es un conjunto de aristas incidentes a cada vértice de un grafo. Un conjunto de subgrafos de un grafo cubre dicho grafo si su unión —considerando tanto los vértices como las aristas— es igual al grafo.
crítico: Un grafo crítico para una propiedad dada es un grafo que posee dicha propiedad, pero cuyo subgrafo formado al eliminar un solo vértice carece de ella. Por ejemplo, un grafo crítico factorial es aquel que tiene un emparejamiento perfecto (un 1-factor) para cada eliminación de vértice, pero (debido a que tiene un número impar de vértices) no posee un emparejamiento perfecto en sí mismo. Compárese con el término hipo- , utilizado para grafos que no poseen una propiedad, pero para los cuales la eliminación de un solo vértice sí la posee.
cubo
cúbico: 1. Grafo cúbico , el grafo de ocho vértices que representa los vértices y las aristas de un cubo.; 2. Grafo hipercubo , una generalización de mayor dimensión del grafo cúbico.; 3. Grafo de cubo plegado , formado a partir de un hipercubo mediante la adición de vértices opuestos que se conectan entre sí.; 4. Gráfico de cubo dividido por la mitad , la mitad del cuadrado de un gráfico de hipercubo.; 5. Cubo parcial , un subgrafo de un hipercubo que conserva la distancia.; 6. El cubo de un grafo $G$ es la potencia del grafo $G$ $3$ .; 7. Grafo cúbico , otro nombre para un grafo $3-$ regular, en el que cada vértice tiene tres aristas incidentes.; 8. Ciclos conectados por cubos , un grafo cúbico formado al reemplazar cada vértice de un hipercubo por un ciclo.
cortar
juego de cortes: 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 este conjunto no está vacío. Se dice que una arista abarca la partición si tiene extremos 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 cortado: El espacio de corte de un grafo es un espacio vectorial GF (2) que tiene como elementos el conjunto de corte s del grafo y como operación de suma vectorial la diferencia simétrica de conjuntos.
ciclo: 1. Un ciclo puede ser un tipo de grafo o un tipo de camino . Como camino, puede ser un camino cerrado (también llamado recorrido ) o, más comúnmente, un camino cerrado sin vértices repetidos y, por consiguiente, sin aristas (también llamado ciclo simple). En este último caso, generalmente se considera un grafo, es decir, la elección del primer vértice y la dirección generalmente se consideran irrelevantes; es decir, las permutaciones cíclicas y las inversiones del camino producen el mismo ciclo. Los tipos especiales importantes de ciclo incluyen los ciclos hamiltonianos , los ciclos inducidos , los ciclos periféricos y el ciclo más corto, que define la circunferencia de un grafo. Un $k$ -ciclo es un ciclo de longitud $k$ ; por ejemplo, un $2$ -ciclo es un digon y un $3$ -ciclo es un triángulo. Un grafo cíclico es un grafo que es en sí mismo un ciclo simple; un grafo cíclico con $n$ vértices se denota comúnmente como $C$ $n$ .; 2. El espacio cíclico es un espacio vectorial generado por los ciclos simples en un grafo, a menudo sobre el campo de 2 elementos, pero también sobre otros campos.

D

TROZO DE CUERO: Abreviatura de grafo dirigido acíclico , un grafo dirigido sin ciclos dirigidos.
cubierta: El multiconjunto de grafos formado a partir de un único grafo $G$ eliminando un único vértice de todas las maneras posibles, especialmente en el contexto de la conjetura de reconstrucción . Un mazo de aristas se forma de la misma manera eliminando una única arista de todas las maneras posibles. Los grafos de un mazo también se denominan cartas . Véase también crítico (grafos que poseen una propiedad que no está presente en ninguna carta) e hipo- (grafos que no poseen una propiedad que está presente en todas las cartas).
descomposición: Consulte descomposición en árbol , descomposición en ruta o descomposición en ramas .
degenerar
degeneración: Un grafo $k$ -degenerado es un grafo no dirigido en el que cada subgrafo inducido tiene un grado mínimo de como máximo $k$ . La degeneración de un grafo es el menor $k$ para el cual es $k$ -degenerado. Un ordenamiento de degeneración es un ordenamiento de los vértices tal que cada vértice tiene un grado mínimo en su subgrafo inducido y en todos los vértices posteriores; en un ordenamiento de 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 enlace k, 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 el número de aristas incidentes. ^[²^] 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 denomina 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 del apretón de manos es un número par. La secuencia de grados es la colección de grados de todos los vértices, ordenados de mayor a menor. En un 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. El grado de homomorfismo de un grafo es sinónimo de su número de Hadwiger , el orden del menor de clique más grande.
Δ , δ: $Δ (G)$ (usando la letra griega delta) es el grado máximo de un vértice en $G$ , y $δ (G)$ es el grado mínimo; ver grado .
densidad: En un grafo de n nodos, la densidad es la razón entre el número de aristas del grafo y el número de aristas en 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 de cualquiera de sus nodos adyacentes es 1. Es el nivel de un nodo menos uno. Sin embargo, cabe señalar que algunos autores utilizan el término «profundidad» como sinónimo de « nivel de un nodo». ^{[ 9 ]}
diámetro: El diámetro de un grafo conexo es la longitud máxima del camino más corto . Es decir, es la máxima de las distancias entre pares de vértices del grafo. Si el grafo tiene pesos en sus aristas, su diámetro ponderado mide la longitud del camino mediante la suma de los pesos de las aristas a lo largo del camino, mientras que el diámetro no ponderado la mide mediante el número de aristas. Para grafos desconectados, las definiciones varían: el diámetro puede definirse como infinito, como el diámetro mayor de un componente conexo o puede ser indefinido.
diamante: El grafo diamante es un grafo no dirigido con cuatro vértices y cinco aristas.
desconectado: Fuertemente conectado .(No confundir con desconectado )
digon: Un digon es un ciclo simple de longitud dos en un grafo dirigido o un multigrafo. Los digons no pueden aparecer en grafos simples no dirigidos, ya que requieren repetir la misma arista dos veces, lo que viola la definición de simple .
dígrafo: Sinónimo de grafo dirigido . ^{[ 2 ]}
dipath: Ver ruta indicada .
predecesor directo: La cola de una arista dirigida cuyo extremo es el vértice dado.
sucesor directo: La cabeza de una arista dirigida cuya cola es el vértice dado.
dirigido: Un grafo dirigido es aquel en el que las aristas tienen una dirección definida, de un vértice a otro. ^{[ 2 ]} En un grafo mixto , una arista dirigida es también aquella que tiene una dirección definida; 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: Un camino en el que todas las aristas tienen la misma dirección . Si un camino dirigido va del vértice $x$ al vértice $y$ , $x$ es un predecesor de $y$ , $y$ es un sucesor de $x$ , y se dice que $y es$ alcanzable desde $x$ .
dirección: 1. La relación asimétrica entre dos vértices adyacentes en un grafo , representada como una flecha .; 2. La relación asimétrica entre dos vértices en un camino dirigido .
desconectar: Causa de desconexión .
desconectado: No conectado .
desarticular: 1. Dos subgrafos son disjuntos por aristas si no comparten ninguna arista, y disjuntos por vértices si no comparten ningún vértice.; 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 de un grafo es la longitud del camino más corto que tiene esos 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 cobertura de vértices, un conjunto de vértices incidente a todas las aristas del grafo. Entre los tipos especiales importantes de conjuntos dominantes se incluyen los conjuntos dominantes independientes (conjuntos dominantes que también son conjuntos independientes) y los conjuntos dominantes conexos (conjuntos dominantes que inducen subgrafos conexos). Un conjunto dominante de un solo vértice también puede denominarse 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 grafo dual de un grafo plano $G$ es un grafo que tiene un vértice por cada cara de $G.$

mi

mi: $E (G)$ es el conjunto de aristas de $G$ ; véase conjunto de aristas .
oreja: Una oreja de un grafo es un camino cuyos extremos pueden coincidir, pero en el que no hay repeticiones de vértices ni de aristas.
descomposición del oído: Una descomposición en orejas es una partición de las aristas de un grafo en una secuencia de orejas, cuyos extremos (después de la primera) pertenecen a una oreja anterior y cuyos puntos interiores no pertenecen a ninguna. Una oreja abierta es un camino simple (una oreja sin vértices repetidos), y una descomposición en orejas abiertas es aquella en la que cada oreja posterior a la primera es abierta; un grafo tiene una descomposición en orejas abiertas si y solo si es biconexo. Una oreja es impar si tiene un número impar de aristas, y una descomposición en orejas impares es aquella en la que cada oreja es impar; un grafo tiene una descomposición en orejas impares si y solo si es crítico con respecto a un factor.
excentricidad: La excentricidad de un vértice es la distancia máxima que lo separa de 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 hipergrafos, más) vértices a los que está unida, llamados sus extremos. Las aristas pueden ser dirigidas o no dirigidas; las aristas no dirigidas también se llaman líneas y las aristas dirigidas también se llaman 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: Un conjunto de aristas cuya eliminación desconecta el grafo . Un corte de una arista se denomina puente , istmo o arista de corte .
conjunto de bordes: El conjunto de aristas de un grafo dado $G$ , a veces denotado por $E (G)$ .
gráfico sin bordes: Un grafo sin aristas o totalmente desconectado sobre un conjunto dado de vértices es aquel que no tiene aristas. A veces se le denomina grafo vacío, pero este término también puede referirse a un grafo sin vértices.
incrustación: Una incrustación de grafos es una representación topológica de un grafo como un subconjunto de un espacio topológico, donde cada vértice se representa como un punto, cada arista como una curva cuyos extremos coinciden con los extremos de la curva, y no existen otras intersecciones entre vértices o aristas. Un grafo planar es aquel que tiene dicha incrustación en el plano euclidiano, y un grafo toroidal es aquel que tiene dicha incrustación en un toro. El género de un grafo es el género mínimo posible de una variedad bidimensional en la que puede incrustarse.
gráfico vacío: 1. Un grafo sin aristas sobre un conjunto no vacío de vértices.; 2. El grafo de orden cero , un grafo sin vértices ni aristas.
fin: Un extremo de un grafo infinito es una clase de equivalencia de rayos, donde dos rayos son equivalentes si existe 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 camino, sendero o senda. El primer extremo de una arista dirigida dada se llama cola y el segundo extremo se llama cabeza .
enumeración: La enumeración de grafos consiste en contar los grafos de una clase determinada, en función de su orden. En términos más generales, los problemas de enumeración pueden referirse tanto al conteo de una clase específica de objetos combinatorios (como camarillas, conjuntos independientes, coloraciones o árboles de expansión) como a la enumeración algorítmica de todos estos 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 posee un circuito euleriano. Para un grafo no dirigido, esto significa que el grafo es conexo y cada vértice tiene grado par. Para un grafo dirigido, esto significa que el grafo es fuertemente conexo y cada vértice tiene grado de entrada igual a grado de salida. En algunos casos, el requisito de conectividad se flexibiliza, y un grafo que solo cumple con los requisitos de grado se denomina euleriano.
incluso: Divisible por dos; por ejemplo, un ciclo par es un ciclo cuya longitud es par.
expansor: Un grafo expansor es un grafo cuya expansión de aristas, expansión de vértices o expansión espectral está acotada lejos de cero.
expansión: 1. La expansión de aristas, número isoperimétrico o constante de Cheeger de un grafo $G$ es la razó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 razón mínima, sobre subconjuntos $S$ de como máximo la mitad de los vértices de $G$ , del número de vértices fuera pero adyacentes a $S$ al número de vértices en $S.$; 3. La expansión de vecinos únicos de un grafo $G$ es la razó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 único vértice 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 menores $r$ -poco profundos tienen una razó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 , una cara es un componente conexo del subconjunto del plano o superficie de la incrustación que no está unido al grafo. Para una incrustación en el plano, todas las caras, excepto una, estarán acotadas; la cara excepcional que se extiende hasta el infinito se denomina cara exterior (o infinita).
factor: Un factor de un grafo es un subgrafo generador: un subgrafo que incluye todos los vértices del grafo. El término se usa principalmente en el contexto de subgrafos regulares: un $k$ -factor es un factor $k$ -regular. En particular, un $1-$ factor es lo mismo que un emparejamiento perfecto. Un grafo crítico de factor es un grafo para el cual la eliminación de cualquier vértice produce un grafo con un $1-$ factor.
factorización: Una factorización de grafos consiste en dividir las aristas del grafo en factores; una $k-$ factorización consiste en dividirlas en $k$ -factores. Por ejemplo, una $1-$ factorización es una coloración de aristas con la propiedad adicional de que cada vértice es incidente a una arista 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 asumen que todos los grafos son finitos sin mencionarlo 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, infinitas aristas o ambas cosas.
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. Se distingue 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 conexo del subgrafo inducido formado al eliminar $X.$ El término "flap" se usa comúnmente en el contexto de los 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 mismo.
prohibido: Una caracterización de grafos prohibidos es aquella que define a una familia de grafos como aquellos que no tienen otros grafos como subgrafos, subgrafos inducidos o menores. Si $H$ es uno de los grafos que no aparece como subgrafo, subgrafo inducido o menor, entonces se dice que $H$ es prohibido.
gráfico de forzamiento: Un grafo forzante es un grafo $H$ tal que evaluar la densidad de subgrafos de $H$ en los grafos de una secuencia de grafos $G(n)$ es suficiente para comprobar si esa secuencia es cuasialeatoria .
bosque: Un bosque es un grafo no dirigido sin ciclos (una unión disjunta de árboles sin raíz), o un grafo dirigido formado como una unión disjunta de árboles con raíz.
borde libre: Un borde que no está en una coincidencia .
vértice libre: 1. Un vértice que no está en una arista coincidente en una coincidencia; 2. Un vértice que no ha sido emparejado.
Frucht: 1. Robert Frucht; 2. El grafo de Frucht , uno de los dos grafos cúbicos más pequeños sin simetrías no triviales.; 3. El teorema de Frucht que establece que todo grupo finito es el grupo de simetrías de un grafo finito.
lleno: Sinónimo de inducido .
grafo funcional: Un grafo funcional es un grafo dirigido donde cada vértice tiene grado de salida uno. De forma equivalente, un grafo funcional es un pseudobosque dirigido maximal.

GRAMO

GRAMO: Una variable que se usa frecuentemente para representar un gráfico.
género: El género de un grafo es el género mínimo de una superficie sobre la cual se puede incrustar; véase incrustación .
geodésico: Como sustantivo, geodésica es sinónimo de camino más corto . Cuando se usa como adjetivo, significa relacionado con los caminos más cortos o con 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: El objeto fundamental de estudio en la teoría de grafos es un sistema de vértices conectados de dos en dos por aristas. A menudo se subdivide en grafos dirigidos o 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 grafo es una coloración que se obtiene al considerar los vértices en una secuencia determinada y asignar a cada vértice el primer color disponible.
Grötzsch: 1. Herbert Grötzsch; 2. El grafo de Grötzsch , el grafo más pequeño sin triángulos que requiere cuatro colores en cualquier coloración adecuada.; 3. El teorema de Grötzsch que establece que los grafos planares libres de triángulos siempre se pueden colorear con como máximo tres colores.
Número Grundy: 1. El número de Grundy de un grafo es el número máximo de colores producidos por una coloración voraz , con un ordenamiento de vértices mal elegido.

H

H: Una variable que se usa a menudo para denotar un gráfico, especialmente cuando otro gráfico ya ha sido denotado por $G.$
coloración H: Una $H$ -coloración 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 triángulo-libres son los grafos que no tienen un grafo triángulo como subgrafo. La propiedad de ser $H$ -libre es siempre hereditaria. Un grafo es $H$ -menor-libre 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 le conoce como 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 ciclo hamiltoniano es un camino o ciclo generador simple: recorre 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 a cada conjunto $X$ con menos de $k$ vértices una de sus solapas, a menudo satisfaciendo condiciones de consistencia adicionales. El orden de un haven es el número $k$ . Los havens se pueden usar para caracterizar la anchura 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 con raíz 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 con raíces es la altura de su raíz. Es decir, la altura de un árbol es el número de aristas en el camino más largo posible, que parte de la raíz y termina en una hoja.; 3. La altura de un grafo dirigido acíclico es la longitud máxima de un camino dirigido en este grafo.
hereditario: Una propiedad hereditaria de los grafos es una propiedad que es cerrada bajo subgrafos inducidos: si $G$ tiene una propiedad hereditaria, entonces también la tendrá todo subgrafo inducido de $G.$ Compárese con monótono (cerrado bajo todos los subgrafos) o cerrado bajo menores (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 complemento. Esta terminología se usa principalmente en el contexto de los grafos perfectos, que se caracterizan por el teorema del grafo perfecto fuerte como aquellos grafos sin agujeros impares ni 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.
homomorfismo: 1. Un homomorfismo de grafos es una función que asigna vértices adyacentes entre sí, partiendo del conjunto de vértices de un grafo y del conjunto de vértices de otro. Este tipo de función es la más utilizada en los enfoques de la teoría de grafos basados en categorías. Una coloración de grafos adecuada puede describirse, de forma equivalente, como un homomorfismo a un grafo completo.; 2. El grado de homomorfismo de un grafo es sinónimo de su número de Hadwiger , el orden del menor de clique más grande.
hiperarco: Un hiperborde dirigido que tiene un origen y un destino definidos.
hiperborde: Una arista en un hipergrafo , que tiene cualquier número de extremos, en contraste con el requisito de que las aristas de los grafos tengan exactamente dos extremos.
hipercubo: Un grafo hipercubo es un grafo formado a partir de los vértices y las aristas de un hipercubo geométrico .
hipergrafo: Un hipergrafo es una generalización de un grafo en la que cada arista (llamada hiperarista en este contexto) puede tener más de dos extremos.
hipo-: Este prefijo, en combinación con una propiedad del grafo, indica un grafo que no posee dicha propiedad, pero en el que cada subgrafo formado al eliminar un único vértice sí la posee. Por ejemplo, un grafo hipohamiltoniano es aquel que no tiene un ciclo hamiltoniano, pero en el que la eliminación de un único vértice produce un subgrafo hamiltoniano. Compárese con el prefijo crítico , utilizado para grafos que poseen una propiedad, pero en los que la eliminación de un único vértice no produce un subgrafo hamiltoniano. ^{[ 11 ]}

I

grado de entrada: El número de aristas entrantes en un grafo dirigido; véase grado .
incidencia: Una incidencia en un grafo es un par vértice-arista tal que el vértice es un extremo de la arista.
matriz de incidencia: La matriz de incidencia de un grafo es una matriz cuyas filas están indexadas por los vértices del grafo y cuyas columnas están indexadas por las aristas, con un uno en la celda correspondiente a 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: (Adjetivo) La relación entre una arista y uno de sus extremos. ^{[ 2 ]}
incomparabilidad: Un grafo de incomparabilidad es el complemento de un grafo de comparabilidad ; véase comparabilidad .
independiente: 1. Un conjunto independiente es un conjunto de vértices que induce un subgrafo sin aristas. También puede llamarse 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 propio o gráfico de intervalo unitario; véase propio .
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 cuyos extremos se encuentran dentro de dicho subconjunto. Entre los casos especiales se incluyen los caminos inducidos y los ciclos inducidos , que son subgrafos inducidos que son caminos o ciclos.
inductivo: Sinónimo de degenerado .
infinito: Un grafo infinito es aquel que no es finito; véase 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 grafos es su subgrafo común más grande, el grafo formado por los vértices y las aristas que pertenecen a ambos grafos.; 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. Se pueden definir varias clases de grafos como 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 intervalos (grafos de intersección de intervalos de una línea), grafos de líneas (grafos de intersección de las aristas de un grafo) y grafos de cliques (grafos de intersección de las cliques máximas de un grafo). Todo 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 intervalos es un gráfico de intersección de intervalos de una línea .; 2. El intervalo $[$ $u$ $,$ $v$ $]$ en un grafo es la unión de todos los caminos más cortos desde $u$ hasta $v$ .; 3. El grosor del intervalo es sinónimo de ancho de trayectoria .
invariante: Sinónimo de propiedad .
flecha invertida: Una flecha con dirección opuesta a otra flecha. La flecha $(y, x)$ es la flecha invertida de la flecha $(x, y)$ .
aislado: Un vértice aislado de un 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; véase isomorfismo .
isomorfismo: Un isomorfismo de grafos es una correspondencia biunívoca que preserva la incidencia entre los vértices y las aristas de un grafo y los vértices y las 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 una arista cuya eliminación desconecta el grafo.

J

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

K

K: Para la notación de grafos completos, grafos bipartitos completos y grafos multipartitos completos, consulte completo .
κ: $κ (G)$ (usando la letra griega kappa) puede referirse a laconectividad de vérticesdeG $o$ al número de clique de $G.$
núcleo: El núcleo de un grafo dirigido es un conjunto de vértices que es a la vez estable y absorbente .
nudo: Una sección ineludible de un grafo dirigido . Véase nudo (matemáticas) y teoría de nudos .

L

L: $L (G)$ es la gráfica de línea de $G$ ; ver línea .
etiqueta: 1. Información asociada a un vértice o arista de un grafo. Un grafo etiquetado es aquel cuyos vértices o aristas tienen etiquetas. Los términos « vertices etiquetados» o «aristas etiquetadas» pueden utilizarse para especificar qué objetos de un grafo tienen etiquetas. El etiquetado de grafos se refiere a diversos problemas relacionados con la asignación de etiquetas a grafos sujetos a ciertas restricciones. Véase también «coloración de grafos» , donde 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 lograr estableciendo una correspondencia biunívoca entre los vértices y los números enteros del 1 al orden del grafo. Cuando los vértices están etiquetados, los grafos isomorfos entre sí (pero con diferentes ordenamientos de vértices) se cuentan como objetos separados. Por el contrario, cuando los vértices no están etiquetados, los grafos isomorfos entre sí no se cuentan por separado.
hoja: 1. Un vértice hoja o vértice colgante (especialmente en un árbol) es un vértice cuyo grado es $1.$ Una arista hoja o arista colgante es la arista que conecta un vértice 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 cuyas aristas conectan hojas cuya distancia en el árbol es como máximo un umbral dado.
longitud: En un grafo no ponderado, la longitud de un ciclo, camino o recorrido es igual al número de aristas que utiliza. En un grafo ponderado, puede ser la suma de los pesos de las aristas que utiliza. La longitud se usa para definir el camino más corto , la circunferencia (longitud del ciclo más corto) y el camino más largo entre dos vértices en un grafo.
nivel: 1. Esta es la profundidad de un nodo más 1, aunque algunos ^[¹²^] 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 el camino 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. Un conjunto de todos los nodos que tienen el mismo nivel o profundidad. ^[¹²^]
línea: Un sinónimo de arista no dirigida. El grafo de líneas $L (G)$ de un grafo $G$ es un grafo con un vértice por cada arista de $G$ y una arista por 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 grafos que se utiliza en algoritmos de grafos.; 2. La coloración por listas es una variación de la coloración de grafos en la que cada vértice tiene una lista de colores disponibles.
local: Una propiedad local de un grafo es aquella que está determinada únicamente por los vecindarios de los vértices que lo componen. Por ejemplo, un grafo es localmente finito si todos sus vecindarios son finitos.
bucle: Un bucle o auto-bucle es una arista cuyos extremos coinciden en el mismo vértice. Forma un ciclo de longitud $1.$ Estos bucles no están permitidos en grafos simples.

METRO

aumento: Sinónimo de expansión de vértice .
pareo: Un emparejamiento es un conjunto de aristas en el que ninguna comparte ningún vértice. Un vértice está emparejado o saturado si es uno de los extremos de una arista en el emparejamiento. Un emparejamiento perfecto o completo es aquel que empareja todos los vértices; también se le puede llamar 1-factor y solo puede existir cuando el orden es par. Un emparejamiento casi perfecto, en un grafo con orden impar, es aquel que satura todos los vértices excepto uno. Un emparejamiento máximo es aquel 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 maximal es aquel al que no se le pueden añadir aristas adicionales.
máximo: 1. Un subgrafo de un grafo $G$ dado es maximal para una propiedad particular si posee dicha propiedad, pero ningún otro supergrafo de G que también sea subgrafo de $G$ posee la misma propiedad. Es decir, es un elemento maximal de los subgrafos que poseen la propiedad. Por ejemplo, una camarilla maximal es un subgrafo completo que no puede expandirse a un subgrafo completo mayor. El término "maximal" debe distinguirse de "máximo": un subgrafo maximal siempre es maximal, pero no necesariamente a la inversa.; 2. Un grafo simple con una propiedad dada es maximal para esa propiedad si no es posible añadirle más aristas (manteniendo el conjunto de vértices inalterado) conservando tanto la simplicidad del grafo como la propiedad. Así, por ejemplo, un grafo planar maximal es un grafo planar tal que añadirle más aristas lo convertiría en un grafo no planar.
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 que poseen 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 una terna de vértices, un vértice que pertenece a los caminos más cortos entre todos los pares de vértices, especialmente en grafos medianos y grafos modulares .; 2. Un grafo mediano es un grafo en el que cada tres vértices tienen 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 dicha propiedad, pero ningún otro subgrafo propio del mismo posee también la misma propiedad. Es decir, es un elemento mínimo de los subgrafos que poseen la propiedad.
corte mínimo: Un corte cuyo conjunto de cortes tiene un peso total mínimo, posiblemente restringido a cortes que separan un par de vértices designados; se caracterizan por el teorema del flujo máximo y el corte mínimo .
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 bajo menores si es cerrada bajo menores; el teorema de Robertson-Seymour caracteriza a las familias cerradas bajo menores como poseedoras de un conjunto finito de menores prohibidos .
mezclado: Un grafo mixto es un grafo que puede incluir tanto aristas dirigidas como no dirigidas.
modular: 1. Grafo modular , un grafo en el que cada triplete de vértices tiene al menos un vértice mediano que pertenece a los caminos más cortos entre todos los pares del triplete.; 2. Descomposición modular , una descomposición de un grafo en subgrafos dentro de los cuales todos los vértices se conectan al resto del grafo de la misma manera.; 3. Modularidad de un agrupamiento de grafos, la diferencia entre el número de aristas entre clústeres y su valor esperado.
monótono: Una propiedad monótona de los grafos es una propiedad que es cerrada bajo subgrafos: si $G$ tiene una propiedad monótona, entonces también la tendrá cada subgrafo de $G.$ Compárese con hereditaria (cerrada bajo subgrafos inducidos) o cerrada bajo menores (cerrada bajo menores).
Gráfico de Moore: Un grafo de Moore es un grafo regular que cumple exactamente con la cota de Moore. La cota 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); un grafo que no tiene por qué ser simple.
adyacencia múltiple: Una adyacencia múltiple o arista múltiple es un conjunto de más de una arista que tienen los mismos extremos (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 barrios abiertos y cerrados, véase barrio .; 2. A menudo se utiliza una $n$ minúscula (especialmente en informática) para denotar el número de vértices en un grafo dado.
vecino
vecino: Un vértice que es adyacente a un vértice dado.
vecindario
vecindario: El entorno abierto (o simplemente entorno) 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$ se puede denotar como $N G (v)$ o $N (v)$ , y el entorno cerrado como $N G [v]$ o $N [v]$ . Cuando no se especifica si un entorno es abierto o cerrado, se asume que lo es.
red: Un grafo en el que se asocian atributos (por ejemplo, nombres) a los nodos y/o aristas.
nodo: Un sinónimo de vértice .
no borde: Un no-arista o anti-arista es un par de vértices que no son adyacentes; las aristas del grafo complementario.
gráfico nulo: Ver gráfico vacío .

O

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. Según 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 un camino simple o un ciclo simple con un número impar de aristas, utilizado en descomposiciones de orejas impares de grafos críticos de factores; véase oreja .; 4. Una cuerda impar es una arista que conecta dos vértices que están a 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 por 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 vecindario .; 2. Ver paseo .
orden: 1. El orden de un grafo $G$ es el número de sus vértices, $|$ $V$ $($ $G$ $)|$ . La variable $n$ se usa frecuentemente para esta cantidad. Véase también tamaño , el número de aristas.; 2. Un tipo de lógica de grafos ; véase primer orden y segundo orden .; 3. Un orden o ordenamiento de un grafo es una disposición de sus vértices en una secuencia, especialmente en el contexto del ordenamiento topológico (un ordenamiento de un grafo dirigido acíclico en el que cada arista va de un vértice anterior a un vértice posterior en el ordenamiento) y el ordenamiento de degeneración (un ordenamiento en el que cada vértice tiene un grado mínimo en el subgrafo inducido de él y de 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 consiste en asignar direcciones a sus aristas, convirtiéndolo en un grafo dirigido. Un grafo orientado es aquel al que se le ha asignado una orientación. Por ejemplo, un poliárbol es un árbol orientado; se diferencia de un árbol dirigido (una arborescencia) en que no se requiere consistencia en las direcciones de sus aristas. Otros tipos especiales de orientación incluyen torneos , orientaciones de grafos completos; orientaciones fuertes , orientaciones fuertemente conectadas; orientaciones acíclicas , orientaciones que no son cíclicas; orientaciones eulerianas , orientaciones que son eulerianas; y orientaciones transitivas , orientaciones transitivamente cerradas.; 2. Grafo orientado, utilizado por algunos autores como sinónimo de grafo dirigido .
grado de salida: Ver grado .
exterior: Mira la cara .
plano exterior: Un grafo planar exterior es un grafo que puede incrustarse en el plano (sin cruces) de manera que todos los vértices se encuentren en la cara exterior del grafo.

PAG

padre: En un árbol con raíz, el padre de un vértice $v$ es un vecino de $v$ a lo largo de la arista entrante, la que está dirigida hacia la raíz.
camino: Según la fuente, un camino puede ser un recorrido o un recorrido sin vértices repetidos y, por consiguiente, sin aristas (también llamado camino simple). Entre los casos especiales importantes se incluyen los caminos inducidos y los caminos más cortos .
descomposición de ruta: Una descomposición en caminos de un grafo $G$ es una descomposición en árbol cuyo árbol subyacente es un camino. Su ancho se define de la misma manera que para las descomposiciones en árbol, como uno menos que el tamaño de la bolsa más grande. El ancho mínimo de cualquier descomposición en caminos de G $es$ el ancho de camino de $G.$
ancho de trayectoria: El ancho de camino de un grafo $G$ es el ancho mínimo de una descomposición de camino de $G.$ También puede definirse en términos del número de clique de una completación de intervalo de $G.$ Siempre se encuentra entre el ancho de banda y el ancho de árbol de $G.$ También se 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 aquel 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 precisamente los grafos sin agujeros ni antiagujeros impares.; 2. Un grafo perfectamente ordenable es aquel cuyos vértices pueden ordenarse de tal manera que un algoritmo de coloración voraz con dicho ordenamiento colorea de forma óptima cada subgrafo inducido. Los grafos perfectamente ordenables son una subclase de los grafos perfectos.; 3. Un emparejamiento perfecto es un emparejamiento que satura todos los vértices; véase emparejamiento .; 4. Una 1-factorización perfecta es una partición de las aristas de un grafo en emparejamientos perfectos de tal manera que cada dos emparejamientos formen un ciclo hamiltoniano.
periférico: 1. Un ciclo periférico o ciclo no separable 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, este debe ser una hoja.
Petersen: 1. Julius Petersen (1839–1910), teórico de grafos danés.; 2. El grafo de Petersen , un grafo de 10 vértices y 15 aristas que se utiliza frecuentemente como contraejemplo.; 3. El teorema de Petersen que establece que todo grafo cúbico sin puentes tiene un emparejamiento perfecto.
planar: Un grafo planar es aquel que tiene una incrustación en el plano euclidiano. Un grafo plano es un grafo planar para el cual ya se ha fijado una incrustación particular. Un grafo $k$ -planar es aquel que puede dibujarse en el plano con como máximo $k$ cruces por arista.
árbol poligonal: Un poliárbol es un árbol orientado; equivalentemente, un grafo dirigido acíclico cuyo grafo subyacente no dirigido es un árbol.
fuerza: 1. Una potencia de grafo $G$ $k$ de un grafo $G$ es otro grafo sobre el mismo conjunto de vértices; dos vértices son adyacentes en $G$ $k$ cuando su distancia en $G es como máximo$ $k$ . Una potencia de hoja es un concepto estrechamente relacionado, derivado de una potencia de á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, bicliques y estrellas dentro de la red.; 3. Las leyes de potencia en las distribuciones de grado de las redes libres de escala son un fenómeno en el que el número de vértices de un grado dado es proporcional a una potencia del grado.
predecesor: Un vértice que precede a un vértice dado en una ruta dirigida .
principal: 1. Un grafo primo se define a partir de un grupo algebraico , con un vértice para cada número primo que divide el orden del grupo.; 2. En la teoría de la descomposición modular , un grafo primo es un grafo sin módulos no triviales.; 3. En la teoría de las divisiones , un grafo primo es aquel que no tiene divisiones, es decir, aquel cuyo conjunto de cortes es un grafo bipartito completo. Todo grafo cociente de una descomposición máxima por divisiones es un grafo primo, una estrella o un grafo completo.; 4. Un grafo primo para el producto cartesiano de grafos es un grafo conexo que no es a su vez un producto. Todo grafo conexo puede factorizarse de forma única en un producto cartesiano de grafos primos.
adecuado: 1. Un subgrafo propio es un subgrafo que elimina al menos un vértice o una arista con respecto al grafo completo; para grafos finitos, los subgrafos propios nunca son isomorfos al grafo completo, pero para grafos infinitos sí pueden serlo.; 2. Una coloración adecuada es una asignación de colores a los vértices de un grafo (una coloración) que asigna diferentes colores a los extremos de cada arista; véase color .; 3. Un grafo de intervalos propio o un grafo de arcos circulares propio es un grafo de intersección de un conjunto de intervalos o arcos circulares (respectivamente) tal que ningún intervalo o arco contiene a otro intervalo o arco. Los grafos de intervalos propios también se denominan grafos de intervalos unitarios (porque siempre se pueden representar mediante intervalos unitarios) o grafos de indiferencia.
propiedad: Una propiedad de un grafo es algo que puede ser cierto para algunos grafos y falso para otros, y que depende únicamente de la estructura del grafo y no de información incidental como las etiquetas. Las propiedades de los grafos pueden describirse de forma equivalente en términos de clases de grafos (los grafos que poseen una propiedad dada). De manera más general, una propiedad de un grafo también puede ser una función de los grafos que, de nuevo, es 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 grafo no dirigido en el que cada componente conexa tiene como máximo un ciclo, o un grafo dirigido en el que cada vértice tiene como máximo una arista saliente.
pseudografo: Un pseudografo es un grafo o multigrafo que permite bucles.

Q

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

R

radio: El radio de un grafo 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, de tal manera que el segundo autovalor más grande de su matriz de adyacencia es como máximo $2{\sqrt {d-1}}$ .
rayo: En un grafo infinito, un rayo es un camino simple infinito con un único extremo. Los extremos de un grafo son clases de equivalencia de rayos.
accesibilidad: La capacidad de ir de un vértice a otro dentro de un grafo .
accesible: Tiene alcanzabilidad afirmativa . Se dice que un vértice $y$ es alcanzable desde un vértice $x$ si existe un camino de $x$ a $y$ .
reconocible: En el contexto de la conjetura de reconstrucción , una propiedad de un grafo es reconocible si su veracidad puede determinarse a partir del conjunto de propiedades del grafo. Se sabe que muchas propiedades de los grafos son reconocibles. Si la conjetura de reconstrucción es verdadera, todas las propiedades de los grafos son reconocibles.
reconstrucción: La conjetura de reconstrucción afirma que cada grafo no dirigido $G$ está determinado de forma única por su conjunto de grafos, un multiconjunto formado al eliminar un vértice de $G$ de todas las maneras posibles. En este contexto, la reconstrucción es la formación de un grafo a partir de su conjunto de grafos.
rectángulo: Un ciclo simple que consta de exactamente 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 $d$ .
torneo regular: Un torneo regular es aquel 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 grafo, particularmente en árboles dirigidos y grafos 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 solo si tienen una distancia como máximo $k$ en la raíz.

S

saturado: Ver coincidencias .
número de búsqueda: El número de búsqueda de nodos es sinónimo de ancho de ruta .
segundo orden: La lógica de segundo orden de 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. Se distingue 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 sinónimo de ancho de camino .
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$ .
vértice simplicial: Un vértice simplicial es un vértice cuyo vecindario cerrado forma una camarilla .
simple: 1. Un grafo simple es aquel que no tiene bucles ni adyacencias múltiples. Es decir, cada arista conecta dos extremos distintos y no hay dos aristas con los mismos extremos. Una arista simple es aquella que no forma parte de una adyacencia múltiple. En muchos casos, se asume 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, por consiguiente, no tiene aristas repetidas.
hundir: En un grafo dirigido, un sumidero es un vértice sin aristas salientes (grado de salida 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 usa frecuentemente 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 grafo en el que la mayoría de los nodos no son vecinos entre sí, pero se puede llegar a la mayoría de ellos desde cualquier otro nodo con un número reducido de saltos o pasos. Específicamente, una red de mundo pequeño se define como un grafo donde la distancia típica L entre dos nodos elegidos al azar (el número de pasos necesarios) crece proporcionalmente al logaritmo del número de nodos N en la red ^{[ 14 ].}
sarcasmo: Un snark es un grafo cúbico simple, conectado y sin puentes con un índice cromático igual a 4.
fuente: En un grafo dirigido, una fuente es un vértice sin aristas entrantes (grado de entrada igual a 0).
espacio: En la teoría algebraica de grafos , se pueden asociar varios espacios vectoriales sobre el cuerpo binario a un grafo. Cada espacio vectorial tiene conjuntos de aristas o vértices como vectores, y la diferencia simétrica de conjuntos como 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 cortes es un subespacio del espacio de aristas que tiene como elementos los conjuntos de cortes del grafo. El espacio de ciclos tiene como elementos los subgrafos generadores eulerianos.
llave: Un grafo de expansión es un grafo (generalmente disperso) cuyas distancias de camino más corto se aproximan a las de un grafo denso u otro espacio métrico. Entre las variantes se incluyen los grafos de expansión geométricos , cuyos vértices son puntos en un espacio geométrico; los grafos de expansión de árbol , que son árboles de expansión de un grafo cuyas distancias se aproximan a las del grafo original; y los grafos de expansión, que son subgrafos dispersos de un grafo denso cuyas distancias se aproximan a las del grafo original. Un grafo de expansión voraz es un grafo de expansión construido mediante un algoritmo voraz, generalmente uno que considera todas las aristas desde la más corta hasta la más larga y conserva las necesarias para mantener 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 (subgrafos generadores que son árboles) y los emparejamientos perfectos (subgrafos generadores que son emparejamientos). Un subgrafo generador también puede denominarse factor , especialmente (aunque no exclusivamente) 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, esta misma propiedad también debería cumplirse 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 espectros para analizar grafos. Véase también expansión espectral .
dividir: 1. Un grafo dividido es un grafo cuyos vértices pueden particionarse en una camarilla y un conjunto independiente. Una clase relacionada de grafos, los grafos doblemente divididos, se utilizan en la demostración del teorema del grafo perfecto fuerte.; 2. Una partición de un grafo arbitrario consiste en dividir sus vértices en dos subconjuntos no vacíos, de modo que las aristas que forman este corte constituyen un subgrafo bipartito completo. Las particiones de un grafo se pueden representar mediante una estructura de árbol denominada descomposición en particiones . Una partición se denomina fuerte cuando no está cruzada por ninguna otra. Una partición se denomina no trivial cuando ambos lados tienen más de un vértice. Un grafo se denomina primo cuando no tiene particiones 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, de modo que estos dos nuevos vértices son adyacentes a los vértices adyacentes al vértice original. La operación inversa a 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²$ $;$ en sentido contrario, $G$ es la raíz cuadrada de $G²$ . El semicasqueño de un grafo bipartito es el subgrafo de su cuadrado inducido por un lado de la bipartición.; 2. Un grafo cuadrado es un grafo planar que se puede dibujar de manera que todas las caras acotadas sean ciclos de grado 4 y todos los vértices de grado ≤ 3 pertenezcan a la cara exterior.; 3. Un grafo de cuadrícula cuadrada es un grafo reticular definido a partir de puntos en el plano con coordenadas enteras conectados 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 denomina garra.
fortaleza: La fuerza de un grafo es la relación mínima entre el número de aristas eliminadas del grafo y los componentes creados, considerando todas las eliminaciones posibles; es análoga a la robustez, basada en la eliminación de vértices.
fuerte: 1. Para la conectividad fuerte y los componentes fuertemente conectados de los grafos dirigidos, consulte conectado y componente . Una orientación fuerte es una orientación que está fuertemente conectada; consulte orientación .; 2. Para el teorema del grafo perfecto fuerte , véase perfecto .; 3. Un grafo fuertemente regular es un grafo 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 aquel en el que cada subgrafo inducido tiene un conjunto independiente que satisface todas las camarillas máximas. 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 aristas de $G.$ El subconjunto de vértices debe incluir todos los extremos del subconjunto de aristas, pero también puede incluir vértices adicionales. Un subgrafo generador es aquel que incluye todos los vértices del grafo; un subgrafo inducido es aquel que incluye todas las aristas cuyos extremos pertenecen al subconjunto de vértices.
subárbol: Un subárbol es un subgrafo conexo de un árbol. En ocasiones, para árboles con raíz, los subárboles se definen como un tipo especial de subgrafo conexo, formado por todos los vértices y aristas alcanzables desde un vértice elegido.
sucesor: Un vértice que viene después de un vértice dado en un camino dirigido .
superconcentrador: Un superconcentrador es un grafo con dos subconjuntos de vértices designados e iguales, $I$ y $O$ , de tal manera que para cada par de subconjuntos iguales $S$ de $I$ y $T$ de $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 dirigido acíclico, con $I$ como sus fuentes y $O$ como sus sumideros.
supergrafo: Un grafo formado al agregar vértices, aristas o ambos a un grafo dado. Si $H$ es un subgrafo de $G$ , entonces $G$ es un supergrafo de $H.$

T

theta: 1. Un grafo theta es la unión de tres caminos disjuntos internamente (simples) que tienen los mismos dos vértices extremos distintos. ^[¹⁵^]; 2. La gráfica theta de un conjunto de puntos en el plano euclidiano se construye creando un sistema de conos que rodean cada punto y añadiendo una arista por cono al punto cuya proyección sobre un rayo central del cono sea la más pequeña.; 3. El número de Lovász o la función theta de Lovász de un grafo es un invariante del grafo 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 grafo de Thomsen es un nombre para el grafo bipartito completo. $K_{3,3}$ .
topológico: 1. Un grafo topológico es una representación de los vértices y aristas de un grafo mediante puntos y curvas en el plano (sin que necesariamente se eviten los cruces).; 2. La teoría topológica de grafos es el estudio de las incrustaciones de grafos.; 3. La ordenación topológica es el problema algorítmico de ordenar un grafo dirigido acíclico 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 sendero cerrado es un recorrido que comienza y termina en el mismo vértice y no tiene aristas repetidas. Los recorridos eulerianos son recorridos que utilizan todas las aristas del grafo; véase Euleriano .
torneo: Un torneo es una orientación de un grafo completo; es decir, es un grafo dirigido tal que cada dos vértices están conectados por exactamente una arista dirigida (que va en una sola de las dos direcciones entre los dos vértices).
rastreable: Un grafo trazable es un grafo que contiene una trayectoria hamiltoniana.
camino: Un paseo sin bordes repetidos.
transitivo: Relacionado con la propiedad transitiva . El cierre transitivo de un grafo dirigido dado es un grafo sobre 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 mínimo que tiene el mismo cierre transitivo; los grafos dirigidos acíclicos tienen una única reducción transitiva. Una orientación transitiva es una orientación de un grafo que es su propio cierre transitivo; existe solo para grafos de comparabilidad .
transponer: La transpuesta de un grafo dirigido dado es un grafo con los mismos vértices, pero con cada arista invertida en su dirección. También se le puede llamar recíproco o inverso del grafo.
árbol: 1. Un árbol es un grafo no dirigido que es a la vez conectado y acíclico, o un grafo dirigido en el que existe un único camino desde un vértice (la raíz del árbol) a todos los vértices restantes.; 2. Un $k$ -árbol es un grafo formado al unir $($ $k$ $+ 1)$ -clicas mediante $k$ -clicas compartidas. Un árbol en el sentido ordinario es un $1$ -árbol según esta definición.
descomposición de árboles: 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 de á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 en árbol de $G.$ También se puede definir en términos del número de clique de una completación cordal de $G$ , el orden de un refugio de $G$ o el orden de una zarza de $G.$
triángulo: Un ciclo de longitud tres en un grafo. Un grafo libre de triángulos es un grafo no dirigido que no tiene subgrafos triangulares.
trivial: Un grafo trivial es un grafo con 0 o 1 vértices. ^{[ 16 ]} Un grafo con 0 vértices también se denomina grafo nulo .
Turán: 1. Pál Turán; 2. Un grafo de Turán es un grafo multipartito completo y 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 cliques de un orden dado.; 4. El problema de la fábrica de ladrillos de Turán pide encontrar el número mínimo de cruces en un dibujo de un grafo bipartito completo.
mellizo: Dos vértices $u,v$ son gemelos verdaderos si tienen el mismo vecindario cerrado : $N G [u] = N G [v]$ (esto implica que $u$ y $v$ son vecinos), y son gemelos falsos si tienen el mismo vecindario abierto: $N G (u) = N G (v))$ (esto implica que $u$ y $v$ no son vecinos).

U

vértice unario: En un árbol con raíz, un vértice unario es un vértice que tiene exactamente un vértice hijo.
no dirigido: Un grafo no dirigido es aquel en el que los dos extremos de cada arista no se distinguen entre sí. Véase también grafos dirigidos y mixtos . En un grafo mixto , una arista no dirigida es aquella cuyos extremos no se distinguen entre sí.
uniforme: Un hipergrafo es $k$ -uniforme cuando todas sus aristas tienen $k$ extremos, 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 grafo universal es un grafo que contiene como subgrafos todos los grafos de una familia de grafos determinada, o todos los grafos de un tamaño u orden determinado dentro de una familia de grafos determinada.; 2. Un vértice universal (también llamado ápice o vértice dominante) es un vértice adyacente a todos los demás vértices del grafo. Por ejemplo, los grafos de rueda y los grafos de umbral conectados siempre tienen un vértice universal.; 3. En la lógica de los grafos , un vértice que se cuantifica universalmente en una fórmula puede llamarse vértice universal para esa fórmula.
gráfico no ponderado: Un grafo cuyos vértices y aristas no han sido ponderados ; lo opuesto a un grafo ponderado .
gráfico de utilidad: El grafo de utilidad es un nombre para el grafo bipartito completo. $K_{3,3}$ .

V

V: Ver conjunto de vértices .
valencia: Sinónimo de grado .
vértice: Un vértice (o 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: Un conjunto de vértices cuya eliminación desconecta el grafo . Un corte de un vértice se llama punto de articulación o vértice de corte .
conjunto de vértices: El conjunto de vértices de un grafo dado $G$ , a veces denotado por $V (G)$ .
vértices: Ver vértice .
Vizing: 1. Vadim G. Vizing; 2. El teorema de Vizing que establece que el índice cromático es como máximo uno más que el grado máximo.; 3. La conjetura de Vizing sobre el número de dominación de productos cartesianos de grafos.
volumen: La suma de los grados de un conjunto de vértices.

W

$W$: La letra $W$ se utiliza en la notación de gráficos de rueda y gráficos de molino de viento . Esta 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 los grafos planares por sus menores prohibidos.; 4. Teorema de Wagner que caracteriza los grafos libres de $K$ $5 menores.$
caminar: Un camino es una secuencia finita o infinita de aristas que une una secuencia de vértices . Los caminos también se denominan a veces cadenas . ^{[ 17 ]} Un camino es abierto si su primer y último vértice son distintos, y cerrado si se repiten.
débilmente conectado: Un grafo dirigido se denomina débilmente conexo si al reemplazar todas sus aristas dirigidas por aristas no dirigidas se obtiene un grafo conexo (no dirigido).
peso: Un valor numérico, asignado como etiqueta a un vértice o arista de un grafo. El peso de un subgrafo es la suma de los pesos de los vértices o aristas que lo componen.
gráfico ponderado: Un grafo cuyos vértices o aristas tienen pesos asignados . Un grafo ponderado por vértices tiene pesos en sus vértices y un grafo ponderado por aristas tiene pesos en sus aristas.
bien coloreado: Un gráfico bien coloreado es un gráfico cuyas coloraciones codiciosas utilizan la misma cantidad de colores.
bien cubierto: Un grafo bien cubierto es un grafo cuyos conjuntos independientes máximos tienen todos el mismo tamaño.
rueda: Un grafo rueda es un grafo formado al añadir un vértice universal a un ciclo simple.
ancho: 1. Sinónimo de degeneración .; 2. Para otros invariantes de grafos conocidos como ancho, consulte bandwidth , branchwidth , clique-width , pathwidth y treewidth .; 3. El ancho de una descomposición de árbol o 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 grafo acíclico dirigido es la cardinalidad máxima de una anticadena.
molino: Un grafo de molino de viento es la unión de un conjunto de camarillas, todas del mismo orden entre sí, con un vértice común que pertenece a todas las camarillas y todos los demás vértices y aristas distintos.

Véase también

Referencias

↑ Farber, M.; Hahn, G.; Hell, P .; Miller, DJ (1986), "Concerning the achromatic number of graphs", Journal of Combinatorial Theory, Series B , 40 (1): 21– 39, doi : 10.1016/0095-8956(86)90062-6.
1 2 3 4 5 6 7 8 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford ( 2001), "B.4 Grafos", 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 Grafos", Teoría de grafos , Textos de posgrado en matemáticas, vol. 173 (5.ª ed.), Berlín, Nueva York: Springer-Verlag, p. 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 grafo 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 grafo" , 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 correctamente coloreadas y arcoíris de grafos con pocas cerezas", Journal of Combinatorial Theory, Series 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 revisión , Monografías SIAM sobre matemáticas discretas y aplicaciones, págs. 105-121 , ISBN 978-0-89871-432-6
↑ Mitchem, John (1969), "Hipo-propiedades en grafos", The Many Facets of Graph Theory (Actas de la Conferencia, Western Mich. Univ., Kalamazoo, Mich., 1968) , Lecture Notes in Mathematics, vol. 110, Springer, pp. 223–230 , doi : 10.1007/BFb0060121 , ISBN 978-3-540-04629-5, MR 0253932 .
Nivel 1 2 , 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 (Actas de la Conferencia, Western Michigan Univ., Kalamazoo, Mich., 1972; dedicada 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, MR 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
↑ "Cadenas - teoría de grafos" , britannica.com , consultado el 25 de marzo de 2018

[1] Farber, M.; Hahn, G.; Hell, P .; Miller, DJ (1986), "Concerning the achromatic number of graphs", Journal of Combinatorial Theory, Series B , 40 (1): 21– 39, doi : 10.1016/0095-8956(86)90062-6.

[clrs-2] 1 2 3 4 5 6 7 8 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford ( 2001), "B.4 Grafos", Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw-Hill, págs. 1080–1084 .

[3] Grünbaum, B. (1973), "Coloraciones acíclicas de grafos planares", Israel Journal of Mathematics , 14 (4): 390– 408, doi : 10.1007/BF02764716.

[4] Cormen et al. (2001) , pág. 529.

[diestel-5] Diestel, Reinhard (2017), "1.1 Grafos", Teoría de grafos , Textos de posgrado en matemáticas, vol. 173 (5.ª ed.), Berlín, Nueva York: Springer-Verlag, p. 3, doi : 10.1007/978-3-662-53622-3 , ISBN 978-3-662-53621-6.

[6] Woodall, DR (1973), "El número de enlace de un grafo y su número de Anderson", J. Combin. Theory Ser. B , 15 (3): 225– 255, doi : 10.1016/0095-8956(73)90038-5

[7] van der Holst, Hein (marzo de 2009), "Un algoritmo de tiempo polinomial para encontrar una incrustación sin enlaces de un grafo" , Journal of Combinatorial Theory, Serie B , 99 (2), Elsevier BV: 512–530 , doi : 10.1016/j.jctb.2008.10.002

[8] Sudakov, Benny; Volec, Jan (2017), "Copias correctamente coloreadas y arcoíris de grafos con pocas cerezas", Journal of Combinatorial Theory, Series B , 122 (1): 391– 416, arXiv : 1504.06176 , doi : 10.1016/j.jctb.2016.07.001.

[9] profundidad , NIST

[10] Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), "Capítulo 7: Subgrafo prohibido", Clases de grafos: una revisión , Monografías SIAM sobre matemáticas discretas y aplicaciones, págs. 105-121 , ISBN 978-0-89871-432-6

[11] Mitchem, John (1969), "Hipo-propiedades en grafos", The Many Facets of Graph Theory (Actas de la Conferencia, Western Mich. Univ., Kalamazoo, Mich., 1968) , Lecture Notes in Mathematics, vol. 110, Springer, pp. 223–230 , doi : 10.1007/BFb0060121 , ISBN 978-3-540-04629-5, MR 0253932 .

[NIST_Level-12] Nivel 1 2 , NIST

[13] Harris, John M. (2000), Combinatoria y teoría de grafos , Nueva York: Springer-Verlag, pág. 5, ISBN 978-0-387-98736-1

[14] 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

[15] Bondy, JA (1972), "La "teoría de grafos" del alfabeto griego", Teoría de grafos y aplicaciones (Actas de la Conferencia, Western Michigan Univ., Kalamazoo, Mich., 1972; dedicada 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, MR 0335362

[16] 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

[17] "Cadenas - teoría de grafos" , britannica.com , consultado el 25 de marzo de 2018

[ 1 ]

[

[

[ 4 ]

[

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[

[ 13 ]

[ 14 ].

[

[ 16 ]

[ 17 ]

Símbolos

A

B

do

D

mi

F

GRAMO

H

I

J

K

L

METRO

norte

O

PAG

Q

R

S

T

U

V

W

Véase también

Referencias

Articulos relacionados