Glosario de teoría de grafos

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Lista de definiciones de términos y conceptos utilizados en la teoría del gráfico

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

Símbolos

Soportes cuadrados [ ]: $G [S]$ es el subgrafo inducido de un gráfico $G$ para subconjunto de vértice $S$ .
Primer símbolo ': El símbolo principal se utiliza a menudo para modificar la notación para los invariantes gráficos de modo que se aplica a la gráfica de línea en lugar del gráfico dado. Por ejemplo, $α () G)$ es el número de independencia de un gráfico; $α . G)$ es el número coincidente del gráfico, que equivale al número de independencia de su gráfico de línea. Análogamente, $χ () G)$ es el número cromático de un gráfico; $χ . G)$ es el índice cromático del gráfico, que equivale al número cromático de su gráfico de línea.

A

absorción: Un conjunto absorbente $A$ de un gráfico dirigido $G$ es un conjunto de vértices tal que para cualquier vértice ${displaystyle vin Gsetminus A}$ , hay un borde de $v$ hacia un vértice de $A$ .
acromático: El número acromático de un gráfico es el número máximo de colores en una coloración completa.
acíclica: 1. Un gráfico es acíclico si no tiene ciclos. Un gráfico acíclico no dirigido es lo mismo que un bosque. Un gráfico acíclico dirigido, que es un digraph sin ciclos dirigidos, a menudo se llama un gráfico acíclico dirigido, especialmente en la ciencia de la computadora.; 2. Una coloración acíclica de un gráfico no dirigido es una coloración adecuada en la que cada dos clases de colores inducen un bosque.
matriz de adyacencia: La matriz adyacencia de un gráfico es una matriz cuyas filas y columnas están indexadas por vértices del gráfico, con una en la celda para fila $i$ y columna $j$ cuando vértices $i$ y $j$ están adyacentes, y un cero de otro modo.
adyacente: 1. La relación entre dos vértices que son ambos puntos finales del mismo borde.; 2. La relación entre dos bordes distintos que comparten un vértice final.
α: Para un gráfico $G$ , $α () G)$ (utilizando la letra griega alpha) es su número de independencia (ver independiente) y $α . G)$ es su número de coincidencia (ver coincidencia).
alternando: En un gráfico con un a juego, un camino alternante es un camino cuyos bordes se alternan entre los bordes emparejados e inigualables. Un ciclo de alternancia es, de forma similar, un ciclo cuyos bordes se alternan entre bordes emparejados e inigualables. Un camino de aumento es un camino alternante que comienza y termina en vértices insaturados. Un emparejamiento más grande se puede encontrar como la diferencia simétrica de la coincidencia y el camino de aumento; un emparejamiento es máximo si y sólo si no tiene un camino de aumento.
Antichain: En un gráfico acíclico dirigido, un subconjunto $S$ de vértices que son incomparables, es decir, para cualquier $xleq y$ dentro $S$ , no hay camino dirigido desde $x$ a $Sí.$ o desde $Sí.$ a $x$ . Inspirado por la noción de antichainas en conjuntos parcialmente ordenados.
anti-edge: Sinónimo para non-edge, un par de vértices no adyacentes.
antitriángulo: Un conjunto independiente de tres-vertex, el complemento de un triángulo.
apex: 1. Un gráfico apex es un gráfico en el que se puede quitar un vértice, dejando un subgrafo plano. El vértice removido se llama el ápice. A $k$ -apex graph es un gráfico que puede ser planificado por la eliminación de $k$ vertices.; 2. Sinónimo para el vértice universal, un vértice adyacente a todos los otros vértices.
arborescencia: Sinónimo de un árbol arraigado y dirigido; vea el árbol.
arc: Mira el borde.
flecha: Un par de vértices ordenados, como un borde en un gráfico dirigido. Una flecha $() x, Sí.)$ tiene una cola $x$ , una cabeza $Sí.$ , y una dirección $desde x a Sí.$ ; $Sí.$ se dice que es el sucesor directo $x$ y $x$ el antecesor directo $Sí.$ . La flecha $() Sí., x)$ es la flecha invertida de la flecha $() x, Sí.)$ .
punto de articulación: Un vértice en un gráfico conectado cuya eliminación desconectaría el gráfico.
-: Un árbol k-ary es un árbol arraigado en el que cada vértice interno no tiene más que $k$ niños. Un árbol de 1 kilo es sólo un camino. Un árbol 2-ary también se llama un árbol binario, aunque ese término se refiere más adecuadamente a los árboles 2-ary en los que los niños de cada nodo se distinguen como niños izquierdos o derecho (con la mayoría de uno de cada tipo). A $k$ - Se dice que el árbol está completo si cada vértice interno tiene exactamente $k$ niños.
aumento: Un tipo especial de camino alternado; ver alternancia.
automorfismo: Un autmorfismo gráfico es una simetría de un gráfico, un isomorfismo del gráfico a sí mismo.

B

bolsa: Uno de los conjuntos de vértices en una descomposición de árboles.
equilibrado: Un gráfico bipartito o multipartito es equilibrado si cada dos subconjuntos de su partición del vértice tienen tamaños dentro de uno de los otros.
ancho de banda: El ancho de banda de un gráfico $G$ es el mínimo, sobre todos los pedidos de vértices de $G$ , de la longitud del borde más largo (el número de pasos en el orden entre sus dos puntos finales). También es uno menos que el tamaño de la camarilla máxima en un intervalo adecuado de terminación de $G$ , elegido para minimizar el tamaño de la camarilla.
biblio: Sinónimo para gráfico bipartito completo o subgrafo bipartito completo; ver completo.
biconnected: Generalmente un sinónimo para 2-vertex-conectado, pero a veces incluye K₂ Aunque no está conectado. Ver conectado; para componentes biconectados, ver componente.
Número obligatorio: La proporción más pequeña posible del número de vecinos de un subconjunto adecuado de vértices al tamaño del subconjunto.
bipartito: Un gráfico bipartito es un gráfico cuyos vértices pueden dividirse en dos conjuntos descomunados de tal manera que los vértices en un conjunto no están conectados entre sí, pero pueden estar conectados a vértices en el otro conjunto. Ponga otra manera, un gráfico bipartito es un gráfico sin ciclos impares; equivalentemente, es un gráfico que puede ser coloreado correctamente con dos colores. Los gráficos bipartitos se escriben a menudo $G = U, V, E)$ Donde $U$ y $V$ son los subconjuntos de vértices de cada color. Sin embargo, a menos que el gráfico esté conectado, puede que no tenga un 2-coloring único.
biregular: Un gráfico biregular es un gráfico bipartito en el que sólo hay dos grados diferentes de vértice, uno para cada conjunto de la bipartición del vértice.
bloque: 1. Un bloque de un gráfico $G$ es un subgrafo maximal que es ya sea un vertex aislado, un borde de puente, o un subgrafo de 2 conexiones. Si un bloque está 2-conectado, cada par de vértices en él pertenecen a un ciclo común. Cada borde de un gráfico pertenece exactamente a una cuadra.; 2. El gráfico bloque de un gráfico $G$ es otro gráfico cuyos vértices son los bloques $G$ , con un borde que conecta dos vértices cuando los bloques correspondientes comparten un punto de articulación; es decir, es el gráfico de intersección de los bloques de $G$ . El gráfico bloque de cualquier gráfico es un bosque.; 3. El gráfico bloqueado (o bloque-punto) de un gráfico $G$ es un gráfico bipartito donde un conjunto de partito consiste en los cortes-vertices de $G$ , y el otro tiene un vértice $b_{i}$ para cada bloque $B_{i}$ de $G$ . Cuando $G$ está conectado, su gráfico de bloque es un árbol.; 4. Un gráfico de bloque (también llamado un árbol de camarillas si está conectado, y a veces erróneamente llamado un árbol Husimi) es un gráfico todos cuyos bloques son gráficos completos. Un bosque es un gráfico de bloques, por lo que en particular el gráfico de bloques de cualquier gráfico es un gráfico de bloques, y cada gráfico de bloque puede ser construido como el gráfico de bloque de un gráfico.
bono: Un corte mínimo: un conjunto de bordes cuya eliminación desconecta el gráfico, para el cual ningún subconjunto adecuado tiene la misma propiedad.
libro: 1. Un libro, gráfico de libros 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 un libro cuadrilátero, es una colección de $4$ - ciclos unidos en un borde compartido; el producto cartesiano de una estrella con un borde.; 3. Una incrustación de libros es una incrustación de un gráfico en un libro topológico, un espacio formado por unir una colección de medio plano a lo largo de una línea compartida. Por lo general, los vértices de la incrustación son requeridos para estar en la línea, que se llama la columna vertebral de la incrustación, y los bordes de la incrustación están obligados a mentir dentro de un solo medio plano, una de las páginas del libro.
frontera: 1. En un gráfico embedding, un paseo fronterizo es el subgrafo que contiene todos los bordes del incidente y vértices a una cara.
brazalete: Un bramble es una colección de subgrafos conectados que se tocan mutuamente, donde dos subgrafos tocan si comparten un vértice o cada uno incluye un punto final de un borde. El orden de un bramble es el tamaño más pequeño de un conjunto de vértices que tiene una intersección no vacía con todos los subgrafos. El ancho de árbol de un gráfico es el orden máximo de cualquiera de sus brambles.
descomposición: Una subdivisión-decomposición $G$ es un agrupamiento jerárquico de los bordes de $G$ , representado por un árbol binario no arraigado con sus hojas etiquetadas por los bordes de $G$ . El ancho de una rama-decomposición es el máximo, sobre los bordes $e$ de este árbol binario, del número de vértices compartidos entre los subgrafos determinado 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 rama-decomposición de $G$ .
ancho de rama: Ver sucursal-decomposición.
puente: 1. Un puente, istmo, o borde cortado es un borde cuya eliminación desconectaría el gráfico. Un gráfico sin puentes es uno que no tiene puentes; equivalentemente, un gráfico conectado con 2 pasos.; 2. Especialmente en el contexto de la prueba de la planaridad, un puente de un ciclo es un subgrafo maximal que se descompone del ciclo y en el que cada dos bordes pertenecen a un camino que está internamente descompuesto del ciclo. Un acorde es un puente de una sola pista. Un ciclo periférico es un ciclo con la mayoría de un puente; debe ser una cara en cualquier embedición plano de su gráfico.; 3. Un puente de un ciclo también puede significar un camino que conecta dos vértices de un ciclo pero es más corto que cualquiera de los caminos del ciclo que conecta los mismos dos vértices. Un gráfico puenteado es un gráfico en el que cada ciclo de cuatro o más vértices tiene un puente.
sin puente: Un gráfico sin puente es un gráfico que no tiene bordes de puente; es decir, un gráfico conectado con 2 pasos.
mariposa: 1. El gráfico mariposa tiene cinco vértices y seis bordes; está formado por dos triángulos que comparten un vértice.; 2. La red de mariposas es un gráfico utilizado como una arquitectura de red en computación distribuida, estrechamente relacionado con los ciclos conectados al cubo.

c

