stringtranslate.com

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 en pares por líneas o aristas.

Símbolos

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

A

absorbente
Un conjunto absorbente de un grafo dirigido es un conjunto de vértices tales que para cualquier vértice de , existe una arista desde hacia un vértice de .
acromático
El número acromático de un grafo es el número máximo de colores en una coloración completa. [1]
acíclico
1. Un grafo es acíclico si no tiene ciclos. Un grafo acíclico no dirigido es lo mismo que un bosque . Un grafo dirigido acíclico, que es un dígrafo sin ciclos dirigidos, a menudo se denomina grafo acíclico dirigido , especialmente en informática. [2]
2. Una coloración acíclica de un gráfico no dirigido es una coloración adecuada en la que cada dos clases de color inducen un bosque. [3]
matriz de adyacencia
La matriz de adyacencia de un gráfico es una matriz cuyas filas y columnas están indexadas por los vértices del gráfico, con un uno en la celda para la fila i y la columna j cuando los vértices i y j son adyacentes, y un cero en caso contrario. [4]
adyacente
1. Relación entre dos vértices que son ambos extremos de la misma arista. [2]
2. La relación entre dos aristas distintas que comparten un vértice final. [5]
alfa
Para un grafo G , α ( G ) (usando la letra griega alpha) es su número de independencia (ver independiente), y α ′( G ) es su número correspondiente (ver correspondencia).
alterno
En un grafo con una coincidencia, una ruta alterna es una ruta cuyos bordes se alternan entre bordes coincidentes y no coincidentes. Un ciclo alternante es, de manera similar, un ciclo cuyos bordes se alternan entre bordes coincidentes y no coincidentes. Una ruta de aumento es una ruta alterna que comienza y termina en vértices no saturados. Una coincidencia mayor se puede encontrar como la diferencia simétrica de la ruta coincidente y la ruta de aumento; una coincidencia es máxima si y solo si no tiene una ruta de aumento.
anticadena
En un grafo acíclico dirigido , un subconjunto S de vértices que no son comparables entre sí, es decir, para ninguno de ellos en S , existe un camino dirigido de x a y o de y a x . Inspirado en la noción de anticadenas en conjuntos parcialmente ordenados .
anti-borde
Sinónimo de no arista , un par de vértices no adyacentes.
anti-triángulo
Un conjunto independiente de tres vértices, el complemento de un triángulo.
ápex
1. Un grafo de vértice es un grafo en el que se puede eliminar un vértice, dejando un subgrafo plano. El vértice eliminado se llama vértice. Un grafo de k -vértices es un grafo que se puede convertir en plano eliminando k vértices.
2. Sinónimo de vértice universal , un vértice adyacente a todos los demás vértices.
arborescencia
Sinónimo de árbol enraizado y dirigido; ver árbol.
arco
Ver borde.
flecha
Un par ordenado de vértices, como una arista en un grafo dirigido. Una flecha ( x , y ) tiene una cola x , una punta y y una dirección de x a y ; se dice que y es el sucesor directo de x y x el predecesor directo de y . La flecha ( y , x ) es la flecha invertida de la flecha ( x , y ) .
punto de articulación
Vértice de un grafo conexo cuya eliminación desconectaría el grafo. En términos más generales, 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 no tiene más de k hijos. Un árbol 1-ario es simplemente un camino. Un árbol 2-ario también se denomina árbol binario , aunque ese término se refiere más apropiadamente a árboles 2-arios en los que los hijos de cada nodo se distinguen como hijos izquierdos o derechos (con como máximo uno de cada tipo). Se dice que un árbol k -ario está completo si cada vértice interno tiene exactamente k hijos.
aumentando
Un tipo especial de trayectoria alternada; véase alternancia.
automorfismo
Un automorfismo de gráfico es una simetría de un gráfico, un isomorfismo del gráfico hacia sí mismo.

B