C: $C n$ es un $n$ - gráfico de ciclo de vértex; ver ciclo.
cactus: Un gráfico de cactus, árbol de cactus, cactus o árbol Husimi es un gráfico conectado en el que cada borde pertenece a la mayoría de un ciclo. Sus bloques son ciclos o bordes individuales. Si, además, cada vértice pertenece a la mayoría de dos bloques, entonces se llama cactus de Navidad.
jaula: Una jaula es un gráfico regular con el orden más pequeño posible para su circunferencia.
canónica
canonización: Una forma canónica de un gráfico es un invariante tal que dos gráficos tienen invariantes iguales si y sólo si son isomorfos. Las formas canónicas también pueden llamarse invariantes canónicos o invariantes completos, y a veces se definen sólo para los gráficos dentro de una familia particular de gráficos. La canonización de Gráficos es el proceso de computación de 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. Vea también cubierta, el multiset de todas las tarjetas de un gráfico.
ancho: El ancho de talla es una noción de ancho de gráfico analógico a ancho de rama, pero usando agrupaciones jerárquicas de vértices en lugar de agrupaciones jerárquicas de bordes.
oruga: Un árbol de orugas o oruga es un árbol en el que los nodos internos inducen un camino.
centro: El centro de un gráfico es el conjunto de vertices de la excentricidad mínima.
cadena: 1. Sinónimo para caminar.; 2. Al aplicar métodos de topología algebraica a gráficos, un elemento de un complejo de cadena, a saber, un conjunto de vértices o un conjunto de bordes.
Cheeger constante: Ver expansión.
cereza: Una cereza es un camino en tres vértices.
χ: $χ () G)$ (utilizando la letra griega chi) es el número cromático $G$ y $χ . G)$ es su índice cromático; vea cromático y colorante.
niño: En un árbol arraigado, un niño de un vértice $v$ es un vecino $v$ a lo largo de un borde saliente, uno que se dirige lejos de la raíz.
acorde
coro: 1. Un acorde de un ciclo es un borde que no pertenece al ciclo, para el cual ambos extremos pertenecen al ciclo.; 2. Un gráfico coral es un gráfico en el que cada ciclo de cuatro o más vértices tiene un acorde, por lo que los únicos ciclos inducidos son triángulos.; 3. Un gráfico del coro es un gráfico del coro en el que cada ciclo de la longitud seis o más tiene un acorde extraño.; 4. Un gráfico bipartito del coro no es el coro (a menos que sea un bosque); es un gráfico bipartito en el que cada ciclo de seis o más vértices tiene un acorde, por lo que los únicos ciclos inducidos son 4 ciclos.; 5. Un acorde 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 acordes se llama un gráfico círculo.
cromático: Tener que ver con colorear; ver color. La teoría del gráfico cromático es la teoría de la coloración del gráfico. El número cromático $χ () G)$ es el número mínimo de colores necesarios en una adecuada coloración de $G$ . $χ . G)$ es el índice cromático $G$ , el número mínimo de colores necesarios en un borde adecuado para colorear de $G$ .
choosable
choosability: Un gráfico es $k$ -establecido si tiene una lista para colorear cada vértice tiene una lista $k$ colores disponibles. La coreabilidad del gráfico es la más pequeña $k$ para lo cual es $k$ - Es posible.
círculo: Un gráfico círculo es el gráfico de intersección de acordes de un círculo.
circuito: Un circuito puede referirse a un sendero cerrado o a un elemento del espacio del ciclo (un subgrafo de azotes Eulerian). El rango de circuito de un gráfico es la dimensión de su espacio de ciclo.
circunferencia: La circunferencia de un gráfico es la longitud de su ciclo simple más largo. El gráfico es Hamiltonian si y sólo si su circunferencia iguala su orden.
clase: 1. Una clase de gráficos o familia de gráficos es una colección (generalmente infinita) de gráficos, a menudo definida como los gráficos que tienen alguna propiedad específica. La palabra "clase" se utiliza más que "set" porque, a menos que se hagan restricciones especiales (como restringir los vértices a ser extraídos de un conjunto particular, y definir los bordes a ser conjuntos de dos vértices) las clases de gráficos no suelen ser conjuntos cuando se formalizan usando la teoría de conjuntos.; 2. Una clase de color de un gráfico de colores es el conjunto de vértices o bordes que tienen un color particular.; 3. En el contexto del teorema de Vizing, en el borde para colorear gráficos simples, se dice que un gráfico es de clase uno si su índice cromático equivale a su grado máximo, y clase dos si su índice cromático equivale a uno más el grado. Según el teorema de Vizing, todos los gráficos simples son de clase uno o clase dos.
garra: Una garra es un árbol con un vértice interno y tres hojas, o equivalentemente el gráfico bipartito completo $K 1,3$ . Un gráfico libre de garras es un gráfico que no tiene un subgrafo inducido que es 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 maximal), uno que no es parte de tal conjunto (o subgrafo). A $k$ -Clique es una camarilla de orden $k$ . El número de la camarilla $\cdot () G)$ de un gráfico $G$ es el orden de su camarilla más grande. El gráfico de un gráfico G es el gráfico de intersección de las camarillas máximas en G. Vea también biclique, un subgraph bipartito completo.
oblicuo árbol: Un sinónimo para un gráfico de bloques.
Clique-width: El ancho de la camarilla de un gráfico $G$ es el número mínimo de etiquetas distintas necesarias para construir $G$ por operaciones que crean un vertex etiquetado, forman la unión disyuntiva de dos gráficos etiquetados, agregan un borde que conecta todos los pares de vértices con etiquetas dadas, o relabel todos los vértices con una etiqueta dada. Los gráficos del ancho de camarilla al máximo $2$ son exactamente los cographs.
cerrado: 1. Un barrio cerrado es uno que incluye su vértice central; ver barrio.; 2. Un paseo cerrado es uno que comienza y termina en el mismo vértice; vea caminar.; 3. Un gráfico se cierra transitivamente si equivale a su propio cierre transitivo; vea transitivo.; 4. Una propiedad gráfica está cerrada bajo alguna operación en gráficos si, cuando el argumento o los argumentos a la operación tienen la propiedad, entonces también lo hace el resultado. Por ejemplo, las propiedades hereditarias se cierran bajo subgrafos inducidos; las propiedades monotonales se cierran bajo subgrafos; y las propiedades menores de edad se cierran bajo menores.
cierre: 1. Para el cierre transitivo de un gráfico dirigido, vea transitivo.; 2. Un cierre de un gráfico dirigido es un conjunto de vértices que no tienen bordes salientes para vertices fuera del cierre. Por ejemplo, un lavabo es un cierre de un solo vértigo. El problema del cierre es el problema de encontrar un cierre de peso mínimo o máximo.
co-: Este prefijo tiene varios significados generalmente implicando gráficos complementarios. Por ejemplo, un gráfico es un gráfico producido por operaciones que incluyen la complementación; un cocoloring es un colorante en el que cada vértice induce un conjunto independiente (como en la coloración adecuada) o una camarilla (como en la coloración del complemento).
color
para colorear: 1. Un gráfico para colorear es un etiquetado de los vértices de un gráfico por elementos de un determinado conjunto de colores, o equivalentemente una partición de los vértices en subconjuntos, llamados "clase de color", cada uno de los cuales está asociado con uno de los colores.; 2. Algunos autores utilizan "coloring", sin cualificación, para significar una coloración adecuada, una que asigna diferentes colores a los puntos finales de cada borde. En la coloración del gráfico, el objetivo es encontrar una coloración adecuada que utiliza tan pocos colores como sea posible; por ejemplo, los gráficos bipartitos son los gráficos que tienen colores con sólo dos colores, y el teorema de cuatro colores indica que cada gráfico planar puede ser coloreado con al menos cuatro colores. Se dice que un gráfico es $k$ -colorado si ha sido (properly) coloreado con $k$ colores, y $k$ -colorable o $k$ - Cromático si es posible.; 3. Se han estudiado muchas variaciones de coloración, incluyendo la coloración de bordes (fildos colorantes para que no haya dos bordes con el mismo punto final comparten un color), la coloración de lista (coloración apropiada con cada vértice restringido a un subconjunto de los colores disponibles), coloración acíclica (cada subgrafo de 2 colores es acíclica), co-coloración (cada clase de color induce un conjunto independiente o una camarilla), dos clases de colorida completas; 4. El número de color de un gráfico es uno más la degeneración. Se llama así porque aplicar un algoritmo de coloración codicioso a una orden degeneración del gráfico utiliza en la mayoría de estos muchos colores.
comparabilidad: Un gráfico no dirigido es un gráfico de comparabilidad si sus vértices son los elementos de un conjunto parcialmente ordenado y dos vértices están adyacentes cuando son comparables en el orden parcial. Equivalentemente, un gráfico de comparabilidad es un gráfico que tiene una orientación transitiva. Muchas otras clases de gráficos pueden definirse como gráficos de comparabilidad de tipos especiales de orden parcial.
complemento: El gráfico de complemento ${bar {G}}$ de un gráfico simple $G$ es otro gráfico en el mismo vértice que $G$ , con un borde para cada dos vértices que no están adyacentes $G$ .
completo: 1. Un gráfico completo es uno en el que cada dos vértices están adyacentes: todos los bordes que podrían existir están presentes. Un gráfico completo con $n$ vertices es a menudo denotado $K n$ . Un gráfico bipartito completo es uno en el que cada dos vértices en los lados opuestos de la partición de vértices están adyacentes. Un gráfico bipartito completo con $a$ vertices en un lado de la partición y $b$ vertices en el otro lado es a menudo denotado $K a, b$ . La misma terminología y notación también se ha ampliado para completar gráficos multipartitos, gráficos en los que los vértices se dividen en más de dos subconjuntos y cada par de vértices en diferentes subconjuntos están adyacentes; si los números de vértices en los subconjuntos son adyacentes $a, b, c,...$ entonces este gráfico está denotado $K a, b, c,...$ .; 2. Una terminación de un gráfico dado es un supergraph que tiene alguna propiedad deseada. Por ejemplo, una finalización del coro es un supergraph que es un gráfico del coro.; 3. Un emparejamiento completo es un sinónimo para un emparejado perfecto; ver coincidencia.; 4. Una coloración completa es una coloración adecuada en la que cada par de colores se utiliza para los puntos finales de al menos un borde. Cada coloración con un número mínimo de colores está completo, pero puede existir coloración completa con un mayor número de colores. El número acromático de un gráfico es el número máximo de colores en una coloración completa.; 5. Un completo invariante de un gráfico es un sinónimo de forma canónica, un invariante que tiene diferentes valores para gráficos no isómorfos.
componente: Un componente conectado de un gráfico es un subgrafo conectado al máximo. El término también se utiliza para subgrafos o subconjuntos máximos de los vértices de un gráfico que tienen algún orden superior de conectividad, incluyendo componentes biconectados, componentes triconectados y componentes fuertemente conectados.
condensación: La condensación de un gráfico dirigido $G$ es un gráfico acíclico dirigido con un vértice para cada componente fuertemente conectado $G$ , y un borde que conecta pares de componentes que contienen los dos puntos finales de al menos un borde en $G$ .
cone: Un gráfico que contiene un vértice universal.
conectar: Porque estar conectado.
conectado: Un gráfico conectado es uno en el que cada par de vértices forma los puntos finales de un camino. Las formas más altas de conectividad incluyen una fuerte conectividad en gráficos dirigidos (por cada dos vértices hay caminos de uno a otro en ambas direcciones), gráficos conectados con k-vertex (removiendo menos que $k$ vertices no pueden desconectar el gráfico), y gráficos conectados con k-edge (removiendo menos que $k$ los bordes no pueden desconectar el gráfico).
componente conectado: Sinónimo para componente.
converso: El gráfico transversal es un sinónimo para el gráfico transpose; vea transpose.
núcleo: 1. Un k-core es el subgrafo inducido formado por la eliminación de todos los vértices de grado menos que $k$ , y todos los vértices cuyo grado se hace menos que $k$ después de extracciones anteriores. Ver degeneración.; 2. Un núcleo es un gráfico $G$ tal que cada homomorfismo gráfico de $G$ a sí mismo es un isomorfismo.; 3. El núcleo de un gráfico $G$ es un gráfico mínimo $H$ tal que existen homomorfismos de $G$ a $H$ y viceversa. $H$ es único hasta el isomorfismo. Puede ser representado como subgrafo inducido de $G$ , y es un núcleo en el sentido de que todas sus auto-homomorfismos son isomorfismos.; 4. En la teoría de emparejamientos de gráficos, el núcleo de un gráfico es un aspecto de su descomposición de Dulmage-Mendelsohn, formada como la unión de todos los emparejamientos máximos.
cotree: 1. El complemento de un árbol de azotes.; 2. Una estructura de árboles enraizada utilizada para describir un cograph, en la que cada vértice cograph es una hoja del árbol, cada nodo interno del árbol se etiqueta con 0 o 1, y dos vértices cograph están adyacentes si y sólo si su ancestro común más bajo en el árbol se etiqueta 1.
cubierta: Una cubierta de vértice es un conjunto de vértices incidente a cada borde en un gráfico. Una tapa de borde es un conjunto de bordes incidente a cada vértice en un gráfico. Un conjunto de subgrafos de un gráfico cubre que el gráfico si su unión – tomada en sentido de vértice y en sentido de borde – es igual al gráfico.
crítica: Un gráfico crítico para una propiedad dada es un gráfico que tiene la propiedad pero tal que cada subgrafo formado por eliminar un solo vértice no tiene la propiedad. Por ejemplo, un gráfico factor-crítico es uno que tiene una combinación perfecta (un 1-factor) para cada eliminación del vértice, pero (porque tiene un número extraño de vértices) no tiene una combinación perfecta. Compare hipo..., utilizado para gráficos que no tienen una propiedad pero para la cual cada eliminación de un solo vértigo hace.
cube
cúbico: 1. Cubo gráfico, el gráfico de ocho vértices de los vértices y bordes de un cubo.; 2. Gráfico Hypercube, una generalización superior del gráfico cubo.; 3. Gráfico de cubo plegado, formado a partir de un hipercubo añadiendo una combinación de vértices opuestos.; 4. Gráfico de cubos escalonados, la mitad del cuadrado de un gráfico hipercubo.; 5. Cubo parcial, subgrafo de conservación a distancia de un hipercubo.; 6. El cubo de un gráfico $G$ es el poder gráfico $G 3$ .; 7. Gráfico cúbico, otro nombre para un $3$ - Gráfico regular, uno en el que cada vértice tiene tres bordes de incidentes.; 8. Ciclos conectados al cubo, un gráfico cúbico formado por reemplazar cada vértice de un hipercubo por un ciclo.
corte
corte-set: Un corte es una partición de los vértices de un gráfico en dos subconjuntos, o el conjunto (también conocido como un conjunto de corte) de los bordes que abarcan tal partición, si ese conjunto es no vacío. Se dice que un borde abarca la partición si tiene puntos finales en ambos subconjuntos. Así, la eliminación de un conjunto de corte de un gráfico conectado lo desconecta.
punto de corte: Véase el punto de articulación.
espacio cortado: El espacio de corte de un gráfico es un espacio GF(2)-vector que tiene los conjuntos de corte del gráfico como sus elementos y diferencia simétrica de conjuntos como su operación de adición de vectores.
ciclo: 1. Un ciclo puede ser una especie de gráfico o una clase de caminata. Como paseo puede ser un paseo cerrado (también llamado recorrido) o más generalmente un paseo cerrado sin vertices repetidos y consecuentemente bordes (también llamado ciclo simple). En este último caso se considera generalmente como un gráfico, es decir, las opciones del primer vértice y la dirección generalmente se consideran inimportantes; es decir, las permutaciones cíclicas y las reversales de la caminata producen el mismo ciclo. Importantes tipos especiales de ciclo incluyen ciclos Hamiltonianos, ciclos inducidos, ciclos periféricos y el ciclo más corto, que define la circunferencia de un gráfico. A $k$ - el ciclo es un ciclo de longitud $k$ ; por ejemplo a $2$ - el ciclo es un digon y un $3$ - El ciclo es un triángulo. Un gráfico de ciclo es un gráfico que es en sí mismo un ciclo simple; un gráfico de ciclo con $n$ vertices es comúnmente denotado $C n$ .; 2. El espacio del ciclo 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

DAG: Abreviatura para gráfico acíclico dirigido, un gráfico dirigido sin ningún ciclo dirigido.
cubierta: El multiconjunto de gráficos formado a partir de un solo gráfico $G$ eliminando un solo vértice de todas las formas posibles, especialmente en el contexto de la conjetura de reconstrucción. Una cubierta de borde se forma de la misma manera eliminando un solo borde de todas las formas posibles. Los gráficos en una cubierta también se llaman tarjetas. Vea también crítico (grafos que tienen una propiedad que no es sostenida por ninguna tarjeta) e hipo- (grafos que no tienen una propiedad que se mantiene por todas las tarjetas).
descomposición: Ver descomposición de árboles, descomposición de caminos o descomposición de ramas.
degenerado
degeneración: A $k$ - el gráfico degenerado es un gráfico no dirigido en el que cada subgrafo inducido tiene un grado mínimo en la mayoría $k$ . La degeneración de un gráfico es la más pequeña $k$ para lo cual es $k$ - Degenerado. Una orden degeneración es una orden de los vértices tal que cada vértice tiene un grado mínimo en el subgrafo inducido de él y todos los vértices posteriores; en una degeneración ordenando un $k$ - Gráfico degenerado, cada vértice tiene $k$ vecinos más tarde. La degeneración también se conoce como $k$ -Número de núcleo, ancho y enlace, y uno más la degeneración también se llama el número de coloración o Szekeres-Número de lobo. $k$ - También se han llamado gráficos degenerados $k$ - Gráficos inductivos.
grado: 1. El grado de un vértice en un gráfico es su número de bordes de incidentes. El grado de un gráfico $G$ (o su grado máximo) es el máximo de los grados de sus vértices, a menudo denotados $Δ(G)$ ; el grado mínimo $G$ es el mínimo de sus grados de vértice, a menudo denotado $δ () G)$ . El grado a veces se llama valenciano; el grado de $v$ dentro $G$ puede ser denotado $d G () v)$ , $d () G)$ , o $deg(v)$ . El grado total es la suma de los grados de todos los vértices; por el apretón de manos lema es un número uniforme. La secuencia de grado es la colección de grados de todos los vértices, en orden ordenados de mayor a menor. En un gráfico dirigido, se puede distinguir el in-degree (número de bordes entrantes) y el out-degree (número de bordes salientes).; 2. El grado de homomorfismo de un gráfico es un sinónimo para su Hadwiger number, el orden del menor de la camarilla más grande.
Δ, δ: $Δ(G)$ (utilizando la letra griega delta) es el grado máximo de un vértice en $G$ , y $δ () G)$ es el grado mínimo; ver grado.
densidad: En un gráfico n nodos, la densidad es la relación del número de bordes del gráfico al número de bordes en un gráfico completo en n nodos. Ver el gráfico denso.
profundidad: La profundidad de un nodo en un árbol arraigado es el número de bordes 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. Nota, sin embargo, que algunos autores utilizan profundidad como sinónimo para el nivel de un nodo.
diámetro: El diámetro de un gráfico conectado es la longitud máxima de un camino más corto. Es decir, es el máximo de las distancias entre pares de vértices en el gráfico. Si el gráfico tiene pesos en sus bordes, entonces su diámetro ponderado mide la longitud del camino por la suma de los pesos del borde a lo largo de un camino, mientras que el diámetro no ponderado mide la longitud del camino por el número de bordes. Para gráficos desconectados, las definiciones varían: el diámetro puede definirse como infinito, o como el mayor diámetro de un componente conectado, o puede ser indefinido.
diamante: El gráfico de diamante es un gráfico no dirigido con cuatro vértices y cinco bordes.
desconexión: Fuertemente conectado. (No confundirse con desconexión)
digon: Un digon es un ciclo simple de longitud dos en un gráfico dirigido o un multigrafo. Las digonas no pueden ocurrir en gráficos simples no dirigidos como requieren repetir el mismo borde dos veces, lo que viola la definición de simple.
digraph: Sinónimo de gráfica dirigida.
dipath: Vea el camino dirigido.
antecesores directos: La cola de un borde dirigido cuya cabeza es el vértice dado.
sucesor directo: La cabeza de un borde dirigido cuya cola es el vértice dado.
Dirigida: Un gráfico dirigido es uno en el que los bordes tienen una dirección distinguida, de un vértice a otro. En un gráfico mixto, un borde dirigido es otra vez uno que tiene una dirección distinguida; los bordes dirigidos también pueden ser llamados arcos o flechas.
arc: Ver flecha.
borde dirigido: Ver flecha.
Línea dirigida: Ver flecha.
Camino dirigido: Un camino en el que todos bordes tienen la misma dirección. Si un camino dirigido conduce desde el vértice $x$ a vertex $Sí.$ , $x$ es un predecesor $Sí.$ , $Sí.$ es un sucesor $x$ , y $Sí.$ se dice que es accesible desde $x$ .
dirección: 1. La relación asimétrica entre dos vértices adyacentes en un gráfico, representado como una flecha.; 2. La relación asimétrica entre dos vértices en un camino dirigido.
desconexión: Porque estar desconectado.
desconectado: No conectado.
disjoint: 1. Dos subgrafos son disjoint borde si no comparten bordes, y el vértice se descompone si no comparten vértices.; 2. La unión disyuntiva de dos o más gráficos es un gráfico cuyo vértice y conjuntos de bordes son los sindicatos descomunales de los conjuntos correspondientes.
distancia: La distancia entre dos vértices en un gráfico es la longitud del camino más corto que tiene los dos vértices como sus puntos finales.
domatic: Una partición domática de un gráfico es una partición de los vértices en conjuntos dominantes. El número domático del gráfico es el número máximo de conjuntos dominantes en tal partición.
dominando: Un conjunto dominante es un conjunto de vértices que incluye o está adyacente a cada vértice en el gráfico; no confundirse con una cubierta de vértice, un conjunto de vértice que es incidente a todos los bordes en el gráfico. Importantes tipos especiales de conjuntos dominantes incluyen conjuntos dominantes independientes (dominar conjuntos que también son conjuntos independientes) y conjuntos de dominación conectados (dominar conjuntos que indujeron subgrafos conectados). También se puede llamar un vertex universal. El número de dominación de un gráfico es el número de vértices en el más pequeño conjunto dominante.
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$ .

E