bolsa
Uno de los conjuntos de vértices en una descomposición de árbol.
equilibrado
Un gráfico bipartito o multipartito está equilibrado si cada dos subconjuntos de su partición de vértices tienen tamaños dentro de uno del otro.
ancho de banda
El ancho de banda de un grafo G es el mínimo, sobre todos los ordenamientos de vértices de G , de la longitud de la arista más larga (el número de pasos en el ordenamiento entre sus dos puntos finales). También es uno menos que el tamaño de la camarilla máxima en una completitud de intervalo adecuada de G , elegida para minimizar el tamaño de la camarilla.
biclicúlo
Sinónimo de gráfico bipartito completo o subgráfico bipartito completo; ver completo.
biconectado
Generalmente es sinónimo de 2 -conexo por vértice , pero a veces incluye K 2 aunque no esté 2-conexo. Véase conexo; para componentes biconexos , véase componente.
número de encuadernación
La relación más pequeña posible entre el número de vecinos de un subconjunto propio de vértices y el tamaño del subconjunto. [6]
bipartito
Un grafo bipartito es un grafo cuyos vértices se pueden dividir en dos conjuntos disjuntos de modo que los vértices de un conjunto no están conectados entre sí, pero pueden estar conectados a vértices del otro conjunto. Dicho de otra manera, un grafo bipartito es un grafo sin ciclos impares; equivalentemente, es un grafo que se puede colorear adecuadamente con dos colores. Los grafos bipartitos a menudo se escriben G = ( U , V , E ) donde U y V son los subconjuntos de vértices de cada color. Sin embargo, a menos que el grafo sea conexo, puede que no tenga una coloración única de 2 colores.
birregular
Un gráfico birregular es un gráfico bipartito en el que solo hay dos grados de vértice diferentes, uno para cada conjunto de la bipartición de vértices.
bloquear
1. Un bloque de un grafo G es un subgrafo maximalista que puede ser un vértice aislado, una arista de puente o un subgrafo biconexo. Si un bloque es biconexo, cada par de vértices que lo componen pertenece a un ciclo común. Cada arista de un grafo pertenece exactamente a un bloque.
2. El grafo de bloques de un grafo G es otro grafo cuyos vértices son los bloques de G , con una arista que une dos vértices cuando los bloques correspondientes comparten un punto de articulación; es decir, es el grafo de intersección de los bloques de G . El grafo de bloques de cualquier grafo es un bosque.
3. El grafo de bloques cortados (o de puntos de corte de bloques) de un grafo G es un grafo bipartito en el que un conjunto de partes consta de los vértices de corte de G y el otro tiene un vértice para cada bloque de G. Cuando G es conexo, su grafo de bloques cortados 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 cada grafo de bloques puede construirse como el grafo de bloques de un grafo.
vínculo
Un conjunto de corte mínimo: un conjunto de aristas cuya eliminación desconecta el gráfico, para el cual ningún subconjunto propio tiene la misma propiedad.
libro
1. Un libro , gráfico de libro o libro triangular es un gráfico tripartito completo K 1,1, n ; una colección de n triángulos unidos en un borde compartido.
2. Otro tipo de gráfico, también llamado libro o libro cuadrilátero, es una colección de 4 ciclos unidos por un borde compartido; el producto cartesiano de una estrella con un borde.
3. Una incrustación de libro es una incrustación de un gráfico en un libro topológico, un espacio formado mediante la unión de una colección de semiplanos a lo largo de una línea compartida. Por lo general, se requiere que los vértices de la incrustación estén en la línea, que se denomina el lomo de la incrustación, y que los bordes de la incrustación se encuentren dentro de un solo semiplano, una de las páginas del libro.
límite
1. En una incrustación de gráficos , un recorrido de límites es el subgráfico que contiene todos los bordes y vértices incidentes de una cara.
zarza
Una zarza es una colección de subgrafos conectados que se tocan entre sí, donde dos subgrafos se tocan si comparten un vértice o cada uno incluye un punto final de una arista. El orden de una zarza es el tamaño más pequeño de un conjunto de vértices que tiene una intersección no vacía con todos los subgrafos. El ancho de árbol de un grafo es el orden máximo de cualquiera de sus zarzas.
rama
Un camino de vértices de grado dos, que termina en vértices cuyo grado no es igual a dos. [7]
descomposición de ramas
Una descomposición en rama de G es una agrupación jerárquica de los bordes de G , representada por un árbol binario sin raíz con sus hojas etiquetadas por los bordes de G . El ancho de una descomposición en rama es el máximo, sobre los bordes e de este árbol binario, del número de vértices compartidos entre los subgrafos determinados por los bordes de G en los dos subárboles separados por e . El ancho de rama de G es el ancho mínimo de cualquier descomposición en rama de G .
Ancho de rama
Véase descomposición de ramas.
puente
1. Un puente , istmo o arista cortada es una arista cuya eliminación desconectaría el grafo. Un grafo sin puentes es aquel que no tiene puentes; equivalentemente, un grafo con dos aristas conectadas.
2. Un puente de un subgrafo H es un subgrafo maximal conexo separado del resto del grafo por H . Es decir, es un subgrafo maximal que es disjunto con H en sus aristas y en el que cada dos vértices y aristas pertenecen a un camino que es internamente disjunto con H . H puede ser un conjunto de vértices. Una cuerda es un puente de una arista. En la prueba de planaridad , H es un ciclo y un ciclo periférico es un ciclo con como máximo un puente; debe ser un límite de cara en cualquier incrustación plana de su grafo.
3. Un puente de un ciclo también puede significar un camino que conecta dos vértices de un ciclo pero que es más corto que cualquiera de los caminos del ciclo que conectan los mismos dos vértices. Un grafo con puente es un grafo en el que cada ciclo de cuatro o más vértices tiene un puente.
Sin puente
Un gráfico sin puentes o sin istmos es un gráfico que no tiene aristas de puente (es decir, istmos); es decir, cada componente conectado es un gráfico con 2 aristas conectadas .
mariposa
1. El gráfico de la mariposa tiene cinco vértices y seis aristas; está formado por dos triángulos que comparten un vértice.
2. La red mariposa es un grafo utilizado como arquitectura de red en computación distribuida, estrechamente relacionado con los ciclos cubo-conexos .

do

do
C n es un gráfico de ciclo de n vértices; ver ciclo.
cactus
Un grafo de cactus , árbol de cactus, cactus o árbol de Husimi es un grafo conexo en el que cada arista pertenece a un máximo de un ciclo. Sus bloques son ciclos o aristas simples. Si, además, cada vértice pertenece a dos bloques como máximo, entonces se denomina cactus de Navidad.
jaula
Una jaula es un grafo regular con el menor orden posible para su circunferencia.
canónico
canonización
Una forma canónica de un grafo es un invariante tal que dos grafos tienen invariantes iguales si y solo si son isomorfos. Las formas canónicas también pueden denominarse invariantes canónicos o invariantes completos, y a veces se definen solo para los grafos dentro de una familia particular de grafos. La canonización de grafos es el proceso de calcular una forma canónica.
tarjeta
Un gráfico formado a partir de un gráfico dado eliminando un vértice, especialmente en el contexto de la conjetura de reconstrucción . Véase también baraja, el conjunto múltiple de todas las cartas de un gráfico.
Ancho de tallado
El ancho de tallado es una noción de ancho de gráfico análoga al ancho de rama, pero que utiliza agrupaciones jerárquicas de vértices en lugar de agrupaciones jerárquicas de aristas.
oruga
Un árbol oruga u oruga es un árbol en el que los nodos internos inducen un camino.
centro
El centro de un gráfico es el conjunto de vértices de mínima excentricidad.
centroide
Un centroide de un árbol es un vértice v tal que si tiene su raíz en v , ningún otro vértice tiene un tamaño de subárbol mayor que la mitad del tamaño del árbol.
cadena
1. Sinónimo de caminar.
2. Al aplicar métodos de topología algebraica a grafos, un elemento de un complejo de cadenas , es decir, un conjunto de vértices o un conjunto de aristas.
Cheeger constante
Ver expansión.
cereza
Una cereza es un camino de tres vértices. [8]
χ
χ ( G ) (usando la letra griega chi) es el número cromático de G y χ  ′( G ) es su índice cromático; ver cromá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 un borde saliente, que se dirige lejos de la raíz.
acorde
acorde
1. Una cuerda de un ciclo es una arista que no pertenece al ciclo, para la cual ambos puntos finales pertenecen al ciclo.
2. Un grafo cordal es un grafo en el que cada ciclo de cuatro o más vértices tiene una cuerda, por lo que los únicos ciclos inducidos son triángulos.
3. Un grafo fuertemente cordal es un grafo cordal en el que cada ciclo de longitud seis o más tiene un acorde impar.
4. Un grafo bipartito cordal no es cordal (a menos que sea un bosque); es un grafo bipartito en el que cada ciclo de seis o más vértices tiene una cuerda, por lo que los únicos ciclos inducidos son 4-ciclos.
5. Una cuerda de un círculo es un segmento de línea que conecta dos puntos en el círculo; el gráfico de intersección de una colección de cuerdas se llama gráfico circular .
cromático
Que tiene que ver con la coloración; véase color. La teoría de grafos cromáticos es la teoría de la coloración de grafos. El número cromático χ ( G ) es el número mínimo de colores necesarios para una coloración adecuada de G . χ  ′( G ) es el índice cromático de G , el número mínimo de colores necesarios para una coloración adecuada de los bordes de G .
Elegible
Capacidad de elección
Un grafo es k -elegible si tiene una lista de colores siempre que cada vértice tenga una lista de k colores disponibles. La capacidad de elección del grafo es el k más pequeño para el cual es k -elegible.
círculo
Un gráfico circular es el gráfico de intersección de las cuerdas de un círculo.
circuito
Un circuito puede hacer referencia a un camino cerrado o a un elemento del espacio de ciclos (un subgrafo de expansión euleriano). El rango de circuito de un grafo es la dimensión de su espacio de ciclos.
circunferencia
La circunferencia de un grafo es la longitud de su ciclo simple más largo. El grafo es hamiltoniano si y solo si su circunferencia es igual a su orden.
clase
1. Una clase de grafos o familia de grafos es una colección (normalmente infinita) de grafos, que a menudo se define como los grafos que tienen alguna propiedad específica. Se utiliza la palabra "clase" en lugar de "conjunto" porque, a menos que se establezcan restricciones especiales (como restringir los vértices que se deben extraer de un conjunto particular y definir que las aristas sean conjuntos de dos vértices), las clases de grafos normalmente no son conjuntos cuando se formalizan utilizando la teoría de conjuntos.
2. Una clase de color de un gráfico coloreado es el conjunto de vértices o aristas que tienen un color particular.
3. En el contexto del teorema de Vizing , sobre la coloración de aristas de grafos simples, se dice que un grafo es de clase uno si su índice cromático es igual a su grado máximo, y de clase dos si su índice cromático es igual a uno más el grado. Según el teorema de Vizing, todos los grafos simples son de clase uno o de clase dos.
garra
Una garra es un árbol con un vértice interno y tres hojas, o equivalentemente el grafo bipartito completo K 1,3 . Un grafo sin garra es un grafo que no tiene un subgrafo inducido que sea una garra.
camarilla
Una camarilla es un conjunto de vértices mutuamente adyacentes (o el subgrafo completo inducido por ese conjunto). A veces, una camarilla se define como un conjunto máximo de vértices mutuamente adyacentes (o subgrafo completo máximo), uno que no es parte de ningún conjunto (o subgrafo) más grande. Una k -camarilla es una camarilla de orden k . El número de camarilla ω ( G ) de un grafo G es el orden de su camarilla más grande. El grafo de camarilla de un grafo G es el grafo de intersección de las camarillas máximas en G . Véase también biclique, un subgrafo bipartito completo.
árbol de camarilla
Un sinónimo de gráfico de bloques.
ancho de camarilla
El ancho de camarilla de un grafo G es el número mínimo de etiquetas distintas necesarias para construir G mediante operaciones que crean un vértice etiquetado, forman la unión disjunta de dos grafos etiquetados, agregan una arista que conecta todos los pares de vértices con etiquetas dadas o reetiquetan todos los vértices con una etiqueta dada. Los grafos con un ancho de camarilla de como máximo 2 son exactamente los cografos .
cerrado
1. Un vecindario cerrado es aquel que incluye su vértice central; ver vecindario.
2. Un paseo cerrado es aquel que empieza y termina en el mismo vértice; ver paseo.
3. Un gráfico es transitivamente cerrado si es igual a su propio cierre transitivo; ver transitivo.
4. Una propiedad de grafo está cerrada bajo alguna operación sobre grafos si, siempre que el argumento o los argumentos de la operación tienen la propiedad, entonces también la tiene el resultado. Por ejemplo, las propiedades hereditarias están cerradas bajo subgrafos inducidos; las propiedades monótonas están cerradas bajo subgrafos; y las propiedades menores cerradas están cerradas bajo menores.
cierre
1. Para el cierre transitivo de un gráfico dirigido, véase transitivo.
2. Un cierre de un grafo dirigido es un conjunto de vértices que no tienen aristas salientes hacia vértices fuera del cierre. Por ejemplo, un sumidero es un cierre de un vértice. El problema del cierre es el problema de encontrar un cierre de peso mínimo o máximo.
co-
Este prefijo tiene varios significados que generalmente involucran grafos complementarios . Por ejemplo, un cografo es un grafo producido por operaciones que incluyen complementación; una cocoloración es una coloración en la que cada vértice induce un conjunto independiente (como en la coloración propia) o una camarilla (como en una coloración del complemento).
color
colorante
1. La coloración de un gráfico es un etiquetado de los vértices de un gráfico mediante elementos de un conjunto dado de colores o, equivalentemente, una partición de los vértices en subconjuntos, llamados "clases de color", cada uno de los cuales está asociado con uno de los colores.
2. Algunos autores utilizan el término "coloración", sin ninguna calificación, para referirse a una coloración adecuada, que asigna colores diferentes a los puntos finales de cada arista. En la coloración de grafos, el objetivo es encontrar una coloración adecuada que utilice la menor cantidad posible de colores; por ejemplo, los grafos bipartitos son los grafos que tienen coloraciones con solo dos colores, y el teorema de los cuatro colores establece que todo grafo plano puede colorearse con un máximo de cuatro colores. Se dice que un grafo tiene k colores si ha sido coloreado (adecuadamente) con k colores, y que es k -coloreable o k -cromático si esto es posible.
3. Se han estudiado muchas variaciones de coloración, incluyendo la coloración de aristas (colorear aristas de modo que no haya dos aristas con el mismo punto final que compartan un color), la coloración de lista (coloración adecuada con cada vértice restringido a un subconjunto de los colores disponibles), la coloración acíclica (cada subgrafo de 2 colores es acíclico), la co-coloración (cada clase de color induce un conjunto independiente o una camarilla), la coloración completa (cada dos clases de color comparten una arista) y la coloración total (tanto las aristas como los vértices están coloreados).
4. El número de coloración de un gráfico es uno más la degeneración . Se llama así porque al aplicar un algoritmo de coloración voraz a un ordenamiento de degeneración del gráfico se utilizan como máximo esta cantidad de colores.
comparabilidad
Un grafo no dirigido es un grafo de comparabilidad si sus vértices son elementos de un conjunto parcialmente ordenado y dos vértices son adyacentes cuando son comparables en el orden parcial. De manera equivalente, un grafo de comparabilidad es un grafo que tiene una orientación transitiva. Muchas otras clases de grafos pueden definirse como grafos de comparabilidad de tipos especiales de orden parcial.
complementar
El grafo complementario de un grafo simple G es otro grafo en el mismo conjunto de vértices que G , con una arista por cada dos vértices que no sean adyacentes en G .
completo
1. Un grafo completo es aquel en el que cada dos vértices son adyacentes: todas las aristas que podrían existir están presentes. Un grafo completo con n vértices se denota a menudo K n . Un grafo bipartito completo es aquel en el que cada dos vértices en lados opuestos de la partición de vértices son adyacentes. Un grafo bipartito completo con a vértices en un lado de la partición y b vértices en el otro lado se denota a menudo K a , b . La misma terminología y notación también se ha extendido a grafos multipartitos completos , grafos en los que los vértices se dividen en más de dos subconjuntos y cada par de vértices en diferentes subconjuntos son adyacentes; si los números de vértices en los subconjuntos son a , b , c , ... entonces este grafo se denota K a , b , c , ... .
2. Una compleción de un grafo dado es un supergrafo que tiene alguna propiedad deseada. Por ejemplo, una compleción cordal es un supergrafo que es un grafo cordal.
3. Una coincidencia completa es sinónimo de una coincidencia perfecta ; ver coincidencia.
4. Una coloración completa es una coloración propia en la que cada par de colores se utiliza para los puntos finales de al menos una arista. Toda coloración con un número mínimo de colores es completa, pero pueden existir coloraciones completas con un número mayor de colores. El número acromático de un grafo es el número máximo de colores en una coloración completa.
5. Un invariante completo de un gráfico es sinónimo de una forma canónica, un invariante que tiene valores diferentes para gráficos no isomorfos.
componente
Un componente conexo de un grafo es un subgrafo conexo maximalista. El término también se utiliza para subgrafos maximalistas o subconjuntos de los vértices de un grafo que tienen un orden superior de conectividad, incluidos los componentes biconexos , los componentes triconexos y los componentes fuertemente conexos .
condensación
La condensación de un grafo dirigido G es un grafo acíclico dirigido con un vértice para cada componente fuertemente conectado de G y una arista que conecta pares de componentes que contienen los dos puntos finales de al menos una arista en G.
cono
Un gráfico que contiene un vértice universal .
conectar
Causa estar conectado.
conectado
Un grafo conexo es aquel en el que cada par de vértices forma los puntos finales de un camino. Las formas superiores de conectividad incluyen la conectividad fuerte en grafos dirigidos (para cada dos vértices hay caminos de uno al otro en ambas direcciones), grafos conexos por k vértices (eliminar menos de k vértices no puede desconectar el grafo) y grafos conexos por k aristas (eliminar menos de k aristas no puede desconectar el grafo).
componente conectado
Sinónimo de componente.
contracción
La contracción de aristas es una operación elemental que elimina una arista de un grafo mientras fusiona los dos vértices que unía previamente. La contracción de vértices (a veces llamada identificación de vértices) es similar, pero los dos vértices no están necesariamente conectados por una arista. La contracción de trayectoria ocurre en el conjunto de aristas de una trayectoria que se contraen para formar una única arista entre los puntos finales de la trayectoria. La operación inversa de la contracción de aristas es la división de vértices.
conversar
El gráfico inverso es un sinónimo del gráfico transpuesto; ver transposición.
centro
1. Un k -núcleo es el subgrafo inducido que se forma al eliminar todos los vértices de grado menor que k y todos los vértices cuyo grado se vuelve menor que k después de eliminaciones anteriores. Véase degeneración.
2. Un núcleo es un grafo G tal que todo homomorfismo de grafo de G a sí mismo es un isomorfismo.
3. El núcleo de un grafo G es un grafo minimal H tal que existen homomorfismos de G a H y viceversa. H es único salvo isomorfismo. Puede representarse como un subgrafo inducido de G y es un núcleo en el sentido de que todos sus autohomomorfismos son isomorfismos.
4. En la teoría de emparejamientos de grafos, el núcleo de un grafo es un aspecto de su descomposición de Dulmage-Mendelsohn , formado como la unión de todos los emparejamientos máximos.
co-árbol
1. El complemento de un árbol de expansión .
2. Una estructura de árbol con raíz utilizada para describir un cografo , en la que cada vértice del cografo es una hoja del árbol, cada nodo interno del árbol está etiquetado con 0 o 1, y dos vértices del cografo son adyacentes si y solo si su ancestro común más bajo en el árbol está etiquetado como 1.
cubrir
Una cobertura de vértices es un conjunto de vértices que inciden en cada arista de un grafo. Una cobertura de aristas es un conjunto de aristas que inciden en cada vértice de un grafo. Un conjunto de subgrafos de un grafo cubre ese grafo si su unión (tomada por vértices y por aristas) es igual al grafo.
crítico
Un grafo crítico para una propiedad dada es un grafo que tiene la propiedad pero de modo que cada subgrafo formado al eliminar un único vértice no tiene la propiedad. Por ejemplo, un grafo crítico en cuanto a factores es uno que tiene una correspondencia perfecta (un factor 1) para cada eliminación de vértice, pero (debido a que tiene un número impar de vértices) no tiene correspondencia perfecta en sí mismo. Compárese con hipo- , utilizado para grafos que no tienen una propiedad pero para los cuales cada eliminación de un vértice sí la tiene.
cubo
cúbico
1.   Gráfico cúbico , el gráfico de ocho vértices que consta de los vértices y las aristas de un cubo.
2.   Gráfico de hipercubo , una generalización de mayor dimensión del gráfico cúbico.
3.   Gráfico cúbico plegado , formado a partir de un hipercubo añadiendo vértices opuestos conectados.
4.   Gráfico cúbico reducido a la mitad , el medio cuadrado de un gráfico hipercubo.
5.   Cubo parcial , un subgrafo que preserva la distancia de un hipercubo.
6. El cubo de un grafo G es la potencia del grafo G 3 .
7.   Grafo cúbico , otro nombre para un gráfico 3 -regular, uno en el que cada vértice tiene tres aristas incidentes.
8.   Ciclos conexos con cubos , un gráfico cúbico formado al reemplazar cada vértice de un hipercubo por un ciclo.
cortar
conjunto de corte
Un corte es una partición de los vértices de un grafo en dos subconjuntos, o el conjunto (también conocido como conjunto de corte) de aristas que abarcan dicha partición, si ese conjunto no está vacío. Se dice que una arista abarca la partición si tiene puntos finales en ambos subconjuntos. Por lo tanto, la eliminación de un conjunto de corte de un grafo conexo lo desconecta.
punto de corte
Ver punto de articulación.
espacio de corte
El espacio de corte de un gráfico es un espacio vectorial GF (2) que tiene los conjuntos de corte del gráfico como sus elementos y la diferencia simétrica de conjuntos como su operación de adición vectorial.
ciclo
1. Un ciclo puede ser un tipo de grafo o un tipo de paseo. Como paseo puede ser un paseo cerrado (también llamado tour) o más usualmente un paseo cerrado sin vértices repetidos y en consecuencia aristas (también llamado ciclo simple). En el último caso usualmente se lo considera como un grafo, es decir, las elecciones del primer vértice y dirección usualmente se consideran poco importantes; esto es, las permutaciones cíclicas y las inversiones del paseo producen el mismo ciclo. Los tipos especiales importantes de ciclo incluyen ciclos hamiltonianos , ciclos inducidos , ciclos periféricos y el ciclo más corto, que define la circunferencia de un grafo. Un k -ciclo es un ciclo de longitud k ; por ejemplo, un 2 -ciclo es un dígono y un 3 -ciclo es un triángulo. Un grafo de ciclo es un grafo que es en sí mismo un ciclo simple; un grafo de ciclo con n vértices es comúnmente denotado C n .
2. El espacio de ciclos es un espacio vectorial generado por los ciclos simples en un gráfico, a menudo sobre el campo de 2 elementos pero también sobre otros campos.