E: $E () G)$ es el conjunto de bordes $G$ ; ver el borde fijado.
oreja: Un oído de un gráfico es un camino cuyos puntos finales pueden coincidir pero en el que de otro modo no hay repeticiones de vértices o bordes.
descomposición del oído: Una descomposición del oído es una partición de los bordes de un gráfico en una secuencia de oídos, cada uno de cuyos puntos finales (después del primero) pertenecen a un oído anterior y cada uno de cuyos puntos interiores no pertenecen a ningún oído anterior. Un oído abierto es un camino simple (un oído sin vértices repetidos), y una descomposición del oído abierto es una descomposición del oído en la que cada oído después de la primera está abierto; un gráfico tiene una descomposición del oído abierto si y sólo si está biconectado. Un oído es extraño si tiene un número extraño de bordes, y una descomposición del oído es una descomposición del oído en la que cada oído es extraño; un gráfico tiene una descomposición del oído extraño si y sólo si es factor crítico.
excentricidad: La excentricidad de un vértice es la distancia más lejana de ella a cualquier otro vértice.
borde: Un borde es (junto con vértices) una de las dos unidades básicas de las cuales se construyen gráficos. Cada borde tiene dos (o en hipergrafías, más) vértices a los que se adjunta, llamados sus puntos finales. Los bordes pueden ser dirigidos o no dirigidos; los bordes no dirigidos también se llaman líneas y los bordes dirigidos también se llaman arcos o flechas. En un gráfico simple no dirigido, un borde puede ser representado como el conjunto de sus vértices, y en un gráfico simple dirigido puede ser representado como un par ordenado de sus vértices. Un borde que conecta vértices $x$ y $Sí.$ a veces escrito $xy$ .
corte de borde: Un conjunto de bordes cuya eliminación desconecta el gráfico. Un corte de una sola punta se llama puente, istmo o borde cortado.
borde: El conjunto de bordes de un gráfico dado $G$ , a veces denotado $E () G)$ .
gráfico sin filo: El gráfico sin borde o el gráfico totalmente desconectado en un conjunto dado de vértices es el gráfico que no tiene bordes. A veces se llama el gráfico vacío, pero este término también puede referirse a un gráfico sin vértices.
incrustaciones: Una incrustación de gráficos es una representación topológica de un gráfico como subconjunto de un espacio topológico con cada vértice representado como punto, cada borde representado como una curva que tiene los puntos finales del borde como puntos finales de la curva, y ninguna otra intersección entre vértices o bordes. Un gráfico plano es un gráfico que tiene tal incrustación en el plano Euclideano, y un gráfico toroidal es un gráfico que tiene tal incrustación en un torus. El género de un gráfico es el género mínimo posible de un manifold bidimensional en el que puede ser incrustado.
gráfico vacío: 1. Un gráfico sin borde en un conjunto de vértices no vacío.; 2. El gráfico orden-cero, un gráfico sin vértices y sin bordes.
final: 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 infinitamente muchos vértices de ambos.
punto final: Uno de los dos vértices unidos por un borde dado, o uno del primer o último vértice de un paseo, sendero o camino. El primer punto final de un borde determinado se llama el cola y el segundo punto final se llama cabeza.
enumeración: La enumeración de gráficos es el problema de contar los gráficos en una determinada clase de gráficos, como función de su orden. Más generalmente, los problemas de enumeración pueden referirse a los problemas de contar una determinada clase de objetos combinatorios (como camarillas, conjuntos independientes, colorantes o azotes), o de enumerar algoritmomente todos esos objetos.
Eulerian: Un camino Eulerian es un paseo que utiliza cada borde de un gráfico exactamente una vez. Un circuito eulerio (también llamado ciclo eulerio o un recorrido por Euler) es un paseo cerrado que utiliza cada borde exactamente una vez. Un gráfico eulerio es un gráfico que tiene un circuito eulerio. Para un gráfico no dirigido, esto significa que el gráfico está conectado y cada vértice tiene incluso grado. Para un gráfico dirigido, esto significa que el gráfico está fuertemente conectado y cada vértice tiene en-degree igual a la salida. En algunos casos, el requisito de conectividad se afloja, y un gráfico que reúne sólo los requisitos de grado se llama Eulerian.
incluso: Divisible por dos; por ejemplo, un ciclo uniforme es un ciclo cuya longitud es incluso.
expander: Un gráfico de expansión es un gráfico cuya expansión del borde, expansión del vértice o expansión espectral está atado de cero.
expansión: 1. La expansión del borde, número isoperimétrico, o constante del Cheeger de un gráfico $G$ es la relación mínima, sobre subconjuntos $S$ de casi la mitad de los vértices $G$ , del número de bordes que salen $S$ al número de vértices en $S$ .; 2. La expansión del vértice, el número isoperimétrico del vértice o la magnificación de un gráfico $G$ es la relación mínima, sobre subconjuntos $S$ de casi la mitad de los vértices $G$ , del número de vértices fuera pero adyacente $S$ al número de vértices en $S$ .; 3. La expansión única vecina de un gráfico $G$ es la relación mínima, sobre subconjuntos de la mayor parte de los vértices de $G$ , del número de vértices fuera $S$ pero adyacente a un vertex único en $S$ al número de vértices en $S$ .; 4. La expansión espectral de un $d$ - Gráfico regular $G$ es la brecha espectral entre el mayor eigenvalue $d$ de su matriz de adyacencia y el segundo eigenvalue más grande.; 5. Una familia de gráficos ha atado la expansión si todo su $r$ - los menores de edad común tienen una relación de bordes a vértices ligados por una función de $r$ , y expansión polinómica si la función $r$ es un polinomio.

F

cara: En un gráfico plano o embedding gráfico, un componente conectado del subconjunto del plano o superficie de la incrustación que se descompone del gráfico. Para una incrustación en el plano, todo menos una cara será atada; la única cara excepcional que se extiende al infinito se llama la cara exterior.
factor: Un factor de un gráfico es un subgrafo que abarca: un subgrafo que incluye todos los vértices del gráfico. El término se utiliza principalmente en el contexto de subgrafos regulares: a $k$ -factor es un factor que es $k$ - irregular. En particular, a $1$ - el factor es lo mismo que una combinación perfecta. Un gráfico factor-crítico es un gráfico para el cual eliminar cualquier vértice produce un gráfico con un $1$ -factor.
factorización: Una factorización gráfica es una partición de los bordes del gráfico en factores; un $k$ -factorización es una partición en $k$ -factores. Por ejemplo, $1$ -factorización es un borde para colorear con la propiedad adicional que cada vértice es un incidente a un borde de cada color.
familia: Un sinónimo de clase.
finito: Un gráfico es finito si tiene un número finito de vértices y un número finito de bordes. Muchas fuentes suponen que todos los gráficos son finitos sin decirlo explícitamente. Un gráfico es localmente finito si cada vértice tiene un número finito de bordes de incidentes. Un gráfico infinito es un gráfico que no es finito: tiene infinitamente muchos vértices, infinitamente muchos bordes, o ambos.
primer orden: La primera lógica de orden de los gráficos es una forma de lógica en la que las variables representan vértices de un gráfico, y existe un predicado binario para probar si dos vértices están adyacentes. Para distinguirse de la lógica de segundo orden, en la que las variables también pueden representar conjuntos de vértices o bordes.
-flap: Para un conjunto de vértices $X$ , un $X$ -flap es un componente conectado del subgrafo inducido formado por eliminación $X$ . La terminología del solapamiento se utiliza comúnmente en el contexto de paraísos, funciones que mapean pequeños conjuntos de vértices a sus solapas. Vea también el puente de un ciclo, que es una solapa de los vértices del ciclo o un acorde del ciclo.
prohibido: Una caracterización gráfica prohibida es una caracterización de una familia de gráficos como los gráficos que no tienen ciertos otros gráficos como subgrafos, subgrafos inducidos o menores. Si $H$ es uno de los gráficos que no ocurre como subgrafo, subgrafo inducido o menor, entonces $H$ se dice que está prohibido.
forcing graph: Un gráfico forzando es un gráfico $H$ tales que evalúan la densidad del subgrafo $H$ en los gráficos de una secuencia gráfica $G(n)$ es suficiente para probar si esa secuencia es cuasi-aleatoria.
bosque: Un bosque es un gráfico no dirigido sin ciclos (una unión disyuntiva de árboles no arraigados), o un gráfico dirigido formado como una unión disyuntiva de árboles arraigados.
Frucht: 1. Robert Frucht; 2. El gráfico Frucht, uno de los dos gráficos cúbicos más pequeños sin simetrías no tripartitas.; 3. El teorema de Frucht de que cada grupo finito es el grupo de simetrías de un gráfico finito.
completo: Sinónimo de inducido.
gráfico funcional: Un gráfico funcional es un gráfico dirigido donde cada vértice tiene uno fuera de grado. Equivalentemente, un gráfico funcional es un pseudoforest dirigido maximalmente.

G

G: Una variable utilizada a menudo 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; vea la incrustación.
geodésica: Como sustantivo, un geodésico es un sinónimo para un camino más corto. Cuando se utiliza como adjetivo, significa relacionado con caminos más cortos o distancias más cortas.
gigante gigante: En la teoría de los gráficos aleatorios, un componente gigante es un componente conectado que contiene una fracción constante de los vértices del gráfico. En modelos estándar de gráficos aleatorios, normalmente hay en la mayoría de un componente gigante.
Girth: La circunferencia de un gráfico es la longitud de su ciclo más corto.
Gráfico: El objeto fundamental del estudio en la teoría gráfica, un sistema de vértices conectado en pares por bordes. A menudo subdividido en gráficos dirigidos o gráficos no dirigidos según si los bordes tienen una orientación o no. Los gráficos mixtos incluyen ambos tipos de bordes.
codicioso: Producido por un algoritmo codicioso. Por ejemplo, una coloración codicioso de un gráfico es un colorante producido por considerar los vértices en alguna secuencia y asignar cada vértice el primer color disponible.
Grötzsch: 1. Herbert Grötzsch; 2. El gráfico Grötzsch, el gráfico más pequeño sin triángulo que requiere cuatro colores en cualquier coloración adecuada.; 3. El teorema de Grötzsch que gráficos planar libres de triángulo siempre se puede colorear con la mayoría de tres colores.
Número de Grundy: 1. El número Grundy de un gráfico es el número máximo de colores producidos por un colorante codicioso, con un orden de vértice mal elegido.

H