D

TROZO DE CUERO
Abreviatura de gráfico acíclico dirigido , un gráfico dirigido sin ningún ciclo dirigido.
cubierta
El multiconjunto de grafos formado a partir de un único grafo G eliminando un único vértice de todas las formas posibles, especialmente en el contexto de la conjetura de reconstrucción . Una baraja de aristas se forma de la misma manera eliminando una única arista de todas las formas posibles. Los grafos de una baraja también se denominan cartas . Véase también crítico (grafos que tienen una propiedad que no se cumple en ninguna carta) e hipo- (grafos que no tienen una propiedad que se cumple en todas las cartas).
descomposición
Véase descomposición de árbol, descomposición de ruta o descomposición de rama.
degenerar
degeneración
Un grafo k -degenerado es un grafo no dirigido en el que cada subgrafo inducido tiene un grado mínimo como máximo de k . La degeneración de un grafo es el k más pequeño para el cual es k -degenerado. Un ordenamiento por degeneración es un ordenamiento de los vértices de modo que cada vértice tenga un grado mínimo en su subgrafo inducido y en todos los vértices posteriores; en un ordenamiento por degeneración de un grafo k -degenerado, cada vértice tiene como máximo k vecinos posteriores. La degeneración también se conoce como número de núcleo k , ancho y ligamiento, y uno más la degeneración también se denomina número de coloración o número de Szekeres-Wilf. Los grafos k -degenerados también se han denominado grafos k -inductivos.
grado
1. El grado de un vértice en un grafo es su número de aristas incidentes. [2] El grado de un grafo G (o su grado máximo) es el máximo de los grados de sus vértices, a menudo denotado Δ( G ) ; el grado mínimo de G es el mínimo de los grados de sus vértices, a menudo denotado δ ( G ) . El grado a veces se llama valencia ; el grado de v en G puede denotarse d G ( v ) , d ( G ) o deg( v ) . El grado total es la suma de los grados de todos los vértices; por el lema 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, en orden ordenado del mayor al menor. En un grafo dirigido, se puede distinguir el grado de entrada (número de aristas entrantes) y el grado de salida (número de aristas salientes). [2]
2. El grado de homomorfismo de un grafo es un sinónimo de su número de Hadwiger , el orden del menor de la 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 relación entre el número de aristas del grafo y el número de aristas de un grafo completo de n nodos. Véase grafo denso .
profundidad
La profundidad de un nodo en un árbol con raíz es el número de aristas en el camino desde la raíz hasta el nodo. Por ejemplo, la profundidad de la raíz es 0 y la profundidad de cualquiera de sus nodos adyacentes es 1. Es el nivel de un nodo menos uno. Sin embargo, hay que tener en cuenta que algunos autores utilizan la profundidad como sinónimo del nivel de un nodo. [9]
diámetro
El diámetro de un grafo conexo es la longitud máxima de un camino más corto . Es decir, es el máximo de las distancias entre pares de vértices en el grafo. Si el grafo tiene pesos en sus aristas, entonces su diámetro ponderado mide la longitud del camino por la suma de los pesos de las aristas a lo largo de un camino, mientras que el diámetro no ponderado mide la longitud del camino por el número de aristas. Para los grafos desconectados, las definiciones varían: el diámetro puede definirse como infinito, o como el diámetro más grande de un componente conexo, o puede ser indefinido.
diamante
El gráfico de diamante es un gráfico no dirigido con cuatro vértices y cinco aristas.
desconectado
Fuertemente conectado. (No confundir con desconectado)
Digón
Un dígono es un ciclo simple de longitud dos en un grafo dirigido o un multigrafo. Los dígonos no pueden aparecer en grafos simples no dirigidos, ya que requieren repetir la misma arista dos veces, lo que viola la definición de grafo simple .
dígrafo
Sinónimo de gráfico dirigido . [2]
dipath
Ver ruta dirigida.
predecesor directo
La cola de una arista dirigida cuya cabeza es el vértice dado.
sucesor directo
La cabeza de una arista dirigida cuya cola es el vértice dado.
Dirigido
Un gráfico dirigido es aquel en el que las aristas tienen una dirección diferenciada, de un vértice a otro. [2] En un gráfico mixto , una arista dirigida es a su vez aquella que tiene una dirección diferenciada; las aristas dirigidas también pueden denominarse arcos o flechas.
arco dirigido
Ver flecha.
borde dirigido
Ver flecha.
línea dirigida
Ver flecha.
camino dirigido
Camino en el que todas las aristas tienen la misma dirección. Si un camino dirigido va del vértice x al vértice y , x es predecesor de y , y es sucesor de x y se dice que y es alcanzable desde x .
dirección
1. La relación asimétrica entre dos vértices adyacentes en un gráfico, representada como una flecha.
2. La relación asimétrica entre dos vértices en una trayectoria dirigida.
desconectar
Provocar desconexión.
desconectado
No conectado.
desarticular
1. Dos subgrafos son disjuntos en aristas si no comparten aristas, y disjuntos en vértices si no comparten vértices.
2. La unión disjunta de dos o más grafos es un grafo cuyos conjuntos de vértices y aristas son las uniones disjuntas de los conjuntos correspondientes.
número de disociación
Un subconjunto de vértices en un grafo G se denomina disociación si induce un subgrafo con grado máximo 1.
distancia
La distancia entre dos vértices cualesquiera en un gráfico es la longitud del camino más corto que tiene los dos vértices como puntos finales.
domático
Una partición domática de un grafo es una partición de los vértices en conjuntos dominantes. El número domático del grafo es el número máximo de conjuntos dominantes en dicha partición.
dominante
Un conjunto dominante es un conjunto de vértices que incluye o es adyacente a cada vértice del grafo; no debe confundirse con una cubierta de vértices, un conjunto de vértices que es incidente en todas las aristas del grafo. Los tipos especiales importantes de conjuntos dominantes incluyen conjuntos dominantes independientes (conjuntos dominantes que también son conjuntos independientes) y conjuntos dominantes conexos (conjuntos dominantes que inducen subgrafos conexos). Un conjunto dominante de un solo vértice también puede llamarse vértice universal. El número de dominación de un grafo es el número de vértices en el conjunto dominante más pequeño.
dual
Un gráfico dual de un gráfico plano G es un gráfico que tiene un vértice para cada cara de G.

mi

mi
E ( G ) es el conjunto de aristas de G ; ver conjunto de aristas.
oreja
Una oreja de un grafo es un camino cuyos puntos finales pueden coincidir pero en el que por lo demás no hay repeticiones de vértices o aristas.
descomposición de la oreja
Una descomposición en orejas es una partición de los bordes de un grafo en una secuencia de orejas, cada uno de cuyos puntos finales (después de la primera) pertenecen a una oreja anterior y cada uno de cuyos puntos interiores no pertenecen a ninguna oreja anterior. Una oreja abierta es un camino simple (una oreja sin vértices repetidos), y una descomposición en orejas abiertas es una descomposición en orejas en la que cada oreja después de la primera es abierta; un grafo tiene una descomposición en orejas abiertas si y solo si es biconectado. Una oreja es impar si tiene un número impar de aristas, y una descomposición en orejas impares es una descomposición en orejas en la que cada oreja es impar; un grafo tiene una descomposición en orejas impares si y solo si es factor-crítico.
excentricidad
La excentricidad de un vértice es la distancia más lejana entre él y cualquier otro vértice.
borde
Una arista es (junto con los vértices) una de las dos unidades básicas a partir de las cuales se construyen los grafos. Cada arista tiene dos (o en los hipergrafos, más) vértices a los que está unida, llamados sus puntos finales. Las aristas pueden ser dirigidas o no dirigidas; las aristas no dirigidas también se denominan líneas y las aristas dirigidas también se denominan arcos o flechas. En un grafo simple no dirigido , una arista puede representarse como el conjunto de sus vértices, y en un grafo simple dirigido puede representarse como un par ordenado de sus vértices. Una arista que conecta los vértices x e y a veces se escribe xy .
corte de borde
Conjunto de aristas cuya eliminación desconecta el grafo. Un corte de una arista se denomina puente, istmo o arista cortada.
conjunto de bordes
El conjunto de aristas de un gráfico dado G , a veces denotado por E ( G ) .
gráfico sin aristas
El grafo sin aristas o totalmente desconectado en un conjunto dado de vértices es el grafo que no tiene aristas. A veces se lo llama grafo vacío, pero este término también puede referirse a un grafo sin vértices.
incrustación
Una incrustación de grafo es una representación topológica de un grafo como un subconjunto de un espacio topológico en el que cada vértice se representa como un punto, cada arista se representa como una curva que tiene los extremos de la arista como extremos de la curva y no hay otras intersecciones entre vértices o aristas. Un grafo plano es un grafo que tiene una incrustación de este tipo en el plano euclidiano, y un grafo toroidal es un grafo que tiene una incrustación de este tipo en un toro. El género de un grafo es el género mínimo posible de una variedad bidimensional en la que se puede incrustar.
gráfico vacío
1. Un gráfico sin aristas en un conjunto no vacío de vértices.
2. El gráfico de orden cero , un gráfico sin vértices ni aristas.
fin
Un final de un gráfico infinito es una clase de equivalencia de rayos, donde dos rayos son equivalentes si hay un tercer rayo que incluye infinitos vértices de ambos.
punto final
Uno de los dos vértices unidos por una arista dada, o uno de los primeros o últimos vértices de un paseo, sendero o camino. El primer punto final de una arista dirigida dada se llama cola y el segundo punto final se llama cabeza .
enumeración
La enumeración de grafos es el problema de contar los grafos en una clase dada de grafos, en función de su orden. En términos más generales, los problemas de enumeración pueden referirse a problemas de contar una cierta clase de objetos combinatorios (como camarillas, conjuntos independientes, coloraciones o árboles de expansión) o de enumerar algorítmicamente todos esos objetos.
Euleriano
Un camino euleriano es un recorrido que utiliza cada arista de un grafo exactamente una vez. Un circuito euleriano (también llamado ciclo euleriano o recorrido euleriano) es un recorrido cerrado que utiliza cada arista exactamente una vez. Un grafo euleriano es un grafo que tiene un circuito euleriano. Para un grafo no dirigido, esto significa que el grafo está conectado y cada vértice tiene un grado par. Para un grafo dirigido, esto significa que el grafo está fuertemente conectado y cada vértice tiene un grado de entrada igual al grado de salida. En algunos casos, el requisito de conectividad se relaja y un grafo que cumple solo los requisitos de grado se llama euleriano.
incluso
Divisible por dos; por ejemplo, un ciclo par es un ciclo cuya longitud es par.
expansor
Un gráfico expansor es un gráfico cuya expansión de aristas, expansión de vértices o expansión espectral está limitada a partir de cero.
expansión
1. La expansión de aristas, número isoperimétrico o constante de Cheeger de un grafo G es la relación mínima, sobre subconjuntos S de como máximo la mitad de los vértices de G , del número de aristas que salen de S al número de vértices en S .
2. La expansión de vértices, número isoperimétrico de vértices o magnificación de un grafo G es la relación mínima, sobre subconjuntos S de como máximo la mitad de los vértices de G , del número de vértices exteriores pero adyacentes a S al número de vértices en S .
3. La expansión vecina única de un grafo G es la relación mínima, sobre subconjuntos de como máximo la mitad de los vértices de G , del número de vértices fuera de S pero adyacentes a un vértice único en S al número de vértices en S .
4. La expansión espectral de un grafo d -regular G es la brecha espectral entre el mayor valor propio d de su matriz de adyacencia y el segundo mayor valor propio.
5. Una familia de grafos tiene expansión acotada si todos sus r -menores superficiales tienen una relación de aristas a vértices acotada por una función de r , y expansión polinómica si la función de r es un polinomio.