H: Una variable utilizada a menudo para denotar un gráfico, especialmente cuando otro gráfico ya ha sido denotado por $G$ .
H-colorante: An $H$ -coloración de un gráfico $G$ (donde) $H$ es también un gráfico) es un homomorfismo de $H$ a $G$ .
H- libre: Un gráfico es $H$ - libre si no tiene un isomorfo subgrafo inducido a $H$ , eso es, si $H$ es un subgrafo inducido prohibido. El $H$ - grafitas libres son la familia de todos los gráficos (o, a menudo, todos los gráficos finitos) que son $H$ - libre. Por ejemplo, los gráficos libres de triángulo son los gráficos que no tienen un gráfico triángulo como subgrafo. La propiedad de ser $H$ - Libre es siempre hereditario. Un gráfico es $H$ - libre de menores si no tiene un isomorfo menor $H$ .
Hadwiger: 1. Hugo Hadwiger; 2. El número Hadwiger de un gráfico es el orden del menor completo más grande del gráfico. También se llama el número de camarilla de contracción o el grado de homomorfismo.; 3. La conjetura Hadwiger es la conjetura de que el número Hadwiger nunca es menor que el número cromático.
Hamiltonian: Un camino Hamiltoniano o el ciclo Hamiltoniano es un simple recorrido o simple ciclo de azotes: cubre todos los vértices del gráfico exactamente una vez. Un gráfico es Hamiltonian si contiene un ciclo Hamiltoniano, y rastreable si contiene un camino Hamiltoniano.
#: A $k$ -haven es una función que mapea cada conjunto $X$ de menos que $k$ vértices a uno de sus solapados, a menudo satisfaciendo condiciones adicionales de consistencia. El orden de un refugio es el número $k$ . Las Havens se pueden utilizar para caracterizar el ancho de árbol de gráficos finitos y los extremos y números Hadwiger de gráficos infinitos.
altura: 1. El altura de un nodo en un árbol arraigado es el número de bordes en un camino más largo, yendo lejos de la raíz (es decir, sus nodos tienen una profundidad estrictamente creciente), que comienza en ese nodo y termina en una hoja.; 2. El altura de un árbol arraigado es la altura de su raíz. Es decir, el altura de un árbol es el número de bordes en un camino más largo posible, lejos de la raíz, que comienza en la raíz y termina en una hoja.; 3. El altura de un gráfico acíclico dirigido es la longitud máxima de un camino dirigido en este gráfico.
hereditario: Una propiedad hereditaria de gráficos es una propiedad que se cierra bajo subgrafos inducidos: si $G$ tiene una propiedad hereditaria, entonces así debe cada subgrafo inducido de $G$ . Comparar monótono (cerrado bajo todos los subgrafos) o menor (cerrado bajo menores).
hexagon: Un ciclo simple compuesto de exactamente seis bordes y seis vértices.
agujero: Un agujero es un ciclo inducido de la longitud cuatro o más. Un agujero extraño es un agujero de longitud extraña. Un anti hoyo es un subgrafo inducido del orden cuatro cuyo complemento es un ciclo; equivalentemente, es un agujero en el gráfico de complemento. Esta terminología se utiliza principalmente en el contexto de gráficos perfectos, que se caracterizan por el teorema de gráficos perfecto fuerte como los gráficos sin agujeros extraños o anti-agujeros extraños. Los gráficos libres de agujeros son los mismos que los gráficos del coro.
homomorfa equivalencia: Dos gráficos son homomorficamente equivalentes si existen dos homomorfismos, uno de cada gráfico a otro gráfico.
homomorfismo: 1. Un homomorfismo gráfico es una cartografía del conjunto de vértice de un gráfico al conjunto de vértice de otro gráfico que mapea los vértices adyacentes a los vértices adyacentes. Este tipo de mapeo entre gráficos es el que se utiliza más comúnmente en los enfoques teóricos de categoría a la teoría del gráfico. Un colorante gráfico adecuado puede describirse como un homomorfismo a un gráfico completo.; 2. El grado de homomorfismo de un gráfico es un sinónimo para su Hadwiger number, el orden del menor de la camarilla más grande.
hiperarc: Un hiperedge dirigido que tiene una fuente y un conjunto de objetivos.
hiperedge: Un borde en un hipergrafo, teniendo cualquier número de puntos finales, en contraste con el requisito de que los bordes de los gráficos tienen exactamente dos puntos finales.
hipercube: Un gráfico hipercubo es un gráfico formado por los vértices y bordes de un hipercubo geométrico.
hipergrafía: Un hipergrafo es una generalización de un gráfico en el que cada borde (llamado hiperedge en este contexto) puede tener más de dos puntos finales.
hipo...: Este prefijo, en combinación con una propiedad gráfica, indica un gráfico que no tiene la propiedad pero tal que cada subgrafo formado por la eliminación de un solo vertex tiene la propiedad. Por ejemplo, un gráfico hipohamiltoniano es uno que no tiene un ciclo Hamiltoniano, pero para el cual cada eliminación de un solo vértigo produce un subgrafo Hamiltoniano. Compare crítica, utilizada para gráficos que tienen una propiedad pero para la cual cada eliminación de un solo vértigo no lo hace.

Did you mean:

IN

in-degree: El número de bordes entrantes en un gráfico dirigido; ver grado.
incidencia: Una incidencia en un gráfico es un par de vértice-edge tal que el vértice es un punto final del borde.
matriz de incidencia: La matriz de incidencia de un gráfico es una matriz cuyas filas están indexadas por vértices del gráfico, y cuyas columnas son indexadas por bordes, con una en la celda para fila $i$ y columna $j$ cuando vértice $i$ y borde $j$ son incidentes, y un cero de lo contrario.
incidente: La relación entre un borde y uno de sus puntos finales.
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 borde. También se puede llamar un conjunto estable o un coco. El número de independencia $α () G)$ es el tamaño del conjunto máximo independiente.; 2. En el materoide gráfico de un gráfico, un subconjunto de bordes es independiente si el subgrafo correspondiente es un árbol o bosque. En el esteroide bicircular, un subconjunto de bordes es independiente si el subgrafo correspondiente es un seudoforest.
indiferencia: Un gráfico de indiferencia es otro nombre para un gráfico de intervalo adecuado o gráfico de intervalo de unidad; ver apropiado.
inducida: Un subgrafo inducido o subgrafo completo de un gráfico es un subgrafo formado a partir de un subconjunto de vértices y de todos los bordes que tienen ambos puntos finales en el subconjunto. Los casos especiales incluyen caminos inducidos y ciclos inducidos, subgrafos inducidos que son caminos o ciclos.
inductivo: Sinónimo degenerado.
infinito: Un gráfico infinito es uno que no es finito; vea finito.
interna: 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 están internamente descompuestos (algunos lo llaman independiente) si no tienen ningún vértice en común, excepto los primeros y los últimos.
intersección: 1. La intersección de dos gráficos es su subgrafo común más grande, el gráfico formado por los vértices y bordes que pertenecen a ambos gráficos.; 2. Un gráfico de intersección es un gráfico cuyos vértices corresponden a conjuntos o objetos geométricos, con un borde entre dos vértices exactamente cuando los dos conjuntos o objetos correspondientes tienen una intersección no vacía. Varias clases de gráficos pueden definirse como los gráficos de intersección de ciertos tipos de objetos, por ejemplo los gráficos corales (grafos de intersección de los subárboles de un árbol), gráficos de círculo (grafos de intersección de acordes de un círculo), gráficos de intervalo (grafos de intersección de intervalos de una línea), gráficos de línea (grafos de intersección de los bordes de un gráfico), y camarillas). Cada gráfico es un gráfico de intersección para algunas familias de conjuntos, y esta familia se llama representación intersección del gráfico. El número de intersección de un gráfico $G$ es el número total mínimo de elementos en cualquier representación de intersección $G$ .
intervalo: 1. Un gráfico de intervalos es un gráfico de intersección de intervalos de una línea.; 2. El intervalo $[u, v]$ en un gráfico es la unión de todos los caminos más cortos de $u$ a $v$ .; 3. El espesor intervalor es un sinónimo para el ancho de ruta.
invariable: Un sinónimo de propiedad.
flecha invertida: Una flecha con dirección opuesta comparada con otra flecha. La flecha $() Sí., x)$ es la flecha invertida de la flecha $() x, Sí.)$ .
aislado: Un vértice aislado de un gráfico es un vértice cuyo grado es cero, es decir, un vértice sin bordes de incidentes.
isomorfo: Dos gráficos son isomorfos si hay un isomorfismo entre ellos; vea el isomorfismo.
isomorfismo: Un isomorfismo gráfico es una incidencia única que preserva la correspondencia de los vértices y bordes de un gráfico a los vértices y bordes de otro gráfico. Se dice que dos gráficos relacionados de esta manera son isomorfos.
isoperimétrica: Ver expansión.
isthmus: Sinónimo de puente, en el sentido de un borde cuya eliminación desconecta el gráfico.

K

K: Para la notación para gráficos completos, gráficos bipartitos completos, y gráficos multipartitos completos, ver completo.
κ: $κ () G)$ (utilizando la letra griega kappa) es el orden de la camarilla máxima en $G$ ; ver camarilla.
kernel: Un núcleo de un gráfico dirigido es un conjunto de vértices que es estable y absorbente.
nudo: Una sección ineludible de un gráfico dirigido. Ver nudo (matemática) y teoría de nudos.

I

L: $L () G)$ es el gráfico de línea $G$ ; ver línea.
etiqueta: 1. Información asociada a un vértice o borde de un gráfico. Un gráfico etiquetado es un gráfico cuyos vértices o bordes tienen etiquetas. Los términos vertex-labeled o borde etiquetado se puede utilizar para especificar qué objetos de un gráfico tienen etiquetas. El etiquetado de gráficos se refiere a varios problemas diferentes de asignar etiquetas a gráficos sujetos a ciertas limitaciones. Vea también para colorear gráfico, en el que las etiquetas se interpretan como colores.; 2. En el contexto de la enumeración del gráfico, se dice que los vértices de un gráfico se etiquetan si todos son distinguibles entre sí. Por ejemplo, esto se puede hacer para ser verdad arreglando una correspondencia de uno a uno entre los vértices y los enteros de 1 al orden del gráfico. Cuando se etiquetan los vértices, los gráficos que son isomorfos entre sí (pero con diferentes órdenes de vértice) se cuentan como objetos separados. En cambio, cuando los vértices no se etiquetan, los gráficos que son isomorfos entre sí no se cuentan por separado.
hoja: 1. Un vértice de hoja o un vértice colgante (especialmente en un árbol) es un vértice cuyo grado es $1$ . Un borde de hoja o borde colgante es el borde que conecta un vértice de hoja a su único vecino.; 2. Un poder de hoja de un árbol es un gráfico cuyos vértices son las hojas del árbol y cuyos bordes conectan hojas cuya distancia en el árbol es en la mayoría de un umbral dado.
longitud: En un gráfico no ponderado, la longitud de un ciclo, camino o caminata es el número de bordes que utiliza. En un gráfico ponderado, puede ser la suma de los pesos de los bordes que utiliza. La longitud se utiliza para definir el camino más corto, la circunferencia (longitud del ciclo más corto), y el camino más largo entre dos vértices en un gráfico.
nivel: 1. Este es el profundidad de un nodo más 1, aunque algunos lo definen en lugar de ser sinónimo de profundidad. El nivel de un nodo en un árbol arraigado es el número de nodos en el camino desde la raíz hasta el nodo. Por ejemplo, la raíz tiene el nivel 1 y cualquiera de sus nodos adyacentes tiene el nivel 2.; 2. Un conjunto de todos los nodos que tienen el mismo nivel o profundidad.
línea: Un sinónimo para un borde no dirigido. El gráfico de línea $L () G)$ de un gráfico $G$ es un gráfico con un vértice para cada borde de $G$ y un borde para cada par de bordes que comparten un punto final en $G$ .
vinculación: Un sinónimo de degeneración.
lista: 1. Una lista de adyacency es una representación computarizada de gráficos para uso en algoritmos gráficos.; 2. Para colorear lista es una variación de coloración de gráficos en la que cada vértice tiene una lista de colores disponibles.
local: Una propiedad local de un gráfico es una propiedad que se determina sólo por los barrios de los vértices en el gráfico. Por ejemplo, un gráfico es localmente finito si todos sus barrios son finitos.
bucle: Un bucle o auto-op es un borde ambos de cuyos puntos finales son el mismo vértice. Forma un ciclo de longitud $1$ . Estos no se permiten en gráficos simples.

M