F

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

GRAMO

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

yo

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

I

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

Yo

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

K

K
Para la notación de gráficos completos, gráficos bipartitos completos y gráficos multipartitos completos, consulte completo.
k
κ ( G ) (usando la letra griega kappa) puede referirse a la conectividad del vértice de G o al número de camarilla de G .
núcleo
Un núcleo de un gráfico dirigido es un conjunto de vértices que es a la vez estable y absorbente.
nudo
Sección ineludible de un grafo dirigido. Véase nudo (matemáticas) y teoría de nudos .

yo

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

METRO

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

norte

norte
1. Para la notación de vecindarios abiertos y cerrados, véase vecindario.
2. A menudo se utiliza una n minúscula (especialmente en informática) para indicar el número de vértices en un gráfico determinado.
vecino
vecino
Un vértice que es adyacente a un vértice dado.
vecindario
vecindario
El entorno abierto (o vecindad) de un vértice v es el subgrafo inducido por todos los vértices adyacentes a v . El entorno cerrado se define de la misma manera pero también incluye al propio v . El entorno abierto de v en G puede denotarse como N G ( v ) o N ( v ) , y el entorno cerrado puede denotarse como N G [ v ] o N [ v ] . Cuando no se especifica la apertura o el cierre de un entorno, se supone que es abierto.
red
Un gráfico en el que los atributos (por ejemplo, nombres) están asociados con los nodos y/o bordes.
nodo
Un sinónimo de vértice.
sin borde
Un no borde o antiborde es un par de vértices que no son adyacentes; los bordes del gráfico complementario.
gráfico nulo
Ver gráfico vacío.

Oh

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

PAG

padre
En un árbol con raíz, un padre de un vértice v es un vecino de v a lo largo del borde entrante, el que se dirige hacia la raíz.
camino
Un camino puede ser un paseo o un paseo sin vértices repetidos y, en consecuencia, sin aristas (también llamado camino simple), según la fuente. Algunos casos especiales importantes son los caminos inducidos y los caminos más cortos .
descomposición de trayectoria
Una descomposición de ruta de un grafo G es una descomposición de árbol cuyo árbol subyacente es una ruta. Su ancho se define de la misma manera que para las descomposiciones de árbol, como uno menos que el tamaño de la bolsa más grande. El ancho mínimo de cualquier descomposición de ruta de G es el ancho de ruta de G.
ancho de ruta
El ancho de ruta de un grafo G es el ancho mínimo de una descomposición de ruta de G. También se puede definir en términos del número de clique de una completitud de intervalo de G. Siempre se encuentra entre el ancho de banda y el ancho de árbol de G. También se lo conoce como grosor de intervalo, número de separación de vértices o número de búsqueda de nodos.
colgante
Ver hoja.
perfecto
1. Un grafo perfecto es un grafo en el que, en cada subgrafo inducido, el número cromático es igual al número de clique. El teorema del grafo perfecto y el teorema del grafo perfecto fuerte son dos teoremas sobre grafos perfectos; el primero demuestra que sus complementos también son perfectos y el segundo demuestra que son exactamente los grafos sin agujeros impares ni antiagujeros.
2. Un grafo perfectamente ordenable es un grafo cuyos vértices pueden ordenarse de tal manera que un algoritmo de coloración voraz con este ordenamiento coloree de manera óptima cada subgrafo inducido. Los grafos perfectamente ordenables son una subclase de los grafos perfectos.
3. Una coincidencia perfecta es una coincidencia que satura cada vértice; ver coincidencia.
4. Una factorización 1 perfecta es una partición de los bordes de un gráfico en coincidencias perfectas, de modo que cada dos coincidencias forman un ciclo hamiltoniano.
periférico
1. Un ciclo periférico o ciclo no separativo es un ciclo con como máximo un puente.
2. Un vértice periférico es un vértice cuya excentricidad es máxima. En un árbol, debe ser una hoja.
Petersen
1.   Julius Petersen (1839-1910), teórico de grafos danés.
2. El gráfico de Petersen , un gráfico de 10 vértices y 15 aristas que se utiliza frecuentemente como contraejemplo.
3.   Teorema de Petersen que establece que todo grafo cúbico sin puente tiene un emparejamiento perfecto.
plano
Un grafo plano es un grafo que tiene una incrustación en el plano euclidiano. Un grafo plano es un grafo plano para el cual ya se ha fijado una incrustación particular. Un grafo k -planar es uno que se puede dibujar en el plano con un máximo de k cruces por arista.
poliárbol
Un poliárbol es un árbol orientado; equivalentemente, un gráfico acíclico dirigido cuyo gráfico no dirigido subyacente es un árbol.
fuerza
1. Una potencia de grafo G k de un grafo G es otro grafo en el mismo conjunto de vértices; dos vértices son adyacentes en G k cuando están a una distancia de como máximo k en G . Una potencia de hoja es un concepto estrechamente relacionado, derivado de una potencia de un árbol al tomar el subgrafo inducido por las hojas del árbol.
2.   El análisis de gráficos de potencia es un método para analizar redes complejas mediante la identificación de camarillas, biclícuotas y estrellas dentro de la red.
3.   Las leyes de potencia en las distribuciones de grados de redes libres de escala son un fenómeno en el que el número de vértices de un grado dado es proporcional a una potencia del grado.
predecesor
Un vértice que viene antes de un vértice dado en una trayectoria dirigida.
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 ningún módulo no trivial.
3. En la teoría de las divisiones , los cortes cuyo conjunto de cortes es un grafo bipartito completo, un grafo primo es un grafo sin divisiones. 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 en sí mismo 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 arista en relación con todo el grafo; para grafos finitos, los subgrafos propios nunca son isomorfos a todo el grafo, pero para grafos infinitos pueden serlo.
2. Una coloración adecuada es una asignación de colores a los vértices de un gráfico (una coloración) que asigna diferentes colores a los puntos finales de cada arista; ver color.
3. Un gráfico de intervalo propio o un gráfico de arco circular propio es un gráfico de intersección de un conjunto de intervalos o arcos circulares (respectivamente) de modo que ningún intervalo o arco contiene otro intervalo o arco. Los gráficos de intervalo propio también se denominan gráficos de intervalo unitario (porque siempre se pueden representar mediante intervalos unitarios) o gráficos de indiferencia.
propiedad
Una propiedad de un grafo es algo que puede ser verdadero en el caso de algunos grafos y falso en el de otros, y que depende únicamente de la estructura del grafo y no de información incidental como las etiquetas. Las propiedades de un grafo pueden describirse de manera equivalente en términos de clases de grafos (los grafos que tienen una propiedad determinada). De manera más general, una propiedad de un grafo también puede ser una función de los grafos que, a su vez, 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 gráfico no dirigido en el que cada componente conectado tiene como máximo un ciclo, o un gráfico dirigido en el que cada vértice tiene como máximo un borde saliente.
seudónimo
Un pseudografo es un grafo o multigrafo que permite bucles propios.