magnificación: Sinónimo de expansión del vértice.
coincidente: Un emparejamiento es un conjunto de bordes en los que no dos comparten ningún vértice. Un vértice es igualado o saturado si es uno de los puntos finales de un borde en el emparejado. Una combinación perfecta o completa es un emparejamiento que coincide con cada vértice; también se puede llamar un factor 1 y sólo puede existir cuando el pedido es uniforme. Una coincidencia casi perfecta, en un gráfico con orden extraño, es una que satura todo menos un vértice. Un emparejamiento máximo es un emparejamiento que utiliza tantos bordes como sea posible; el número de emparejamiento $α . G)$ de un gráfico $G$ es el número de bordes en una combinación máxima. Un emparejamiento máximo es un emparejado al que no se pueden añadir bordes adicionales.
maximal: 1. Un subgrafo del gráfico dado $G$ es maximal para una propiedad particular si tiene esa propiedad pero no otro supergraph de ella que es también un subgraph de $G$ también tiene la misma propiedad. Es decir, es un elemento maximal de los subgrafos con la propiedad. Por ejemplo, una camarilla máxima es un subgrafo completo que no se puede ampliar a un subgrafo completo más grande. La palabra "maximal" debe distinguirse de "maximum": un subgrafo máximo es siempre maximal, pero no necesariamente viceversa.; 2. Un gráfico simple con una propiedad dada es maximal para esa propiedad si no es posible añadir más bordes a ella (mantener el vertex fijado sin cambios) preservando tanto la simplicidad del gráfico y la propiedad. Así, por ejemplo, un gráfico planar maximal es un gráfico plano tal que añadir más bordes a él crearía un gráfico no plano.
máximo: Un subgrafo de un gráfico dado $G$ es máximo para una propiedad particular si es el subgrafo más grande (por orden o tamaño) entre todos los subgrafos con esa propiedad. Por ejemplo, una camarilla máxima es cualquiera de las camarillas más grandes de un gráfico dado.
mediana: 1. Una mediana de un triple de vértices, un vértice que pertenece a caminos más cortos entre todos los pares de vértices, especialmente en gráficos medianos y gráficos modulares.; 2. Un gráfico medio es un gráfico en el que cada tres vértices tienen una mediana única.
Meyniel: 1. Henri Meyniel, teórico francés.; 2. Un gráfico Meyniel es un gráfico en el que cada ciclo extraño de la longitud cinco o más tiene al menos dos acordes.
mínimo: Un subgrafo del gráfico dado es mínimo para una propiedad particular si tiene esa propiedad pero ningún subgrafo adecuado de ella también tiene la misma propiedad. Es decir, es un elemento mínimo de los subgrafos con la propiedad.
mínimo: Un corte cuyo conjunto de corte tiene un peso total mínimo, posiblemente restringido a cortes que separan un par designado de vértices; se caracterizan por el termorema de corte máx.
menor: Un gráfico $H$ es un menor de otro gráfico $G$ si $H$ puede obtenerse eliminando bordes o vértices de $G$ y los bordes contratantes en $G$ . Es un menor poco menor si puede ser formado como menor de tal manera que los subgrafos de $G$ que fueron contratados para formar vértices de $H$ todos tienen pequeño diámetro. $H$ es un menor topológico $G$ si $G$ tiene un subgrafo que es una subdivisión $H$ . Un gráfico es $H$ - libre de menores si no tiene $H$ como menor. Una familia de grafitos es menor si está cerrada bajo menores; el teorema Robertson-Seymour caracteriza a las familias menores de edad que tienen un conjunto finito de menores prohibidos.
mixto: Un gráfico mixto es un gráfico que puede incluir bordes dirigidos y no dirigidos.
modulares: 1. Gráfico modular, un gráfico en el que cada triple de vértices tiene al menos un vértice mediano que pertenece a caminos más cortos entre todos los pares del triple.; 2. Descomposición modular, una descomposición de un gráfico en subgrafos dentro de los cuales todos los vértices se conectan al resto del gráfico de la misma manera.; 3. Modularidad de una agrupación de gráficos, la diferencia del número de bordes transversales de su valor esperado.
monotone: Una propiedad monotona de grafitos es una propiedad que se cierra bajo subgrafos: si $G$ tiene una propiedad hereditaria, entonces así debe cada subgrafo de $G$ . Comparar hereditario (cerrado bajo subgrafos inducidos) o menor (cerrado bajo menores).
Gráfico de Moore: Un gráfico de Moore es un gráfico regular para el cual el límite de Moore se conoce exactamente. El límite de Moore es una desigualdad relacionada con el grado, el diámetro y el orden de un gráfico, probado por Edward F. Moore. Cada gráfico de Moore es una jaula.
multigrafo: Un multigrafo es un gráfico que permite múltiples adyacencias (y, a menudo, self-loops); un gráfico que no se requiere para ser simple.
múltiples adjacency: Una adyacencia múltiple o borde múltiple es un conjunto de más de un borde que todos tienen los mismos puntos finales (en la misma dirección, en el caso de gráficos dirigidos). A menudo se llama un gráfico con múltiples bordes.
multiplicidad: La multiplicidad de un borde es el número de bordes en una adyacencia múltiple. La multiplicidad de un gráfico es la máxima multiplicidad de cualquiera de sus bordes.

Did you mean:

AND

N: 1. Para la notación de barrios abiertos y cerrados, vea el barrio.; 2. Una maleta inferior $n$ a menudo se utiliza (especialmente en la informática) para denotar el número de vértices en un gráfico dado.
vecino
vecino: Un vértice adyacente a un vértice dado.
Barrio
barrio: El barrio abierto (o barrio) de un vértice $v$ es el subgrafo inducido por todos los vértices que están adyacentes a $v$ . El barrio cerrado se define de la misma manera, pero también incluye $v$ en sí mismo. El barrio abierto $v$ dentro $G$ puede ser denotado $N G () v)$ o $N () v)$ , y el barrio cerrado puede ser denotado $N G [v]$ o $N [v]$ . Cuando no se especifica la apertura o cercanía de un barrio, se supone que está abierto.
red: Un gráfico en el que los atributos (por ejemplo, nombres) están asociados con los nodos y/o bordes.
nodos: Un sinónimo de vértice.
non-edge: Un no-edge o anti-edge es un par de vértices que no están adyacentes; los bordes del gráfico de complemento.
null graph: Ver gráfico vacío.

Did you mean: <h2O

extraño: 1. Un ciclo extraño es un ciclo cuya longitud es extraña. La circunferencia extraña de un gráfico no bipartito es la longitud de su ciclo más corto. Un agujero extraño es un caso especial de un ciclo extraño: uno que es inducido y tiene cuatro o más vértices.; 2. Un vértice extraño es un vértice cuyo grado es extraño. Por el apretón de manos lemma cada gráfico undirecto finito tiene un número uniforme de vértices extraños.; 3. Un oído extraño es un camino simple o ciclo simple con un número impar de bordes, usado en descomposiciones auditivas impares de gráficos factor-críticos; vea el oído.; 4. Un acorde extraño es un borde que conecta dos vértices que son una distancia extraña en un ciclo uniforme. Los acordes extraños se utilizan para definir gráficos fuertemente coral.; 5. Un gráfico extraño es un caso especial de un gráfico Kneser, teniendo un vértice para cada uno $() n -1)$ -element subset of a $(22) n -1)$ -element set, y un borde que conecta dos subsets cuando sus conjuntos correspondientes están descompuestos.
abierto: 1. Vean el vecindario.; 2. Ve a caminar.
orden: 1. El orden de un gráfico $G$ es el número de sus vértices, $Silencio V () G)$ . La variable $n$ a menudo se utiliza para esta cantidad. Ver también tamaño, el número de bordes.; 2. Un tipo de lógica de gráficos; ver el primer orden y el segundo orden.; 3. Un orden o pedido de un gráfico es un arreglo de sus vértices en una secuencia, especialmente en el contexto del orden topológico (un orden de un gráfico acíclico dirigido en el que cada borde pasa de un vértice anterior a un vértice posterior en el orden) y degeneración ordenando (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 remanso o bramble, vea el remanso y el freno.
orientación
orientada: 1. Una orientación de un gráfico no dirigido es una asignación de direcciones a sus bordes, convirtiéndolo en un gráfico dirigido. Un gráfico orientado es uno que ha sido asignado una orientación. Así, por ejemplo, un polígono es un árbol orientado; difiere de un árbol dirigido (una arborescencia) en que no hay necesidad de consistencia en las direcciones de sus bordes. Otros tipos especiales de orientación incluyen torneos, orientaciones de gráficos completos; orientaciones fuertes, orientaciones que están fuertemente conectadas; orientaciones acíclicas, orientaciones que son acíclicas; orientaciones eulerias, orientaciones que son eulerias; y orientaciones transitivas, orientaciones que se cierran transitivamente.; 2. Gráfico orientado, utilizado por algunos autores como sinónimo de un gráfico dirigido.
fuera de acuerdo: Ver grado.
exterior: Mira la cara.
exterior: Un gráfico exterior plano es un gráfico que puede ser incrustado en el plano (sin cruces) para que todos los vértices estén en la cara exterior del gráfico.

P

padre: En un árbol arraigado, un padre de un vértice $v$ es un vecino $v$ a lo largo del borde entrante, el que está dirigido hacia la raíz.
sendero: Un camino puede ser un paseo o un paseo sin vertices repetidos y consecuentemente bordes (también llamado un camino simple), dependiendo de la fuente. Los casos especiales importantes incluyen caminos inducidos y caminos más cortos.
ruta de descomposición: Un camino descomposición de un gráfico $G$ es una descomposición de árboles cuyo árbol subyacente es un camino. Su ancho se define de la misma manera que para descomposiciones de árboles, como uno menos que el tamaño de la bolsa más grande. El ancho mínimo de cualquier camino descomposición de $G$ es el ancho de camino $G$ .
Camino: El ancho de camino de un gráfico $G$ es el ancho mínimo de una ruta de descomposición de $G$ . También puede definirse en términos del número de camarillas de un intervalo de terminación $G$ . Siempre está entre el ancho de banda y el ancho de árbol $G$ . También se conoce como espesor de intervalo, número de separación del vértice o número de búsqueda de nodos.
colgante: Ver hoja.
perfecto: 1. Un gráfico perfecto es un gráfico en el que, en cada subgrafo inducido, el número cromático es igual al número de camarilla. El teorema de grafito perfecto y fuerte teorema de grafito perfecto son dos teoremas sobre gráficos perfectos, la primera prueba de que sus complementos también son perfectos y la última prueba de que son exactamente los gráficos sin agujeros extraños o anti-agujeros.; 2. Un gráfico perfectamente ordenable es un gráfico cuyos vértices se pueden ordenar de tal manera que un algoritmo de color avaricioso con este orden de colores óptimos cada subgrafo inducido. Los gráficos perfectamente ordenables son una subclase de los gráficos perfectos.; 3. Un emparejamiento perfecto es un emparejamiento que satura cada vértice; ver coincidencia.; 4. Una perfecta 1-factorización es una partición de los bordes de un gráfico en perfectos emparejamientos para que cada dos emparejamientos formen un ciclo Hamiltoniano.
periférico: 1. Un ciclo periférico o ciclo no separador es un ciclo con la mayoría de un puente.; 2. Un vértice periférico es un vértice cuya excentricidad es máxima. En un árbol, esto debe ser una hoja.
Petersen: 1. Julius Petersen (1839-1910), teórico grafico danés.; 2. El gráfico Petersen, un gráfico de 15 m de 10 vértices usado frecuentemente como contraejemplo.; 3. El teorema de Petersen de que cada gráfico cúbico sin puente tiene una combinación perfecta.
planar: Un gráfico plano es un gráfico que tiene una incrustación en el plano Euclideano. Un gráfico plano es un gráfico planar para el cual ya se ha fijado una codificación particular. A $k$ - el gráfico plano es uno que se puede dibujar en el plano con $k$ cruces por borde.
polytree: Un polígono es un árbol orientado; equivalentemente, un gráfico acíclico dirigido cuyo gráfico no dirigido subyacente es un árbol.
poder: 1. Un poder gráfico $G k$ de un gráfico $G$ es otro gráfico en el mismo conjunto de vértice; dos vértices están adyacentes $G k$ cuando están a distancia en la mayoría $k$ dentro $G$ . Un poder de hoja es un concepto estrechamente relacionado, derivado de un poder de un árbol tomando el subgrafo inducido por las hojas del árbol.; 2. El análisis de gráficos de potencia es un método para analizar redes complejas identificando camarillas, bicliques y estrellas dentro de la red.; 3. Las leyes de poder en las distribuciones de grado de las redes libres de escala son un fenómeno en el que el número de vértices de un grado determinado es proporcional a un poder del grado.
predecesor: Un vértice viniendo antes de un vértice dado en un camino dirigido.
apropiado: 1. Un subgrafo adecuado es un subgrafo que elimina al menos un vértice o borde relativo a todo el gráfico; para gráficos finitos, subgrafos apropiados nunca son isomorfos a todo el gráfico, pero para gráficos infinitos pueden ser.; 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 borde; vea el color.; 3. Un gráfico de intervalo adecuado o gráfico de arco circular adecuado es un gráfico de intersección de una colección de intervalos o arcos circulares (respectivamente) de tal manera que ningún intervalo o arco contiene otro intervalo o arco. Los gráficos de intervalo adecuado también se llaman gráficos de intervalo de unidad (porque siempre pueden ser representados por intervalos de unidad) o gráficos de indiferencia.
propiedad: Una propiedad gráfica es algo que puede ser verdad de algunos gráficos y falsos de otros, y eso depende sólo de la estructura gráfica y no de información incidental como etiquetas. Las propiedades de los Gráficos pueden describirse equivalentemente en términos de clases de gráficos (los gráficos que tienen una propiedad dada). Más generalmente, una propiedad gráfica también puede ser una función de gráficos que es de nuevo independiente de la información incidental, como el tamaño, orden o secuencia de grado de un gráfico; esta definición más general de una propiedad también se llama invariante del gráfico.
pseudoforestación: Un pseudoforest es un gráfico no dirigido en el que cada componente conectado tiene a la mayoría de un ciclo, o un gráfico dirigido en el que cada vértice tiene a la mayoría de un borde saliente.
pseudograph: Un seudografo es un gráfico o multigrafo que permite auto-ops.

P

gráfico cuasi-line: Un gráfico cuasi-line o gráfico co-bipartito local es un gráfico en el que el barrio abierto de cada vértice se puede dividir en dos camarillas. Estos gráficos son siempre libres de garras y incluyen como un caso especial los gráficos de la línea. Se utilizan en la teoría de la estructura de gráficos libres de garras.
secuencia de gráficos cuasi rara: Una secuencia de gráficos de cuasi rara vez es una secuencia de gráficos que comparte varias propiedades con una secuencia de gráficos aleatorios generados según el modelo de gráfico aleatorio Erdős–Rényi.
Quinto: Un quiver es un multigrafo dirigido, como se utiliza en la teoría de la categoría. Los bordes de un perchero se llaman flechas.

Did you mean: <h2R

radio: El radio de un gráfico es la excentricidad mínima de cualquier vértice.
Ramanujan: Un gráfico Ramanujan es un gráfico cuya expansión espectral es lo más grande posible. Es decir, es un $d$ -grafo regular, tal que el segundo eigenvalue más grande de su matriz de adyacency es en la mayoría $2sqrt{d-1}$ .
Rayo: Un rayo, en un gráfico infinito, es un camino infinito simple con exactamente un punto final. Los extremos de un gráfico son clases de equivalencia de rayos.
alcanzabilidad: La capacidad de llegar de un vértice a otro dentro de un gráfico.
accesible: Tiene una posibilidad afirmativa. Un vértice $Sí.$ se dice que es accesible desde un vértice $x$ si existe un camino desde $x$ a $Sí.$ .
reconocible: En el contexto de la conjetura de reconstrucción, una propiedad gráfica es reconocible si su verdad se puede determinar desde la cubierta del gráfico. Se sabe que muchas propiedades graficas son reconocibles. Si la conjetura de reconstrucción es verdadera, todas las propiedades gráficas son reconocibles.
reconstrucción: La conjetura de reconstrucción establece que cada gráfico no dirigido $G$ está determinado por su cubierta, un multiset de gráficos formado por la eliminación de un vértice de $G$ de todas las maneras posibles. En este contexto, la reconstrucción es la formación de un gráfico desde su cubierta.
rectángulo: Un ciclo simple compuesto de exactamente cuatro bordes y cuatro vértices.
ordinario: Un gráfico es $d$ -regular cuando todos sus vértices tienen grado $d$ . Un gráfico regular es un gráfico que es $d$ - regular para algunos $d$ .
torneo regular: Un torneo regular es un torneo donde el in-degree es igual a la salida para todos los vértices.
inversión: Ver transposición.
root: 1. Un vértice designado en un gráfico, especialmente en árboles dirigidos y gráficos arraigados.; 2. La operación inversa a una potencia gráfica: a $k$ raíz de un gráfico $G$ es otro gráfico en el mismo vertex conjunto tal que dos vértices están adyacentes $G$ si y sólo si tienen distancia a la mayoría $k$ en la raíz.

S

saturada: A ver si coinciden.
Número de búsqueda: El número de búsqueda de ganglios es un sinónimo de sinceridad.
segunda orden: La segunda lógica de orden de los gráficos es una forma de lógica en la que las variables pueden representar vértices, bordes, conjuntos de vértices, y (a veces) conjuntos de bordes. Esta lógica incluye predicas para probar si un vértice y borde son incidentes, así como si un vértice o borde pertenece a un conjunto. Para distinguirse de la lógica de primer orden, en la que las variables sólo pueden representar vértices.
self-loop: Sinónimo de bucle.
separando el vértice: Véase el punto de articulación.
Número de separación: El número de separación de Vertex es un sinónimo de progreso.
hermano: En un árbol arraigado, un hermano de un vértice $v$ es un vértice que tiene el mismo vértice padre que $v$ .
simple: 1. Un gráfico simple es un gráfico sin bucles y sin múltiples adjacencies. Es decir, cada borde conecta dos puntos finales distintos y no hay dos bordes con los mismos puntos finales. Un borde simple es un borde que no es parte de una adyacencia múltiple. En muchos casos, se supone que los gráficos son simples a menos que se especifique lo contrario.; 2. Un camino simple o un ciclo simple es un camino o ciclo que no tiene vértices repetidos y por lo tanto no hay bordes repetidos.
fregadero: Un lavabo, en un gráfico dirigido, es un vértice sin bordes salientes (fuera de grado 0).
tamaño: El tamaño de un gráfico $G$ es el número de sus bordes, $Silencio E () G)$ . La variable $m$ a menudo se utiliza para esta cantidad. Véase también orden, el número de vértices.
pequeña red mundial: Una red de pequeño mundo es un gráfico en el que la mayoría de los nodos no son vecinos unos de otros, pero la mayoría de los nodos pueden ser alcanzados por un pequeño número de saltos o pasos. Específicamente, una red de pequeño mundo se define como un gráfico donde la distancia típica L entre dos nodos elegidos al azar (el número de pasos requerido) crece proporcionalmente al logaritmo del número de nodos N en la red
Snark: Un snark es un simple, conectado, gráfico cúbico sin puente con índice cromático igual a 4.
fuente: Una fuente, en un gráfico dirigido, es un vértice sin bordes entrantes (en grado equivale a 0).
espacio: En la teoría del gráfico algebraico, varios espacios vectoriales sobre el campo binario pueden estar asociados con un gráfico. Cada uno tiene conjuntos de bordes o vértices para sus vectores, y diferencia simétrica de conjuntos como su operación suma vectorial. El espacio del borde es el espacio de todos los conjuntos de bordes, y el espacio del vértice es el espacio de todos los conjuntos de vértices. El espacio de corte es un subespacio del espacio de borde que tiene los conjuntos de corte del gráfico como sus elementos. El espacio del ciclo tiene los subgrafos Eulerian abarcando como sus elementos.
spanner: Un spanner es un gráfico (usualmente escaso) cuyo camino más corto distancia aproxima los de un gráfico denso u otro espacio métrico. Las variaciones incluyen nalgas geométricas, grafitas cuyos vértices son puntos en un espacio geométrico; nalgas de árboles, que abarcan árboles de un gráfico cuyas distancias aproximan las distancias del gráfico, y nalgas de gráficos, subgrafos escasos de un gráfico denso cuyas distancias aproximan las distancias del gráfico original. Una nalgada codicioso es un grafito construido por un algoritmo codicioso, generalmente uno que considera todos los bordes de lo más corto a largo y mantiene los que son necesarios para preservar la distancia aproximación.
lapso: Un subgrafo se extiende cuando incluye todos los vértices del gráfico dado. Los casos importantes incluyen árboles de azotes, subgrafos que son árboles, y emparejamientos perfectos, subgrafos que azotan. También se puede llamar un subgrafo que abarca un factor, especialmente (pero no sólo) cuando es regular.
escasa: Un gráfico escaso es uno que tiene pocos bordes relativos a su número de vértices. En algunas definiciones, la misma propiedad también debe ser verdadera para todos los subgrafos del gráfico dado.
espectral
espectro espectro espectro espectro espectro espectro espectro espectro espectro espectro espectro espectro espectro espectro: El espectro de un gráfico es la colección de eigenvalues de su matriz de adyacency. La teoría del gráfico espectral es la rama de la teoría del gráfico que utiliza espectros para analizar gráficos. Vea también expansión espectral.
división: 1. Un gráfico dividido es un gráfico cuyos vértices se pueden dividir en una camarilla y un conjunto independiente. Una clase de gráficos relacionados, los gráficos de doble división, se utilizan en la prueba del teorema de gráficos perfecto fuerte.; 2. Una división de un gráfico arbitrario es una partición de sus vértices en dos subconjuntos no vacíos, de tal manera que los bordes que abarcan este corte forman un subgrafo bipartito completo. Las divisiones de un gráfico pueden ser representadas por una estructura de árboles llamada su descomposición. Una división se llama una fuerte división cuando no es cruzada por ninguna otra división. Una división se llama notrivial cuando ambos lados tienen más de un vértice. Un gráfico se llama primo cuando no tiene divisiones notriviales.
cuadrado: 1. El cuadrado de un gráfico $G$ es el poder gráfico $G 2$ ; en la otra dirección, $G$ es la raíz cuadrada $G 2$ . El medio cuadrado de un gráfico bipartito es el subgrafo de su cuadrado inducido por un lado de la bipartición.; 2. Un gráfico es un gráfico plano que se puede dibujar para que todas las caras atadas sean de 4 ciclos y todos los vértices de grado ≤ 3 pertenecen a la cara exterior.; 3. Un gráfico de cuadrícula cuadrada es un gráfico de celo definido a partir de puntos en el plano con coordenadas entero conectadas por bordes de longitud unitaria.
estable: Un conjunto estable es un sinónimo para un conjunto independiente.
estrella: Una estrella es un árbol con un vértice interno; equivalentemente, es un gráfico bipartito completo $K 1, n$ para algunos $n \geq 2$ . El caso especial de una estrella con tres hojas se llama garra.
fuerza: La fuerza de un gráfico es la relación mínima del número de bordes eliminados del gráfico a los componentes creados, sobre todas las posibles absorciones; es análoga a la dureza, basado en absorciones de vértice.
fuerte: 1. Para una conectividad fuerte y componentes fuertemente conectados de gráficos dirigidos, vea conectado y componente. Una orientación fuerte es una orientación fuertemente conectada; vea la orientación.; 2. Para el teorema de gráficos perfecto fuerte, vea perfecto.; 3. Un gráfico muy 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 gráfico del coro es un gráfico del coro en el que cada ciclo de la longitud seis o más tiene un acorde extraño.; 5. Un gráfico muy perfecto es un gráfico en el que cada subgrafo inducido tiene un conjunto independiente que reúne todas las camarillas máximas. Los gráficos de Meyniel también se llaman "grafos muy perfectos" porque en ellos, cada vértice pertenece a un conjunto tan independiente.
subforestación: Un subgrafo de un bosque.
subgraph: Un subgrafo de un gráfico $G$ es otro gráfico formado a partir de un subconjunto de los vértices y bordes de $G$ . El subconjunto del vértice debe incluir todos los puntos finales del subconjunto del borde, pero también puede incluir vértices adicionales. Un subgrafo es uno que incluye todos los vértices del gráfico; un subgrafo inducido es uno que incluye todos los bordes cuyos puntos finales pertenecen al subconjunto del vértice.
subtree: Un subárbol es un subgrafo conectado de un árbol. A veces, para árboles enraizados, los subárboles se definen como un tipo especial de subgrafo conectado, formado por todos los vértices y bordes alcanzables desde un vértice elegido.
sucesor: Un vértice viniendo después de un vértice dado en un camino dirigido.
superconcentrador: Un superconcentrador es un gráfico con dos subconjuntos designados e iguales de vértices $I$ y $O$ , tal que por cada dos subconjuntos de tamaño igual $S$ de $I$ y $T$ $O$ existe una familia de caminos descomunales que conectan cada vértice en $S$ a un vértice en $T$ . Algunas fuentes requieren además que un superconcentrador sea un gráfico acíclico dirigido, con $I$ como sus fuentes y $O$ como sus sumideros.
supergraph: Un gráfico formado por añadir vértices, bordes, o ambos a un gráfico dado. Si $H$ es un subgrafo de $G$ , entonces $G$ es un supergraph de $H$ .