Q

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

R

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

S

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

yo

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

vértice unario
En un árbol con raíz, un vértice unario es un vértice que tiene exactamente un vértice hijo.
Sin dirección
Un grafo no dirigido es un grafo en el que los dos puntos finales de cada arista no se distinguen entre sí. Véase también dirigido y mixto . En un grafo mixto , una arista no dirigida es nuevamente aquella en la que los puntos finales no se distinguen entre sí.
uniforme
Un hipergrafo es k -uniforme cuando todas sus aristas tienen k puntos finales, y uniforme cuando es k -uniforme para algún k . Por ejemplo, los grafos ordinarios son lo mismo que los hipergrafos 2 -uniformes.
universal
1. Un gráfico universal es un gráfico que contiene como subgráficos todos los gráficos de una familia dada de gráficos, o todos los gráficos de un tamaño u orden dado dentro de una familia dada de gráficos.
2. Un vértice universal (también llamado vértice dominante o ápice) es un vértice que se encuentra adyacente a todos los demás vértices del gráfico. Por ejemplo, los gráficos de rueda y los gráficos de umbral conectados siempre tienen un vértice universal.
3. En la lógica de gráficos , un vértice que está cuantificado universalmente en una fórmula puede llamarse vértice universal para esa fórmula.
gráfico no ponderado
Un gráfico cuyos vértices y aristas no tienen pesos asignados; lo opuesto de un gráfico ponderado.
gráfico de utilidad
El gráfico de utilidad es un nombre para el gráfico bipartito completo .

V

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

Yo

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

Véase también

Referencias

  1. ^ Farber, M.; Hahn, G.; Hell, P .; Miller, DJ (1986), "Sobre el número acromático de grafos", Journal of Combinatorial Theory, Serie B , 40 (1): 21–39, doi : 10.1016/0095-8956(86)90062-6.
  2. ^ abcdefgh Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), "B.4 Graphs", Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw-Hill, págs. 1080-1084.
  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.
  5. ^ Diestel, Reinhard (2017), "1.1 Gráficos", Teoría de grafos , Textos de posgrado en matemáticas, vol. 173 (5.ª ed.), Berlín, Nueva York: Springer-Verlag, p. 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 gráfico y su número de Anderson", J. Combin. Theory Ser. B , 15 (3): 225–255, doi : 10.1016/0095-8956(73)90038-5
  7. ^ van der Holst, Hein (marzo de 2009), "Un algoritmo de tiempo polinomial para encontrar una incrustación sin enlaces de un gráfico", Journal of Combinatorial Theory, Serie B , 99 (2), Elsevier BV: 512–530, doi :10.1016/j.jctb.2008.10.002
  8. ^ Sudakov, Benny; Volec, Jan (2017), "Copias de gráficos coloreadas correctamente y en arco iris con pocas cerezas", Journal of Combinatorial Theory, Serie B , 122 (1): 391–416, arXiv : 1504.06176 , doi : 10.1016/j.jctb.2016.07.001.
  9. ^ profundidad, NIST
  10. ^ Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), "Capítulo 7: Subgrafo prohibido", Clases de grafos: una encuesta, Monografías SIAM sobre matemáticas discretas y aplicaciones, págs. 105-121, ISBN 978-0-89871-432-6
  11. ^ Mitchem, John (1969), "Hipopropiedades en grafos", The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) , Lecture Notes in Mathematics, vol. 110, Springer, págs. 223-230, doi :10.1007/BFb0060121, ISBN 978-3-540-04629-5, Sr.  0253932.
  12. ^ nivel ab , 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 (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicado a la memoria de JWT Youngs) , Lecture Notes in Mathematics, vol. 303, Springer, págs. 43–54, doi :10.1007/BFb0067356, ISBN 978-3-540-06096-3, Sr.  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. ^ "Teoría de cadenas y grafos", britannica.com , consultado el 25 de marzo de 2018