T

theta: 1. Un gráfico Theta es la unión de tres caminos descomunados internamente (simple) que tienen los mismos dos vértices finales distintos.; 2. El gráfico Theta de una colección de puntos en el plano Euclidean se construye mediante la construcción de un sistema de conos que rodea cada punto y la adición de un borde por cono, al punto cuya proyección sobre un rayo central del cono es más pequeña.; 3. El número Lovász o la función Lovász theta de un gráfico es un invariante gráfico relacionado con el número de camarilla y el número cromático que se puede computar en tiempo polinomio por programación semidefinida.
Gráfico de Thomsen: El gráfico Thomsen es un nombre para el gráfico bipartito completo $K_{3,3}$ .
topológica: 1. Un gráfico topológico es una representación de los vértices y bordes de un gráfico por puntos y curvas en el plano (no necesariamente evitando cruces).; 2. Teoría del gráfico topológico es el estudio de las incrustaciones del gráfico.; 3. La clasificación topológica es el problema algorítmico de organizar un gráfico acíclico dirigido en un orden topológico, una secuencia de vértice tal que cada borde pasa de un vértice anterior a un vértice posterior en la secuencia.
totalmente desconectado: Sinónimo sin filo.
Tour: Un sendero cerrado, un paseo que comienza y termina en el mismo vértice y no tiene bordes repetidos. Los tours de Euler son tours que utilizan todos los bordes del gráfico; vea Eulerian.
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 un borde dirigido (ir en sólo una de las dos direcciones entre los dos vértices).
trazable: Un gráfico trazable es un gráfico que contiene un camino Hamiltoniano.
sendero: Un paseo sin bordes repetidos.
transitoria: Tener que ver con la propiedad transitiva. El cierre transitivo de un gráfico dirigido dado es un gráfico en el mismo conjunto de vértice que tiene un borde de un vértice a otro cuando el gráfico original tiene un camino que conecta los mismos dos vértices. Una reducción transitiva de un gráfico es un gráfico mínimo que tiene el mismo cierre transitivo; los gráficos acíclicos dirigidos tienen una reducción transitiva única. Una orientación transitiva es una orientación de un gráfico que es su propio cierre transitivo; sólo existe para gráficos de comparabilidad.
transpose: El gráfico transpose de un gráfico dirigido dado es un gráfico en los mismos vértices, con cada borde revertido en dirección. También se puede llamar el converso o reverso del gráfico.
árbol: 1. Un árbol es un gráfico no dirigido que está conectado y acíclico, o un gráfico dirigido en el que existe un paseo único de un vértice (la raíz del árbol) a todos los vértices restantes.; 2. Un árbol de k es un gráfico formado por cola $() k + 1)$ -cliques juntos en común $k$ -cliques. Un árbol en el sentido ordinario es un $1$ - Árbol según esta definición.
árbol de la descomposición: Un árbol descomposición de un gráfico $G$ es un árbol cuyos nodos son etiquetados con conjuntos de vértices $G$ ; estos juegos se llaman bolsas. Para cada vértice $v$ , las bolsas que contienen $v$ debe inducir un subárbol del árbol, y para cada borde $uv$ debe existir una bolsa que contenga ambos $u$ y $v$ . El ancho de una descomposición de árboles es uno menos que el número máximo de vértices en cualquiera de sus bolsas; el ancho de árbol de $G$ es el ancho mínimo de cualquier descomposición de árboles $G$ .
arbolado: El ancho de árbol de un gráfico $G$ es el ancho mínimo de una descomposición de árboles $G$ . También se puede definir en términos del número de camarillas de una terminación del coro $G$ , el orden de un remanso de $G$ , o el orden de un bramble de $G$ .
triángulo: Un ciclo de longitud tres en un gráfico. Un gráfico sin triángulo es un gráfico no dirigido que no tiene subgrafos de triángulo.
trivial: Un gráfico trivial es un gráfico con 0 o 1 vértices. Un gráfico con 0 vértices también se llama gráfico nulo.
Turán: 1. Pál Turán; 2. Un gráfico Turán es un gráfico multipartito equilibrado.; 3. El teorema de Turán afirma que los gráficos de Turán tienen el máximo número de bordes entre todos los gráficos libres de camarillas de una orden dada.; 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 gráfico bipartito completo.

U

unry vertex: En un árbol arraigado, un vértice unitario es un vértice que tiene exactamente un niño vértice.
no redirigido: Un gráfico no dirigido es un gráfico en el que los dos puntos finales de cada borde no se distinguen entre sí. Véase también Dirigida y mixto. En un gráfico mixto, un borde no dirigido es otra vez uno en el que los puntos finales no se distinguen entre sí.
uniforme: Un hipergrafo $k$ -uniforme cuando todos sus bordes tienen $k$ endpoints, y uniforme cuando es $k$ -uniforme para algunos $k$ . Por ejemplo, los gráficos ordinarios son los mismos $2$ - Hipergrafías uniformes.
universal: 1. Un gráfico universal es un gráfico que contiene como subgrafos todos los gráficos en una familia determinada de gráficos, o todos los gráficos de un tamaño o orden dado dentro de una familia determinada de gráficos.; 2. Un vértice universal (también llamado un ápice o vértice dominante) es un vértice que está adyacente a cada otro vértice en el 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 los gráficos, un vértice que está universalmente cuantificado en una fórmula puede ser llamado un vértice universal para esa fórmula.
gráfico no ponderado: Un gráfico cuyos vértices y bordes no han sido asignados pesos; lo contrario de un gráfico ponderado.
gráfico de utilidad: El gráfico de utilidad es un nombre para el gráfico bipartito completo $K_{3,3}$ .

v

V: See vertex set.
valenciano: Sinónimo para grado.
vertex: Un vértice (vertices plurales) es (junto con bordes) una de las dos unidades básicas de las cuales se construyen gráficos. Los gráficos a menudo se consideran objetos atómicos, sin estructura interna.
corte de vértice
conjunto de separación: Un conjunto de vértices cuya eliminación desconecta el gráfico. Un corte de un solo vértice se llama punto de articulación o vértice cortado.
vertex set: El conjunto de vértices de un gráfico dado $G$ , a veces denotado $V () G)$ .
vertices: See vertex.
Vizing: 1. Vadim G. Vizing; 2. Teorema de Vizing que el índice cromático es en la mayoría de un grado más que el máximo.; 3. La conjetura de Vizing sobre el número de dominio de los productos cartesianos de los gráficos.
volumen: La suma de los grados de un conjunto de vértices.

W

$W$: La carta $W$ se utiliza en notación para gráficos de rueda y gráficos de molino de viento. La notación no está estandarizada.
Wagner: 1. Klaus Wagner; 2. El gráfico Wagner, una escalera Möbius de ocho vértigos.; 3. El teorema de Wagner caracterizando gráficas planas por sus menores prohibidos.; 4. El teorema de Wagner caracterizando el $K 5$ -grafos libres de menores.
caminar: Un paseo es una secuencia finita o infinita de bordes que une una secuencia de vértices. Los paseos también se llaman a veces cadenas. Un paseo abierto si sus primeros y últimos vértices son distintos, y cerrado si se repiten.
débilmente conectado: Un gráfico dirigido se llama débilmente conectado si reemplazar todos sus bordes dirigidos por bordes no redirigidos produce un gráfico conectado (sin dirección).
peso: Un valor numérico, asignado como etiqueta a un vértice o borde de un gráfico. El peso de un subgrafo es la suma de los pesos de los vértices o bordes dentro de ese subgrafo.
Gráfico ponderado: Un gráfico cuyos vértices o bordes han sido asignados pesos. Un gráfico con peso de vértice tiene pesos en sus vértices y un gráfico con peso al borde tiene pesos en sus bordes.
bien coloreado: Un gráfico bien coloreado es un gráfico cuyos colores codiciosos usan el mismo número de colores.
bien cubierto: Un gráfico bien cubierto es un gráfico todos cuyos conjuntos máximo independientes son del mismo tamaño.
rueda: Un gráfico de rueda es un gráfico formado por añadir un vértice universal a un ciclo simple.
ancho: 1. Un sinónimo de degeneración.; 2. Para otros invariantes graficos conocidos como ancho, vea ancho de banda, ancho de rama, ancho de cama, ancho de camino y ancho de árbol.; 3. El ancho de una descomposición de árboles o descomposición de caminos es uno menos que el tamaño máximo de una de sus bolsas, y puede ser utilizado para definir el ancho de árbol y el ancho de ruta.; 4. El ancho de un gráfico acíclico dirigido es la máxima cardinalidad de un antichain.
molino de viento: Un gráfico de molino de viento es la unión de una colección de camarillas, todo el mismo orden que el otro, con un vértice compartido perteneciente a todas las camarillas y todos los otros vértices y bordes distintos.

Contenido relacionado

Más resultados...