Glosario de la teoría de grafos

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.

Simbolos

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

A

absorbenteUn conjunto absorbente de un grafo dirigido es un conjunto de vértices tales que para cualquier vértice hay una arista de hacia un vértice de .acromáticoEl número acromático de un gráfico es el número máximo de colores en una coloración completa.acíclico1. 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 dirigido acíclico, que es un dígrafo sin ciclos dirigidos, a menudo se denomina gráfico acíclico dirigido, especialmente en informática.2. Una coloración acíclica de un gráfico no dirigido es una coloración adecuada en la que cada dos clases de color inducen un bosque.matriz de adyacenciaLa matriz de adyacencia de un gráfico es una matriz cuyas filas y columnas están indexadas por vértices del gráfico, con un uno en la celda para la fila i y la columna j cuando los vértices i y j son adyacentes, y un cero en caso contrario.adyacente1. La relación entre dos vértices que son ambos extremos de la misma arista.2. La relación entre dos aristas distintas que comparten un vértice final.αPara un gráfico G, α (G) (usando la letra griega alpha) es su número de independencia (ver independiente), y α ′(G) es su número correspondiente (ver coincidencia).alternoEn un gráfico con coincidencia, una ruta alterna es una ruta cuyos bordes alternan entre bordes coincidentes y no coincidentes. Un ciclo alterno es, de manera similar, un ciclo cuyos bordes alternan entre bordes coincidentes y no coincidentes. Un camino de aumento es un camino alterno que comienza y termina en vértices no saturados. Se puede encontrar una coincidencia más grande como la diferencia simétrica de la ruta de coincidencia y aumento; una coincidencia es máxima si y solo si no tiene una ruta de aumento.anticadenaEn un grafo acíclico dirigido, un subconjunto S de vértices que son incomparables por pares, es decir, para cualquiera en S, no hay un camino dirigido desde x hasta y o desde y hasta x. Inspirado en la noción de anticadenas en conjuntos parcialmente ordenados.anti-bordeSinónimo de non-edge, un par de vértices no adyacentes.anti-triánguloUn conjunto independiente de tres vértices, el complemento de un triángulo.apéndice1. Un gráfico de vértice es un gráfico en el que se puede quitar un vértice, dejando un subgráfico plano. El vértice eliminado se llama vértice. Un grafo k -ápex es un grafo que puede volverse plano eliminando k vértices.2. Sinónimo de vértice universal, un vértice adyacente a todos los demás vértices.arborescenciaSinónimo de árbol enraizado y dirigido; ver árbol.arcoVer borde.flechaUn par ordenado de vértices, como una arista en un gráfico dirigido. Una flecha (x, y) tiene una cola x, una cabeza y, y una dirección de x a y; Se dice que y es el sucesor directo de x y que x es el predecesor directo de y. La flecha (y, x) es la flecha invertida de la flecha (x, y).punto de articulaciónUn vértice en un gráfico conexo cuya eliminación desconectaría el gráfico.-arioUn árbol k -ario es un árbol enraizado en el que cada vértice interno no tiene más de k hijos. Un árbol 1-ario es solo un camino. Un árbol de 2 arios también se denomina árbol binario, aunque ese término se refiere más correctamente a los árboles de 2 arios en los que los hijos de cada nodo se distinguen como hijos izquierdos o derechos (con como máximo uno de cada tipo). Se dice que un árbol k -ario es completo si cada vértice interno tiene exactamente k hijos.aumentandoUn tipo especial de camino alterno; ver alternancia.automorfismoUn automorfismo gráfico es una simetría de un gráfico, un isomorfismo del gráfico a sí mismo.

B

bolsaUno de los conjuntos de vértices en una descomposición en árbol.equilibradoUn grafo bipartito o multipartito está balanceado si cada dos subconjuntos de su partición de vértices tienen tamaños uno dentro del otro.banda anchaEl ancho de banda de un grafo G es el mínimo, sobre todos los ordenamientos de vértices de G, de la longitud del borde más largo (el número de pasos en el ordenamiento entre sus dos extremos). 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.bicliqueSinónimo de grafo bipartito completo o subgrafo bipartito completo; ver completo.biconectadoPor lo general, un sinónimo de 2 -vértice-conectado, pero a veces incluye K ₂ aunque no es 2-conectado. Ver conectado; para componentes biconectados, véase componente.número vinculanteLa relación más pequeña posible entre el número de vecinos de un subconjunto propio de vértices y el tamaño del subconjunto.bipartitoUn grafo bipartito es un grafo cuyos vértices se pueden dividir en dos conjuntos disjuntos, de modo que los vértices de un conjunto no están conectados entre sí, pero pueden estar conectados a los vértices del otro conjunto. Dicho de otra manera, un gráfico bipartito es un gráfico sin ciclos impares; de manera equivalente, es un gráfico que puede colorearse correctamente con dos colores. Los gráficos bipartitos a menudo se escriben G = (U, V, E) donde U y V son los subconjuntos de vértices de cada color. Sin embargo, a menos que el gráfico esté conectado, es posible que no tenga un color único de 2.biregularUn grafo biregular es un grafo bipartito en el que solo hay dos grados de vértice diferentes, uno para cada conjunto de la bipartición de vértice.bloquear1. Un bloque de un gráfico G es un subgrafo maximal que es un vértice aislado, una arista puente o un subgrafo biconexo. Si un bloque es biconexo, cada par de vértices pertenece a un ciclo común. Cada borde de un gráfico pertenece exactamente a un bloque.2. El grafo de bloques de un grafo G es otro grafo cuyos vértices son los bloques de G, con una arista que conecta dos vértices cuando los bloques correspondientes comparten un punto de articulación; es decir, es la gráfica de intersección de los bloques de G. El gráfico de bloques de cualquier gráfico es un bosque.3. El gráfico de corte de bloque (o punto de corte de bloque) de un gráfico G es un gráfico bipartito en el que un conjunto de partículas consiste en los vértices de corte de G, y el otro tiene un vértice para cada bloque de G. Cuando G está conectado, su gráfico de punto de corte de bloque es un árbol.4. Un gráfico de bloques (también llamado árbol clique si está conectado, y algunas veces erróneamente llamado árbol de Husimi) es un gráfico cuyos bloques son gráficos completos. Un bosque es un gráfico de bloques; entonces, en particular, el gráfico de bloques de cualquier gráfico es un gráfico de bloques, y cada gráfico de bloques puede construirse como el gráfico de bloques de un gráfico.vínculoUn conjunto de corte mínimo: un conjunto de aristas cuya eliminación desconecta el gráfico, para el cual ningún subconjunto propio tiene la misma propiedad.libro1. Un libro, libro gráfico o libro triangular es un gráfico tripartito completo K _{1,1, n}; una colección de n triángulos unidos en un borde compartido.2. Otro tipo de gráfico, también llamado libro, o libro cuadrilátero, es una colección de 4 ciclos unidos en un borde compartido; el producto cartesiano de una estrella con una arista.3. Una incrustación de libro es una incrustación de un gráfico en un libro topológico, un espacio formado al unir una colección de semiplanos a lo largo de una línea compartida. Por lo general, se requiere que los vértices de la incrustación estén en la línea, que se denomina el lomo de la incrustación, y los bordes de la incrustación deben estar dentro de un solo semiplano, una de las páginas del libro.Perímetro1. En una incrustación de gráficos, un recorrido de límite es el subgráfico que contiene todas las aristas y vértices incidentes en una cara.zarzaUna zarza es una colección de subgrafos conectados que se tocan mutuamente, donde dos subgrafos se tocan si comparten un vértice o cada uno incluye un punto final de un borde. El orden de una zarza es el tamaño más pequeño de un conjunto de vértices que tiene una intersección no vacía con todos los subgrafos. El ancho del árbol de un gráfico es el orden máximo de cualquiera de sus zarzas.descomposición de ramasUna descomposición en ramas de G es un agrupamiento jerárquico de los bordes de G, representado por un árbol binario sin raíz con sus hojas etiquetadas por los bordes de G. El ancho de una descomposición en ramas es el máximo, sobre las aristas e de este árbol binario, del número de vértices compartidos entre los subgrafos determinados por las aristas de G en los dos subárboles separados por e. El ancho de rama de G es el ancho mínimo de cualquier descomposición de rama de G.ancho de ramaVer descomposición de ramas.puente1. Un puente, istmo o borde cortado es un borde cuya eliminación desconectaría el gráfico. Un grafo sin puente es aquel que no tiene puentes; equivalentemente, un gráfico conectado por 2 aristas.2. Especialmente en el contexto de las pruebas de planaridad, un puente de un ciclo es un subgrafo máximo que es disjunto del ciclo y en el que cada dos aristas pertenecen a un camino que es internamente disjunto del ciclo. Un acorde es un puente de un solo lado. Un ciclo periférico es un ciclo con como máximo un puente; debe ser una cara en cualquier incrustación plana de su gráfico.3. Un puente de un ciclo también puede significar un camino que conecta dos vértices de un ciclo pero es más corto que cualquiera de los caminos del ciclo que conecta los mismos dos vértices. Un grafo puenteado es un grafo en el que cada ciclo de cuatro o más vértices tiene un puente.sin puenteUn gráfico sin puente es un gráfico que no tiene bordes de puente; es decir, un gráfico conectado por 2 aristas.mariposa1. El gráfico de la mariposa tiene cinco vértices y seis aristas; está formado por dos triángulos que comparten un vértice.2. La red mariposa es un grafo utilizado como arquitectura de red en computación distribuida, estrechamente relacionado con los ciclos cubo-conectados.

C

CC _n es un gráfico de ciclo de n vértices; ver ciclo.cactusUn gráfico de cactus, árbol de cactus, cactus o árbol de Husimi es un gráfico conectado en el que cada borde pertenece a un ciclo como máximo. Sus bloques son ciclos o aristas simples. Si, además, cada vértice pertenece como máximo a dos bloques, entonces se llama cactus de Navidad.jaulaUna jaula es un grafo regular con el orden más pequeño posible para su perímetro.canónicocanonizaciónUna forma canónica de un gráfico es un invariante tal que dos gráficos tienen invariantes iguales si y solo si son isomorfos. Las formas canónicas también pueden denominarse invariantes canónicas o invariantes completas y, a veces, se definen solo para los gráficos dentro de una familia particular de gráficos. La canonización de grafos es el proceso de calcular una forma canónica.tarjetaUn gráfico formado a partir de un gráfico dado eliminando un vértice, especialmente en el contexto de la conjetura de reconstrucción. Véase también mazo, el conjunto múltiple de todas las cartas de un gráfico.ancho de tallaEl ancho de tallado es una noción de ancho de gráfico análoga al ancho de rama, pero que utiliza agrupaciones jerárquicas de vértices en lugar de agrupaciones jerárquicas de bordes.orugaUn árbol oruga u oruga es un árbol en el que los nodos internos inducen un camino.centroEl centro de un gráfico es el conjunto de vértices de mínima excentricidad.cadena1. Sinónimo de andar.2. Cuando se aplican métodos de topología algebraica a gráficos, un elemento de un complejo de cadenas, a saber, un conjunto de vértices o un conjunto de aristas.constante animadoraVer expansión.cerezaUna cereza es un camino en tres vértices.xχ (G) (usando la letra griega chi) es el número cromático de G y χ  ′(G) es su índice cromático; ver cromático y colorido.niñoEn un árbol con raíz, un hijo de un vértice v es vecino de v a lo largo de un borde saliente, uno que se aleja de la raíz.acordecordal1. Una cuerda de un ciclo es una arista que no pertenece al ciclo, por lo que ambos extremos pertenecen al ciclo.2. Un grafo cordal es un grafo en el que cada ciclo de cuatro o más vértices tiene una cuerda, por lo que los únicos ciclos inducidos son triángulos.3. Un grafo fuertemente cordal es un grafo cordal en el que cada ciclo de longitud seis o más tiene una cuerda impar.4. Un grafo bipartito cordal no es cordal (a menos que sea un bosque); es un grafo bipartito en el que cada ciclo de seis o más vértices tiene una cuerda, por lo que los únicos ciclos inducidos son 4 ciclos.5. Una cuerda de un círculo es un segmento de línea que conecta dos puntos en el círculo; el gráfico de intersección de una colección de cuerdas se llama gráfico circular.cromáticoQue tiene que ver con la coloración; ver color. La teoría de grafos cromáticos es la teoría de la coloración de grafos. El número cromático χ (G) es el número mínimo de colores necesarios para una correcta coloración de G. χ  ′(G) es el índice cromático de G, el número mínimo de colores necesarios en una coloración adecuada de los bordes de G.seleccionableelegibilidadUn grafo es k -elegible si tiene una lista de colores siempre que cada vértice tenga una lista de k colores disponibles. La elegibilidad del grafo es el k más pequeño para el cual es k -elegible.circuloUn gráfico circular es el gráfico de intersección de las cuerdas de un círculo.circuitoUn circuito puede referirse a un camino cerrado o a un elemento del espacio del ciclo (un subgrafo de expansión euleriano). El rango de circuito de un gráfico es la dimensión de su espacio de ciclo.circunferenciaLa circunferencia de un gráfico es la longitud de su ciclo simple más largo. El gráfico es hamiltoniano si y solo si su circunferencia es igual a su orden.clase1. Una clase de gráficos o familia de gráficos es una colección (normalmente infinita) de gráficos, a menudo definida como los gráficos que tienen alguna propiedad específica. La palabra "clase" se usa en lugar de "conjunto" porque, a menos que se establezcan restricciones especiales (como restringir que los vértices se dibujen de un conjunto particular y definir los bordes para que sean conjuntos de dos vértices), las clases de gráficos generalmente no son conjuntos. cuando se formaliza usando la teoría de conjuntos.2. Una clase de color de un gráfico coloreado es el conjunto de vértices o aristas que tienen un color particular.3. En el contexto del teorema de Vizing, sobre la coloración de aristas de grafos simples, se dice que un grafo es de clase uno si su índice cromático es igual a su grado máximo, y de clase dos si su índice cromático es igual a uno más el grado. Según el teorema de Vizing, todos los gráficos simples son de clase uno o clase dos.garraUna garra es un árbol con un vértice interno y tres hojas, o equivalentemente el grafo bipartito completo K _1,3. Un gráfico sin garras es un gráfico que no tiene un subgrafo inducido que sea una garra.camarillaUna 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 adyacentes entre sí (o subgrafo completo máximo), uno que no forma parte de ningún conjunto (o subgrafo) más grande. Una camarilla k es una camarilla de orden k. El número de camarilla ω (G) de un gráfico G es el orden de su camarilla más grande. El gráfico de camarilla de un gráfico G es el gráfico de intersección de las camarillas máximas en G. Véase también biclique, un subgrafo bipartito completo.árbol camarillaSinónimo de gráfico de bloques.ancho de camarillaEl ancho de camarilla de un gráfico G es el número mínimo de etiquetas distintas necesarias para construir G mediante operaciones que crean un vértice etiquetado, forman la unión separada de dos gráficos etiquetados, agregan un borde que conecta todos los pares de vértices con etiquetas dadas o reetiquetan todos los vértices con una etiqueta dada. Los gráficos de ancho de camarilla como máximo 2 son exactamente los cografos.cerrado1. Un barrio cerrado es aquel que incluye su vértice central; ver barrio.2. Un paseo cerrado es aquel que comienza y termina en el mismo vértice; ver caminar.3. Un grafo es cerrado transitivamente si es igual a su propio cierre transitivo; ver transitivo.4. Una propiedad de grafos es cerrada bajo alguna operación sobre grafos si, siempre que el argumento o argumentos de la operación tengan la propiedad, también la tendrá el resultado. Por ejemplo, las propiedades hereditarias se cierran bajo subgrafos inducidos; las propiedades monótonas se cierran bajo subgrafos; y las propiedades cerradas a menores están cerradas a menores.cierre1. Para el cierre transitivo de un grafo dirigido, consulte transitivo.2. Una clausura de un grafo dirigido es un conjunto de vértices que no tienen aristas salientes a vértices fuera de la clausura. Por ejemplo, un fregadero es un cierre de un vértice. El problema del cierre es el problema de encontrar un cierre de peso mínimo o máximo.co-Este prefijo tiene varios significados que generalmente involucran gráficos de complemento. Por ejemplo, un cografo es un grafo producido por operaciones que incluyen complementación; una cocoloración es una coloración en la que cada vértice induce un conjunto independiente (como en la coloración adecuada) o una camarilla (como en una coloración del complemento).colorcolorante1. La coloración de un gráfico es un etiquetado de los vértices de un gráfico por elementos de un conjunto dado de colores, o de manera equivalente, una partición de los vértices en subconjuntos, llamados "clases de color", cada uno de los cuales está asociado con uno de los colores.2. Algunos autores usan "coloreado", sin calificación, para referirse a un coloreado adecuado, uno que asigna diferentes colores a los extremos de cada borde. En la coloración de gráficos, el objetivo es encontrar una coloración adecuada que utilice la menor cantidad de colores posible; por ejemplo, los gráficos bipartitos son los gráficos que tienen colorantes con solo dos colores, y el teorema de los cuatro colores establece que cada gráfico plano se puede colorear con un máximo de cuatro colores. Se dice que un gráfico es k -coloreado si ha sido (correctamente) coloreado con k colores, y k -coloreable o k -cromático si esto es posible.3. Se han estudiado muchas variaciones de coloración, incluida la coloración de bordes (colorear bordes de modo que no haya dos bordes con el mismo punto final que compartan un color), coloración de lista (coloración adecuada con cada vértice restringido a un subconjunto de los colores disponibles), coloración acíclica (cada subgrafo de 2 colores es acíclico), cocoloración (cada clase de color induce un conjunto independiente o una camarilla), coloración completa (cada dos clases de color comparten un borde) y coloración total (tanto los bordes como los vértices están coloreados).4. El número de color de un gráfico es uno más la degeneración. Se llama así porque la aplicación de un algoritmo de coloración codicioso a un orden de degeneración del gráfico utiliza como máximo esta cantidad de colores.comparabilidadUn grafo no dirigido es un grafo de comparabilidad si sus vértices son los elementos de un conjunto parcialmente ordenado y dos vértices son adyacentes cuando son comparables en el orden parcial. De manera equivalente, un gráfico de comparabilidad es un gráfico que tiene una orientación transitiva. Muchas otras clases de gráficos pueden definirse como gráficos de comparabilidad de tipos especiales de orden parcial.complementarEl grafo complemento de un grafo simple G es otro grafo en el mismo conjunto de vértices que G, con una arista por cada dos vértices que no son adyacentes en G.completo1. Un grafo completo es aquel en el que cada dos vértices son adyacentes: todas las aristas que pudieran existir están presentes. Un gráfico completo con n vértices a menudo se denota como K _n. Un grafo bipartito completo es aquel en el que cada dos vértices en lados opuestos de la partición de vértices son adyacentes. Un grafo bipartito completo con vértices a en un lado de la partición y vértices b en el otro lado a menudo se denota como K _{a, b}. La misma terminología y notación también se ha extendido a gráficos multipartitos completos, gráficos en los que los vértices se dividen en más de dos subconjuntos y cada par de vértices en diferentes subconjuntos son adyacentes; si el número de vértices en los subconjuntos es a, b, c,... entonces este gráfico se denota como K _{a, b, c,...}.2. Una terminación de un gráfico dado es un supergrafo que tiene alguna propiedad deseada. Por ejemplo, una terminación cordal es un supergrafo que es un gráfico cordal.3. Un emparejamiento completo es sinónimo de un emparejamiento perfecto; ver coincidencia.4. Una coloración completa es una coloración adecuada en la que cada par de colores se utiliza para los extremos de al menos un borde. Toda coloración con un número mínimo de colores es completa, pero pueden existir coloraciones completas con 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 invariante completo de un gráfico es sinónimo de una forma canónica, un invariante que tiene diferentes valores para gráficos no isomorfos.componenteUn componente conexo de un gráfico es un subgrafo conexo máximo. El término también se usa para subgráficos máximos o subconjuntos de vértices de un gráfico que tienen un orden superior de conectividad, incluidos componentes biconectados, componentes triconectados y componentes fuertemente conectados.condensaciónLa condensación de un gráfico dirigido G es un gráfico acíclico dirigido con un vértice para cada componente fuertemente conectado de G y una arista que conecta pares de componentes que contienen los dos extremos de al menos una arista en G.conoUn gráfico que contiene un vértice universal.conectarCausa para estar conectado.conectadoUn grafo conexo es aquel en el que cada par de vértices forman los extremos de un camino. Las formas más altas de conectividad incluyen conectividad fuerte en gráficos dirigidos (por cada dos vértices hay caminos de uno a otro en ambas direcciones), k -gráficos conectados por vértices (eliminar menos de k vértices no puede desconectar el gráfico) y k -borde -Gráficos conectados (eliminar menos de k bordes no puede desconectar el gráfico).conversarEl gráfico inverso es sinónimo de gráfico transpuesto; ver transponer.centro1. Un núcleo k es el subgrafo inducido formado al eliminar todos los vértices de grado menor que k y todos los vértices cuyo grado se vuelve menor que k después de eliminaciones anteriores. Véase degeneración.2. Un núcleo es un grafo G tal que todo homomorfismo de grafo de G a sí mismo es un isomorfismo.3. El núcleo de un grafo G es un grafo minimal H tal que existen homomorfismos de G a H y viceversa. H es único salvo isomorfismo. Se puede representar como un subgrafo inducido de G y es un núcleo en el sentido de que todos sus auto-homomorfismos son isomorfismos.4. In the theory of graph matchings, the core of a graph is an aspect of its Dulmage–Mendelsohn decomposition, formed as the union of all maximum matchings.cotree1. The complement of a spanning tree.2. A rooted tree structure used to describe a cograph, in which each cograph vertex is a leaf of the tree, each internal node of the tree is labeled with 0 or 1, and two cograph vertices are adjacent if and only if their lowest common ancestor in the tree is labeled 1.coverA vertex cover is a set of vertices incident to every edge in a graph. An edge cover is a set of edges incident to every vertex in a graph. A set of subgraphs of a graph covers that graph if its union – taken vertex-wise and edge-wise – is equal to the graph.criticalA critical graph for a given property is a graph that has the property but such that every subgraph formed by deleting a single vertex does not have the property. For instance, a factor-critical graph is one that has a perfect matching (a 1-factor) for every vertex deletion, but (because it has an odd number of vertices) has no perfect matching itself. Compare hypo-, used for graphs which do not have a property but for which every one-vertex deletion does.cubecubic1. Cube graph, the eight-vertex graph of the vertices and edges of a cube.2. Hypercube graph, a higher-dimensional generalization of the cube graph.3. Folded cube graph, formed from a hypercube by adding a matching connecting opposite vertices.4. Halved cube graph, the half-square of a hypercube graph.5. Cubo parcial, un subgrafo que conserva la distancia de un hipercubo.6. El cubo de un grafo G es la potencia del grafo G.7. Gráfico cúbico, otro nombre para un gráfico de 3 regulares, uno en el que cada vértice tiene tres aristas incidentes.8. Ciclos conectados por cubos, un gráfico cúbico formado reemplazando cada vértice de un hipercubo por un ciclo.Corteconjunto de corteUn corte es una partición de los vértices de un gráfico en dos subconjuntos, o el conjunto (también conocido como conjunto de corte) de bordes que abarcan dicha partición, si ese conjunto no está vacío. Se dice que un borde abarca la partición si tiene extremos en ambos subconjuntos. Por lo tanto, la eliminación de un conjunto de corte de un gráfico conectado lo desconecta.punto de corteVéase punto de articulación.espacio de corteEl espacio de corte de un gráfico es un espacio vectorial GF (2) que tiene el conjunto de corte s del gráfico como sus elementos y la diferencia simétrica de conjuntos como su operación de suma de vectores.ciclo1. Un ciclo puede ser una especie de gráfico o una especie de caminata. Como paseo, puede ser un paseo cerrado (también llamado recorrido) o, más generalmente, un paseo cerrado sin vértices repetidos y, en consecuencia, bordes (también llamado ciclo simple). En el último caso, generalmente se lo considera como un grafo, es decir, las elecciones del primer vértice y la dirección generalmente se consideran sin importancia; es decir, las permutaciones cíclicas y las inversiones del camino producen el mismo ciclo. Los tipos especiales importantes de ciclo incluyen ciclos hamiltonianos, ciclos inducidos, ciclos periféricos y el ciclo más corto, que define la circunferencia de un gráfico. Un k -ciclo es un ciclo de longitud k; por ejemplo, un 2 -cycle es un digon y un 3-el ciclo es un triangulo. Un gráfico de ciclo es un gráfico que en sí mismo es un ciclo simple; un gráfico de ciclo con n vértices se denota comúnmente como 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

TROZO DE CUEROAbreviatura de gráfico acíclico dirigido, un gráfico dirigido sin ciclos dirigidos.plataformaEl conjunto múltiple 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 plataforma de borde se forma de la misma manera eliminando un solo borde de todas las formas posibles. Los gráficos en una baraja también se llaman cartas. Véase también crítico (gráficos que tienen una propiedad que no está en ninguna tarjeta) e hipo- (gráficos que no tienen una propiedad que está en todas las tarjetas).descomposiciónConsulte descomposición en árbol, descomposición en rutas o descomposición en ramas.degenerardegeneraciónUn gráfico k -degenerado es un gráfico no dirigido en el que cada subgráfico inducido tiene un grado mínimo como máximo k. La degeneración de un gráfico es la k más pequeña para la que es k -degenerado. Una ordenación de degeneración es una ordenación 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 un orden de degeneración de un gráfico k -degenerado, cada vértice tiene como máximo k vecinos posteriores. La degeneración también se conoce como número de núcleo k, ancho y enlace, y uno más la degeneración también se denomina número de coloración o número de Szekeres-Wilf. k -grafos degenerados también han sido llamados k-gráficos inductivos.la licenciatura1. El grado de un vértice en un gráfico es su número de aristas incidentes. El grado de un grafo G (o su grado máximo) es el máximo de los grados de sus vértices, a menudo denotados Δ(G); el grado mínimo de G es el mínimo de sus grados de vértice, a menudo denotados δ (G). El grado a veces se llama valencia; el grado de v en G se puede denotar d _G (v), d (G) o grado (v). El grado total es la suma de los grados de todos los vértices; por el lema del apretón de manos es un número par. La secuencia de grados es la colección de grados de todos los vértices, ordenados de mayor a menor. En un gráfico dirigido, se puede distinguir el grado de entrada (número de aristas entrantes) y el grado de salida (número de aristas salientes).2. El grado de homomorfismo de un grafo es sinónimo de su número de Hadwiger, el orden del mayor clique minor.Δ, δΔ(G) (usando la letra griega delta) es el grado máximo de un vértice en G, y δ (G) es el grado mínimo; ver grado.densidadEn un gráfico de n nodos, la densidad es la relación entre el número de aristas del gráfico y el número de aristas en un gráfico completo en n nodos. Ver gráfico denso.profundidadLa profundidad de un nodo en un árbol con raíz es el número de aristas en el camino desde la raíz hasta el nodo. Por ejemplo, la profundidad de la raíz es 0 y la profundidad de cualquiera de sus nodos adyacentes es 1. Es el nivel de un nodo menos uno. Tenga en cuenta, sin embargo, que algunos autores utilizan profundidad como sinónimo del nivel de un nodo.diámetroEl diámetro de un gráfico conexo es la longitud máxima de un camino más corto. Es decir, es el máximo de las distancias entre pares de vértices en el grafo. Si el gráfico tiene pesos en sus bordes, entonces su diámetro ponderado mide la longitud de la ruta por la suma de los pesos de los bordes a lo largo de una ruta, mientras que el diámetro no ponderado mide la longitud de la ruta por el número de bordes. Para gráficos desconectados, las definiciones varían: el diámetro puede definirse como infinito, o como el diámetro más grande de un componente conectado, o puede no estar definido.diamanteEl gráfico de diamante es un gráfico no dirigido con cuatro vértices y cinco aristas.desconectadoFuertemente conectado. _ (No debe confundirse con desconectado)excavarUn digon es un ciclo simple de longitud dos en un gráfico dirigido o un multigrafo. Los digones no pueden aparecer en gráficos simples no dirigidos, ya que requieren repetir el mismo borde dos veces, lo que viola la definición de simple.dígrafoSinónimo de grafo dirigido.dipatoVéase ruta dirigida.predecesor directoLa cola de un borde dirigido cuya cabeza es el vértice dado.sucesor directoLa cabeza de un borde dirigido cuya cola es el vértice dado.dirigidoUn grafo dirigido es aquel en el que las aristas tienen una dirección distinguida, de un vértice a otro. En un gráfico mixto, un borde dirigido es nuevamente uno que tiene una dirección distinguida; los bordes dirigidos también pueden llamarse arcos o flechas.arco dirigidoVer flecha.borde dirigidoVer flecha.línea dirigidaVer flecha.camino dirigidoUn camino en el que todas las aristas tienen la misma dirección. Si un camino dirigido lleva del vértice x al vértice y, x es un predecesor de y, y es un sucesor de x, y se dice que y es alcanzable desde x.dirección1. La relación asimétrica entre dos vértices adyacentes en un gráfico, representada como una flecha.2. La relación asimétrica entre dos vértices en un camino dirigido.desconectarCausa para ser desconectado.desconectadoNo conectado _desarticular1. Dos subgrafos son disjuntos por arista si no comparten aristas, y disjuntos por vértice si no comparten vértices.2. La unión disjunta de dos o más grafos es un grafo cuyos conjuntos de vértices y aristas son las uniones disjuntas de los conjuntos correspondientes.distanciaLa distancia entre dos vértices en un gráfico es la longitud del camino más corto que tiene los dos vértices como puntos finales.domáticoUna partición dómática de un grafo es una partición de los vértices en conjuntos dominantes. El número domático del gráfico es el número máximo de conjuntos dominantes en dicha partición.dominanteUn conjunto dominante es un conjunto de vértices que incluye o es adyacente a todos los vértices del gráfico; no debe confundirse con una cubierta de vértices, un conjunto de vértices que incide en todos los bordes del gráfico. Los tipos especiales importantes de conjuntos dominantes incluyen conjuntos dominantes independientes (conjuntos dominantes que también son conjuntos independientes) y conjuntos dominantes conectados (conjuntos dominantes que indujeron subgrafos conectados). Un conjunto dominante de un solo vértice también puede llamarse vértice universal. El número de dominación de un gráfico es el número de vértices en el conjunto dominante más pequeño.dobleUn gráfico dual de un gráfico plano G es un gráfico que tiene un vértice para cada cara de G.

Mi

miE (G) es el conjunto de aristas de G; ver conjunto de bordes.oídoUna oreja de un grafo es un camino cuyos extremos pueden coincidir pero en el que por lo demás no hay repeticiones de vértices o aristas.descomposición del oídoUna descomposición de oídos es una partición de los bordes de un gráfico en una secuencia de oídos, cada uno de cuyos extremos (después del primero) pertenece a un oído anterior y cada uno de cuyos puntos interiores no pertenece a ningún oído anterior. Una oreja abierta es un camino simple (una oreja sin vértices repetidos), y una descomposición de oreja abierta es una descomposición de oreja en la que cada oreja después de la primera está abierta; un gráfico tiene una descomposición en oreja abierta si y solo si es biconexo. Una mazorca es impar si tiene un número impar de aristas, y una descomposición de mazorca impar es una descomposición de mazorca en la que cada mazorca es impar; un gráfico tiene una descomposición de orejas impares si y solo si es un factor crítico.excentricidadLa excentricidad de un vértice es la distancia más lejana de éste a cualquier otro vértice.bordeUna arista es (junto con los vértices) una de las dos unidades básicas a partir de las cuales se construyen los gráficos. Cada borde tiene dos (o en hipergrafías, más) vértices a los que está unido, llamados puntos finales. Los bordes pueden ser dirigidos o no dirigidos; los bordes no dirigidos también se llaman líneas y los bordes dirigidos también se llaman arcos o flechas. En un gráfico simple no dirigido, una arista puede representarse como el conjunto de sus vértices, y en un gráfico simple dirigido puede representarse como un par ordenado de sus vértices. Una arista que conecta los vértices xey a veces se escribe xy.corte de bordeUn conjunto de aristas cuya eliminación desconecta el gráfico. Un corte de un borde se llama puente, istmo o borde cortado.conjunto de bordesEl conjunto de aristas de un gráfico G dado, a veces denotado por E (G).gráfico sin bordesEl gráfico sin bordes o el gráfico totalmente desconectado en un conjunto dado de vértices es el gráfico que no tiene bordes. A veces se le llama gráfico vacío, pero este término también puede referirse a un gráfico sin vértices.incrustaciónUna incrustación de gráfico es una representación topológica de un gráfico como un subconjunto de un espacio topológico con cada vértice representado como un punto, cada borde representado como una curva que tiene los puntos finales del borde como puntos finales de la curva, y ninguna otra intersección entre vértices o bordes Un gráfico plano es un gráfico que tiene una incrustación de este tipo en el plano euclidiano, y un gráfico toroidal es un gráfico que tiene una incrustación de este tipo en un toroide. El género de un gráfico es el género mínimo posible de una variedad bidimensional en la que se puede incrustar.gráfico vacío1. Un gráfico sin bordes en un conjunto de vértices no vacío.2. El gráfico de orden cero, un gráfico sin vértices ni bordes.finalUn extremo de un gráfico infinito es una clase de equivalencia de rayos, donde dos rayos son equivalentes si hay un tercer rayo que incluye infinitos vértices de ambos.punto finalUno de los dos vértices unidos por una arista dada, o uno de los primeros o últimos vértices de un paseo, sendero o camino. El primer punto final de un borde dirigido dado se llama cola y el segundo punto final se llama cabeza.enumeraciónLa enumeración de gráficos es el problema de contar los gráficos en una clase dada de gráficos, en función de su orden. De manera más general, los problemas de enumeración pueden referirse a problemas de contar una cierta clase de objetos combinatorios (como grupos, conjuntos independientes, colorantes o árboles de expansión), o de enumerar algorítmicamente todos esos objetos.EulerianoUn camino euleriano es un paseo que usa cada borde de un gráfico exactamente una vez. Un circuito euleriano (también llamado ciclo euleriano o recorrido euleriano) es un paseo cerrado que utiliza cada arista exactamente una vez. Un grafo euleriano es un grafo que tiene un circuito euleriano. Para un gráfico no dirigido, esto significa que el gráfico es conexo y cada vértice tiene un grado par. Para un gráfico dirigido, esto significa que el gráfico está fuertemente conectado y cada vértice tiene un grado de entrada igual al grado de salida. En algunos casos, el requisito de conectividad se relaja y un gráfico que cumple solo con los requisitos de grado se denomina euleriano.inclusoDivisible por dos; por ejemplo, un ciclo par es un ciclo cuya duración es par.expansorUn gráfico de expansión es un gráfico cuya expansión de borde, expansión de vértice o expansión espectral está limitada desde cero.expansión1. La expansión de la arista, el número isoperimétrico o la constante de Cheeger de un gráfico G es la relación mínima, sobre subconjuntos S de como máximo la mitad de los vértices de G, del número de aristas que salen de 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 ampliación de un gráfico G es la relación mínima, sobre subconjuntos S de como máximo la mitad de los vértices de G, del número de vértices fuera pero adyacentes a S al número de vértices en s _3. La expansión vecina única de un grafo G es la relación mínima, sobre subconjuntos de como máximo la mitad de los vértices de G, del número de vértices fuera de S pero adyacentes a un vértice único en S al número de vértices en S.4. La expansión espectral de un gráfico d -regular G es la brecha espectral entre el valor propio más grande d de su matriz de adyacencia y el segundo valor propio más grande.5. Una familia de grafos tiene expansión acotada si todos sus r -menores poco profundos tienen una relación de aristas a vértices acotada por una función de r, y expansión polinomial si la función de r es un polinomio.

F

caraEn un gráfico plano o incrustación de gráfico, un componente conectado del subconjunto del plano o superficie de incrustación que es disjunto del gráfico. Para una incrustación en el plano, se delimitarán todas las caras excepto una; la única cara excepcional que se extiende hasta el infinito se llama cara exterior.factorUn factor de un gráfico es un subgráfico de expansión: un subgráfico que incluye todos los vértices del gráfico. El término se usa principalmente en el contexto de subgrafos regulares: un k -factor es un factor que es k - regular. En particular, un factor 1 es lo mismo que una combinación perfecta. Un gráfico de factor crítico es un gráfico para el cual la eliminación de cualquier vértice produce un gráfico con un factor 1.factorizaciónUna factorización de gráfico es una partición de los bordes del gráfico en factores; una k -factorización es una partición en k -factores. Por ejemplo, una factorización en 1 es una coloración de borde con la propiedad adicional de que cada vértice incide en un borde de cada color.familiaun sinónimo para clasefinitoUn grafo es finito si tiene un número finito de vértices y un número finito de aristas. Muchas fuentes asumen que todos los gráficos son finitos sin decirlo explícitamente. Un grafo es localmente finito si cada vértice tiene un número finito de aristas incidentes. Un grafo infinito es un grafo que no es finito: tiene infinitos vértices, infinitos bordes, o ambos.primer ordenLa lógica de primer orden de los gráficos es una forma de lógica en la que las variables representan los vértices de un gráfico y existe un predicado binario para probar si dos vértices son adyacentes. Para distinguirse de la lógica de segundo orden, en la que las variables también pueden representar conjuntos de vértices o aristas.-solapaPara un conjunto de vértices X, un colgajo X es un componente conectado del subgrafo inducido formado al eliminar X. La terminología flap se usa comúnmente en el contexto de los refugios, funciones que asignan pequeños conjuntos de vértices a sus flaps. Véase también el puente de un ciclo, que es un colgajo de los vértices del ciclo o una cuerda del ciclo.prohibidoUna caracterización de gráficos prohibidos 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 aparece como subgráfico, subgráfico inducido o menor, se dice que H está prohibido.gráfico de forzamientoUn gráfico forzado es un gráfico H tal que evaluar la densidad de subgráficos de H en los gráficos de una secuencia gráfica G(n) es suficiente para probar si esa secuencia es casi aleatoria.bosqueUn bosque es un grafo no dirigido sin ciclos (una unión disjunta de árboles sin raíz), o un grafo dirigido formado como una unión disjunta de árboles enraizados.fruto1. Robert Frucht2. El gráfico de Frucht, uno de los dos gráficos cúbicos más pequeños sin simetrías no triviales.3. El teorema de Frucht de que todo grupo finito es el grupo de simetrías de un grafo finito.completoSinónimo de inducido.gráfico funcionalUn grafo funcional es un grafo dirigido donde cada vértice tiene un grado de salida. De manera equivalente, un gráfico funcional es un pseudobosque dirigido al máximo.

GRAMO

GRAMOUna variable que se usa a menudo para denotar un gráfico.géneroEl género de un gráfico es el género mínimo de una superficie en la que se puede incrustar; ver incrustación.geodésicoComo sustantivo, una geodésica es sinónimo de camino más corto. Cuando se usa como adjetivo, significa relacionado con los caminos más cortos o las distancias de camino más cortas.giganteEn la teoría de grafos aleatorios, una componente gigante es una componente conexa que contiene una fracción constante de los vértices del gráfico. En los modelos estándar de gráficos aleatorios, normalmente hay como máximo un componente gigante.circunferenciaLa circunferencia de un gráfico es la longitud de su ciclo más corto.graficoEl objeto fundamental de estudio en teoría de grafos, un sistema de vértices conectados en pares por aristas. A menudo se subdivide 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 aristas.codiciosoProducido por un algoritmo codicioso. Por ejemplo, una coloración codiciosa de un gráfico es una coloración producida considerando los vértices en alguna secuencia y asignando a cada vértice el primer color disponible.Grotzsch1. Herbert Grötzsch2. El gráfico de Grötzsch, el gráfico sin triángulos más pequeño que requiere cuatro colores en cualquier coloración adecuada.3. El teorema de Grötzsch de que los gráficos planos sin triángulos siempre se pueden colorear con un máximo de tres colores.número grundy1. El número de Grundy de un grafo es el número máximo de colores producidos por una coloración codiciosa, con una ordenación de vértices mal elegida.

H

HUna variable que a menudo se usa para denotar un gráfico, especialmente cuando otro gráfico ya ha sido denotado por G.H -coloraciónUna coloración H de un gráfico G (donde H es también un gráfico) es un homomorfismo de H a G.libre de HUn grafo está libre de H si no tiene un subgrafo inducido isomorfo a H, es decir, si H es un subgrafo inducido prohibido. Los gráficos libres de H son la familia de todos los gráficos (o, a menudo, todos los gráficos finitos) que son libres de H. Por ejemplo, los gráficos sin triángulos son los gráficos que no tienen un gráfico triangular como subgráfico. La propiedad de estar libre de H siempre es hereditaria. Un grafo está libre de H -menor si no tiene un isomorfo menor a H.Hadwiger1. Hugo Hadwiger2. El número de Hadwiger de una gráfica es el orden del mayor menor completo de la gráfica. También se le llama número de clique de contracción o grado de homomorfismo.3. La conjetura de Hadwiger es la conjetura de que el número de Hadwiger nunca es menor que el número cromático.hamiltonianoUna ruta hamiltoniana o un ciclo hamiltoniano es una ruta de expansión simple o un ciclo de expansión simple: cubre todos los vértices del gráfico exactamente una vez. Un gráfico es hamiltoniano si contiene un ciclo hamiltoniano y rastreable si contiene un camino hamiltoniano.refugioUn refugio k es una función que asigna cada conjunto X de menos de k vértices a una de sus aletas, a menudo satisfaciendo condiciones de consistencia adicionales. El orden de un refugio es el número k. Los refugios se pueden utilizar para caracterizar el ancho del árbol de gráficos finitos y los extremos y los números de Hadwiger de gráficos infinitos.altura1. La altura de un nodo en un árbol con raíz es el número de aristas en un camino más largo, alejándose de la raíz (es decir, sus nodos tienen una profundidad estrictamente creciente), que comienza en ese nodo y termina en una hoja.2. La altura de un árbol con raíces es la altura de su raíz. Es decir, la altura de un árbol es el número de aristas en el camino más largo posible, alejándose de la raíz, que comienza en la raíz y termina en una hoja.3. La altura de un gráfico acíclico dirigido es la longitud máxima de un camino dirigido en este gráfico.hereditarioUna propiedad hereditaria de los grafos es una propiedad que está cerrada bajo los subgrafos inducidos: si G tiene una propiedad hereditaria, también debe serlo todo subgrafo inducido de G. Compare monótono (cerrado bajo todos los subgráficos) o menor-cerrado (cerrado bajo menores).hexágonoUn ciclo simple que consta exactamente de seis aristas y seis vértices.agujeroUn agujero es un ciclo inducido de longitud cuatro o más. Un agujero impar es un agujero de longitud impar. Un antiagujero es un subgrafo inducido de orden cuatro cuyo complemento es un ciclo; de manera equivalente, es un agujero en el gráfico del complemento. Esta terminología se usa principalmente en el contexto de los gráficos perfectos, que se caracterizan por el teorema del gráfico perfecto fuerte como gráficos sin agujeros impares o antiagujeros impares. Los gráficos sin agujeros son los mismos que los gráficos cordales.equivalencia homomórficaDos grafos son homomórficamente equivalentes si existen dos homomorfismos, uno de cada grafo al otro grafo.homomorfismo1. Un homomorfismo de gráfico es un mapeo del conjunto de vértices de un gráfico al conjunto de vértices de otro gráfico que mapea vértices adyacentes a vértices adyacentes. Este tipo de mapeo entre grafos es el que se usa más comúnmente en los enfoques teóricos de categorías de la teoría de grafos. Una coloración de gráfico adecuada se puede describir de manera equivalente como un homomorfismo a un gráfico completo.2. El grado de homomorfismo de un grafo es sinónimo de su número de Hadwiger, el orden del mayor clique minor.hiperarcoUn hiperborde dirigido que tiene un origen y un destino establecidos.hiperbordeUna arista en una hipergrafía, que tiene cualquier número de puntos finales, en contraste con el requisito de que las aristas de los gráficos tengan exactamente dos puntos finales.hipercuboUn gráfico de hipercubo es un gráfico formado por los vértices y las aristas de un hipercubo geométrico.hipergrafiaUn hipergráfico es una generalización de un gráfico en el que cada borde (llamado hiperborde en este contexto) puede tener más de dos extremos.hipo-Este prefijo, en combinación con una propiedad de gráfico, indica un gráfico que no tiene la propiedad pero que cada subgráfico formado al eliminar un solo vértice sí tiene la propiedad. Por ejemplo, un grafo hipohamiltoniano es aquel que no tiene un ciclo hamiltoniano, pero para el cual cada eliminación de un vértice produce un subgrafo hamiltoniano. Comparar Critical, utilizado para gráficos que tienen una propiedad pero para los que cada eliminación de un vértice no la tiene.

Yo

en gradoEl número de aristas entrantes en un gráfico dirigido; ver grado.incidenciaUna incidencia en un gráfico es un par vértice-arista tal que el vértice es un punto final de la arista.matriz de incidenciaLa matriz de incidencia de un grafo es una matriz cuyas filas están indexadas por vértices del gráfico, y cuyas columnas están indexadas por aristas, con un uno en la celda para la fila i y la columna j cuando el vértice i y la arista j son incidentes, y un cero en caso contrario.incidenteLa relación entre una arista y uno de sus extremos.incomparableUn gráfico de incomparablebilidad es el complemento de un gráfico de comparabilidad; ver comparabilidad.independiente1. Un conjunto independiente es un conjunto de vértices que induce un subgrafo sin bordes. También puede llamarse conjunto estable o coclique. El número de independencia α (G) es el tamaño del conjunto máximo independiente.2. En la matriz gráfica de un grafo, un subconjunto de aristas es independiente de que el subgrafo correspondiente sea un árbol o un bosque. En la matroide bicircular, un subconjunto de aristas es independiente si el subgrafo correspondiente es un pseudobosque.indiferenciaUn gráfico de indiferencia es otro nombre para un gráfico de intervalo propio o un gráfico de intervalo unitario; ver adecuado.inducidoUn subgrafo inducido o subgrafo completo de un grafo es un subgrafo formado a partir de un subconjunto de vértices y de todos los bordes que tienen ambos extremos en el subconjunto. Los casos especiales incluyen caminos inducidos y ciclos inducidos, subgrafos inducidos que son caminos o ciclos.inductivoSinónimo de degenerado.infinitoUn grafo infinito es aquel que no es finito; ver finito.internoUn vértice de un camino o árbol es interno si no es una hoja; es decir, si su grado es mayor que uno. Dos caminos son internamente disjuntos (algunos lo llaman independientes) si no tienen ningún vértice en común, excepto el primero y el último.intersección1. La intersección de dos grafos es su mayor subgrafo común, el grafo formado por los vértices y aristas que pertenecen a ambos grafos.2. Un gráfico de intersección es un gráfico cuyos vértices corresponden a conjuntos u objetos geométricos, con una arista entre dos vértices exactamente cuando los dos conjuntos u objetos correspondientes tienen una intersección no vacía. Se pueden definir varias clases de gráficos como gráficos de intersección de ciertos tipos de objetos, por ejemplo, gráficos cordales (gráficos de intersección de subárboles de un árbol), gráficos circulares (gráficos de intersección de cuerdas de un círculo), gráficos de intervalo (gráficos de intersección de intervalos). de una línea), gráficos de líneas (gráficos de intersección de los bordes de un gráfico) y gráficos de camarilla (gráficos de intersección de las camarillas máximas de un gráfico). Cada gráfico es un gráfico de intersección para alguna familia de conjuntos, y esta familia se denomina representación de intersección del gráfico. El número de intersección de un gráfico Ges el número total mínimo de elementos en cualquier representación de intersección de G.intervalo1. Un gráfico de intervalos es un gráfico de intersección de intervalos de una recta.2. El intervalo [ u, v ] en un gráfico es la unión de todos los caminos más cortos de u a v.3. El grosor del intervalo es sinónimo de ancho de ruta.invarianteUn sinónimo de propiedad.flecha invertidaUna flecha con una dirección opuesta en comparación con otra flecha. La flecha (y, x) es la flecha invertida de la flecha (x, y).aisladoUn vértice aislado de un grafo es un vértice de grado cero, es decir, un vértice sin aristas incidentes.isomorfoDos grafos son isomorfos si existe un isomorfismo entre ellos; ver isomorfismo.isomorfismoUn isomorfismo de gráfico es una incidencia uno a uno que conserva la correspondencia de los vértices y las aristas de un gráfico con los vértices y las aristas de otro gráfico. Dos grafos relacionados de esta manera se dice que son isomorfos.isoperimétricoVer expansión.istmoSinónimo de puente, en el sentido de una arista cuya remoción desconecta el grafo.

K

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

L

LL (G) es el gráfico lineal de G; ver línea.etiqueta1. Información asociada con 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 etiquetados con vértices o etiquetados con bordes se pueden usar para especificar qué objetos de un gráfico tienen etiquetas. El etiquetado de gráficos se refiere a varios problemas diferentes de asignación de etiquetas a gráficos sujetos a ciertas restricciones. Consulte también la coloración de gráficos, en la que las etiquetas se interpretan como colores.2. En el contexto de la enumeración de gráficos, se dice que los vértices de un gráfico están etiquetados si se pueden distinguir entre sí. Por ejemplo, esto se puede hacer realidad fijando una correspondencia uno a uno entre los vértices y los números enteros desde 1 hasta el orden del gráfico. Cuando se etiquetan los vértices, los gráficos que son isomorfos entre sí (pero con diferentes órdenes de vértices) se cuentan como objetos separados. Por el contrario, cuando los vértices no están etiquetados, los gráficos que son isomorfos entre sí no se cuentan por separado.hoja1. Un vértice de hoja o vértice colgante (especialmente en un árbol) es un vértice cuyo grado es 1. Un borde de hoja o borde colgante es el borde que conecta un vértice de hoja con su único vecino.2. Una potencia de hoja de un árbol es un grafo cuyos vértices son las hojas del árbol y cuyas aristas conectan hojas cuya distancia en el árbol es como mucho un umbral dado.longitudEn un gráfico no ponderado, la longitud de un ciclo, camino o caminata es el número de aristas que utiliza. En un gráfico ponderado, en cambio, puede ser la suma de los pesos de los bordes que utiliza. La longitud se utiliza para definir la ruta más corta, la circunferencia (longitud de ciclo más corta) y la ruta más larga entre dos vértices en un gráfico.nivel1. Esta es la profundidad de un nodo más 1, aunque algunos la definen como sinónimo de profundidad. El nivel de un nodo en un árbol con raíz es el número de nodos en el camino desde la raíz hasta el nodo. Por ejemplo, la raíz tiene nivel 1 y cualquiera de sus nodos adyacentes tiene nivel 2.2. A set of all node having the same level or depth.lineA synonym for an undirected edge. The line graph L(G) of a graph G is a graph with a vertex for each edge of G and an edge for each pair of edges that share an endpoint in G.linkageA synonym for degeneracy.list1. An adjacency list is a computer representation of graphs for use in graph algorithms.2. List coloring is a variation of graph coloring in which each vertex has a list of available colors.localA local property of a graph is a property that is determined only by the neighbourhoods of the vertices in the graph. For instance, a graph is locally finite if all of its neighborhoods are finite.loopA loop or self-loop is an edge both of whose endpoints are the same vertex. It forms a cycle of length 1. These are not allowed in simple graphs.

M

magnificationSynonym for vertex expansion.matchingA matching is a set of edges in which no two share any vertex. A vertex is matched or saturated if it is one of the endpoints of an edge in the matching. A perfect matching or complete matching is a matching that matches every vertex; it may also be called a 1-factor, and can only exist when the order is even. A near-perfect matching, in a graph with odd order, is one that saturates all but one vertex. A maximum matching is a matching that uses as many edges as possible; the matching number α′(G) of a graph G is the number of edges in a maximum matching. A maximal matching is a matching to which no additional edges can be added.maximal1. A subgraph of given graph G is maximal for a particular property if it has that property but no other supergraph of it that is also a subgraph of G also has the same property. That is, it is a maximal element of the subgraphs with the property. For instance, a maximal clique is a complete subgraph that cannot be expanded to a larger complete subgraph. The word "maximal" should be distinguished from "maximum": a maximum subgraph is always maximal, but not necessarily vice versa.2. A simple graph with a given property is maximal for that property if it is not possible to add any more edges to it (keeping the vertex set unchanged) while preserving both the simplicity of the graph and the property. Thus, for instance, a maximal planar graph is a planar graph such that adding any more edges to it would create a non-planar graph.maximumA subgraph of a given graph G is maximum for a particular property if it is the largest subgraph (by order or size) among all subgraphs with that property. For instance, a maximum clique is any of the largest cliques in a given graph.median1. A median of a triple of vertices, a vertex that belongs to shortest paths between all pairs of vertices, especially in median graphs and modular graphs.2. A median graph is a graph in which every three vertices have a unique median.Meyniel1. Henri Meyniel, French graph theorist.2. A Meyniel graph is a graph in which every odd cycle of length five or more has at least two chords.minimalA subgraph of given graph is minimal for a particular property if it has that property but no proper subgraph of it also has the same property. That is, it is a minimal element of the subgraphs with the property.minimum cutA cut whose cut-set has minimum total weight, possibly restricted to cuts that separate a designated pair of vertices; they are characterized by the max-flow min-cut theorem.minorA graph H is a minor of another graph G if H can be obtained by deleting edges or vertices from G and contracting edges in G. It is a shallow minor if it can be formed as a minor in such a way that the subgraphs of G that were contracted to form vertices of H all have small diameter. H is a topological minor of G if G has a subgraph that is a subdivision of H. A graph is H-minor-free if it does not have H as a minor. A family of graphs is minor-closed if it is closed under minors; the Robertson–Seymour theorem characterizes minor-closed families as having a finite set of forbidden minors.mixedA mixed graph is a graph that may include both directed and undirected edges.modular1. Modular graph, a graph in which each triple of vertices has at least one median vertex that belongs to shortest paths between all pairs of the triple.2. Modular decomposition, a decomposition of a graph into subgraphs within which all vertices connect to the rest of the graph in the same way.3. Modularity of a graph clustering, the difference of the number of cross-cluster edges from its expected value.monotoneUna propiedad monótona de los grafos es una propiedad que está cerrada bajo los subgrafos: si G tiene una propiedad hereditaria, también debe serlo cada subgrafo de G. Compare hereditario (cerrado bajo subgrafos inducidos) o menor-cerrado (cerrado bajo menores).Gráfico de MooreUn grafo de Moore es un grafo regular en el que el límite de Moore se cumple exactamente. El límite de Moore es una desigualdad que relaciona el grado, el diámetro y el orden de un gráfico, demostrada por Edward F. Moore. Cada gráfico de Moore es una jaula.multigrafoUn multigrafo es un grafo que permite múltiples adyacencias (y, a menudo, bucles automáticos); un gráfico que no se requiere que sea simple.adyacencia múltipleUna adyacencia múltiple o una arista múltiple es un conjunto de más de una arista que tienen todos los mismos puntos finales (en la misma dirección, en el caso de gráficos dirigidos). Un gráfico con múltiples aristas a menudo se denomina multigrafo.multiplicidadLa multiplicidad de una arista es el número de aristas en una adyacencia múltiple. La multiplicidad de un grafo es la multiplicidad máxima de cualquiera de sus aristas.

Norte

norte1. Para la notación de vecindades abiertas y cerradas, vea vecindad.2. A menudo se usa una n minúscula (especialmente en informática) para indicar el número de vértices en un gráfico dado.VecinoVecinoUn vértice que es adyacente a un vértice dado.vecindariovecindarioLa vecindad abierta (o vecindad) de un vértice v es el subgrafo inducido por todos los vértices que son adyacentes a v. La vecindad cerrada se define de la misma manera pero también incluye a la propia v. La vecindad abierta de v en G se puede denotar N _G (v) o N (v), y la vecindad cerrada se puede denotar N _G [ v ] o N [ v ]. Cuando no se especifica la apertura o la clausura de un barrio, se supone que es abierto.la redUn gráfico en el que los atributos (por ejemplo, los nombres) están asociados con los nodos y/o los bordes.nodoUn sinónimo para vértice.sin bordeUn non-edge o anti-edge es un par de vértices que no son adyacentes; los bordes de la gráfica del complemento.gráfico nuloVer gráfico vacío.

O

extraño1. Un ciclo impar es un ciclo cuya duración es impar. La circunferencia impar de un gráfico no bipartito es la longitud de su ciclo impar más corto. Un agujero impar es un caso especial de un ciclo impar: uno que es inducido y tiene cuatro o más vértices.2. Un vértice impar es un vértice cuyo grado es impar. Por el lema del apretón de manos, cada gráfico no dirigido finito tiene un número par de vértices impares.3. Un oído impar es un camino simple o ciclo simple con un número impar de aristas, usado en descomposiciones de oídos impares de gráficos de factor crítico; ver oído.4. Una cuerda impar es una arista que conecta dos vértices que están separados por una distancia impar en un ciclo par. Las cuerdas impares se utilizan para definir gráficos fuertemente cordales.5. Un gráfico impar es un caso especial de un gráfico de Kneser, que tiene un vértice para cada subconjunto de elementos (n − 1) de un conjunto de elementos (2 n − 1) y una arista que conecta dos subconjuntos cuando sus conjuntos correspondientes son desarticular.abierto1. Ver barrio.2. Ver caminar.ordenar1. El orden de un grafo G es el número de sus vértices, | V (G)|. La variable n se usa a menudo para esta cantidad. Véase también tamaño, el número de aristas.2. Un tipo de lógica de grafos; ver primer orden y segundo orden.3. Un orden u ordenamiento de un grafo es una disposición de sus vértices en una secuencia, especialmente en el contexto del ordenamiento topológico (un orden de un grafo acíclico dirigido en el que cada borde va desde un vértice anterior a un vértice posterior en el orden) y ordenación de degeneración (un orden en el que cada vértice tiene un grado mínimo en el subgrafo inducido de él y todos los vértices posteriores).4. Para el orden de un asilo o zarza, véase asilo y zarza.orientaciónorientado1. 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 grafo orientado es aquel al que se le ha asignado una orientación. Entonces, por ejemplo, un poliárbol es un árbol orientado; se diferencia de un árbol dirigido (una arborescencia) en que no hay requisitos 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 eulerianas, orientaciones que son eulerianas; y orientaciones transitivas, orientaciones transitivamente cerradas.2. Grafo orientado, utilizado por algunos autores como sinónimo de grafo dirigido.fuera de gradoVer grado.exteriorVer cara.plano exteriorUn gráfico plano exterior es un gráfico que se puede incrustar en el plano (sin cruces) de modo que todos los vértices estén en la cara exterior del gráfico.

PAGS

senderoUn camino puede ser un camino o un camino sin vértices repetidos y, en consecuencia, bordes (también llamado camino simple), dependiendo de la fuente. Los casos especiales importantes incluyen caminos inducidos y caminos más cortos.descomposición de caminosUna descomposición de caminos de un grafo G es una descomposición de árbol cuyo árbol subyacente es un camino. Su ancho se define de la misma manera que para las descomposiciones de árboles, como uno menos que el tamaño de la bolsa más grande. El ancho mínimo de cualquier descomposición de ruta de G es el ancho de ruta de G.ancho de rutaEl ancho de ruta de un gráfico G es el ancho mínimo de una descomposición de ruta de G. También se puede definir en términos del número de camarilla de una terminación de intervalo de G. Siempre está entre el ancho de banda y el ancho del árbol de G. También se conoce como grosor de intervalo, número de separación de vértices o número de búsqueda de nodos.colganteVer hoja.Perfecto1. Un grafo perfecto es un grafo en el que, en cada subgrafo inducido, el número cromático es igual al número clique. El teorema del gráfico perfecto y el teorema del gráfico perfecto fuerte son dos teoremas sobre gráficos perfectos, el primero demuestra que sus complementos también son perfectos y el segundo demuestra que son exactamente los gráficos sin agujeros impares ni antiagujeros.2. Un grafo perfectamente ordenable es un grafo cuyos vértices se pueden ordenar de tal manera que un algoritmo de coloreo voraz con este ordenamiento colorea de manera óptima cada subgrafo inducido. Los grafos perfectamente ordenables son una subclase de los grafos perfectos.3. Un emparejamiento perfecto es un emparejamiento que satura todos los vértices; ver coincidencia.4. Una factorización perfecta en 1 es una partición de los bordes de un gráfico en emparejamientos perfectos, de modo que cada dos emparejamientos formen un ciclo hamiltoniano.periférico1. Un ciclo periférico o ciclo no separador es un ciclo con un puente como máximo.2. Un vértice periférico es un vértice cuya excentricidad es máxima. En un árbol, esto debe ser una hoja.petersen1. Julius Petersen (1839–1910), teórico de grafos danés.2. El gráfico de Petersen, un gráfico de 10 vértices y 15 aristas que se usa con frecuencia como contraejemplo.3. El teorema de Petersen de que todo gráfico cúbico sin puente tiene una correspondencia perfecta.planoUn gráfico plano es un gráfico que tiene una incrustación en el plano euclidiano. Un gráfico plano es un gráfico plano para el que ya se ha fijado una incrustación particular. Un gráfico k -planar es aquel que se puede dibujar en el plano con un máximo de k cruces por borde.poliárbolUn poliárbol es un árbol orientado; de manera equivalente, un gráfico acíclico dirigido cuyo gráfico no dirigido subyacente es un árbol.energía1. Una potencia gráfica G de una gráfica G es otra gráfica en el mismo conjunto de vértices; dos vértices son adyacentes en G cuando están a una distancia como máximo k en G. Un poder de hoja es un concepto estrechamente relacionado, derivado de un poder de un árbol al tomar el subgrafo inducido por las hojas del árbol.2. El análisis gráfico de potencia es un método para analizar redes complejas mediante la identificación de clicas, bicliques y estrellas dentro de la red.3. Las leyes de potencias en las distribuciones de grados de redes libres de escala son un fenómeno en el que el número de vértices de un grado dado es proporcional a una potencia del grado.predecesorUn vértice que viene antes de un vértice dado en un camino dirigido.correcto1. Un subgráfico propio es un subgráfico que elimina al menos un vértice o arista en relación con el gráfico completo; para gráficos finitos, los subgráficos propios nunca son isomorfos al gráfico completo, pero para gráficos infinitos pueden serlo.2. Una coloración adecuada es una asignación de colores a los vértices de un gráfico (una coloración) que asigna diferentes colores a los extremos de cada borde; ver color.3. Un gráfico de intervalo propio o un gráfico de arco circular propio es un gráfico de intersección de una colección de intervalos o arcos circulares (respectivamente) de modo que ningún intervalo o arco contiene otro intervalo o arco. Los gráficos de intervalos propios también se denominan gráficos de intervalos unitarios (porque siempre se pueden representar mediante intervalos unitarios) o gráficos de indiferencia.propiedadUna propiedad de un gráfico es algo que puede ser verdadero para algunos gráficos y falso para otros, y que depende solo de la estructura del gráfico y no de información incidental como las etiquetas. Las propiedades de los gráficos pueden describirse de manera equivalente en términos de clases de gráficos (los gráficos que tienen una propiedad determinada). De manera más general, una propiedad de gráfico también puede ser una función de gráficos que nuevamente es independiente de la información incidental, como el tamaño, el orden o la secuencia de grados de un gráfico; esta definición más general de una propiedad también se llama invariante del gráfico.pseudobosqueUn pseudobosque es un grafo no dirigido en el que cada componente conectado tiene como máximo un ciclo, o un grafo dirigido en el que cada vértice tiene como máximo una arista saliente.seudógrafoUn seudógrafo es un gráfico o multigrafo que permite bucles automáticos.

Q

gráfico de cuasilíneaUn gráfico de cuasilínea o gráfico localmente co-bipartito es un gráfico en el que la vecindad abierta de cada vértice se puede dividir en dos camarillas. Estos gráficos son siempre sin garras e incluyen como caso especial los gráficos de líneas. Se utilizan en la teoría de la estructura de grafos sin garras.secuencia gráfica casi aleatoriaUna secuencia de gráficos cuasialeatorios es una secuencia de gráficos que comparte varias propiedades con una secuencia de gráficos aleatorios generados según el modelo de gráficos aleatorios de Erdős-Rényi.carcajUn carcaj es un multigrafo dirigido, como se usa en la teoría de categorías. Los bordes de una aljaba se llaman flechas.

R

radioEl radio de un gráfico es la excentricidad mínima de cualquier vértice.RamanujanUn gráfico de Ramanujan es un gráfico cuya expansión espectral es lo más grande posible. Es decir, es un gráfico d -regular, tal que el segundo valor propio más grande de su matriz de adyacencia es como máximo .rayoUn rayo, en un gráfico infinito, es un camino simple infinito con exactamente un punto final. Los extremos de un gráfico son clases de equivalencia de rayos.accesibilidadLa capacidad de pasar de un vértice a otro dentro de un gráfico.accesibleTiene una accesibilidad afirmativa. Se dice que un vértice y es alcanzable desde un vértice x si existe un camino de x a y.reconocibleEn el contexto de la conjetura de reconstrucción, una propiedad gráfica es reconocible si su verdad puede determinarse a partir de la cubierta del gráfico. Se sabe que muchas propiedades gráficas son reconocibles. Si la conjetura de reconstrucción es verdadera, todas las propiedades del gráfico son reconocibles.reconstrucciónLa conjetura de reconstrucción establece que cada gráfico no dirigido G está determinado únicamente por su mazo, un conjunto múltiple de gráficos formado al eliminar un vértice de G de todas las formas posibles. En este contexto, la reconstrucción es la formación de un gráfico a partir de su cubierta.rectánguloUn ciclo simple que consta exactamente de cuatro aristas y cuatro vértices.regularUn grafo es d -regular cuando todos sus vértices tienen grado d. Un grafo regular es un grafo que es d -regular para alguna d.torneo regularUn torneo regular es un torneo donde el grado de entrada es igual al grado de salida para todos los vértices.reversoVéase transponer.raíz1. Un vértice designado en un gráfico, particularmente en árboles dirigidos y gráficos con raíces.2. La operación inversa a una potencia gráfica: una raíz k -ésima de una gráfica G es otra gráfica en el mismo conjunto de vértices tal que dos vértices son adyacentes en G si y solo si tienen una distancia como máximo k en la raíz.

S

segundo ordenLa lógica de segundo orden de los gráficos es una forma de lógica en la que las variables pueden representar vértices, aristas, conjuntos de vértices y (a veces) conjuntos de aristas. Esta lógica incluye predicados para probar si un vértice y una arista son incidentes, así como si un vértice o una arista pertenecen a un conjunto. Para distinguirse de la lógica de primer orden, en la que las variables solo pueden representar vértices.saturadoVer emparejamiento.número de búsquedaNúmero de búsqueda de nodo es sinónimo de ancho de ruta.bucle automáticoSinónimo de bucle.vértice separadorVéase punto de articulación.número de separaciónEl número de separación de vértices es un sinónimo de ancho de ruta.simple1. Un gráfico simple es un gráfico sin bucles y sin adyacencias múltiples. Es decir, cada arista conecta dos extremos distintos y no hay dos aristas que tengan los mismos extremos. Una arista simple es una arista que no forma parte de una adyacencia múltiple. En muchos casos, se supone que los gráficos son simples a menos que se especifique lo contrario.2. Un camino simple o un ciclo simple es un camino o ciclo que no tiene vértices repetidos y, en consecuencia, tampoco aristas repetidas.piletaUn sumidero, en un gráfico dirigido, es un vértice sin bordes salientes (el grado de salida es igual a 0).TallaEl tamaño de un gráfico G es el número de sus aristas, | mi (sol)|. La variable m se usa a menudo para esta cantidad. Véase también orden, el número de vértices.red de mundo pequeñoUna red de mundo pequeño es un gráfico en el que la mayoría de los nodos no son vecinos entre sí, pero se puede llegar a la mayoría de los nodos desde cualquier otro nodo mediante un pequeño número de saltos o pasos. Específicamente, una red de mundo pequeño se define como un gráfico donde la distancia típica L entre dos nodos elegidos al azar (el número de pasos requeridos) crece proporcionalmente al logaritmo del número de nodos N en la red.gruñidoUn snark es un gráfico cúbico simple, conectado y sin puente con un índice cromático igual a 4.fuenteUna fuente, en un gráfico dirigido, es un vértice sin aristas entrantes (grado de entrada es igual a 0).espacioEn la teoría de gráficos algebraicos, varios espacios vectoriales sobre el campo binario pueden estar asociados con un gráfico. Cada uno tiene conjuntos de aristas o vértices para sus vectores, y diferencia simétrica de conjuntos como su operación de suma de vectores. El espacio de aristas es el espacio de todos los conjuntos de aristas, y el espacio de los vértices es el espacio de todos los conjuntos de vértices. El espacio de corte es un subespacio del espacio de borde que tiene los conjuntos de corte del gráfico como sus elementos. El espacio del ciclo tiene los subgrafos de expansión eulerianos como sus elementos.llaveUna llave inglesa es un gráfico (generalmente disperso) cuyas distancias de ruta más cortas se aproximan a las de un gráfico denso u otro espacio métrico. Las variaciones incluyen llaves inglesas geométricas, gráficos cuyos vértices son puntos en un espacio geométrico; llaves de árbol, árboles de expansión de un gráfico cuyas distancias se aproximan a las distancias del gráfico, y llaves de árbol, subgráficos dispersos de un gráfico denso cuyas distancias se aproximan a las distancias del gráfico original. Una llave inglesa codiciosa es una llave inglesa construida por un algoritmo codicioso, generalmente uno que considera todos los bordes desde el más corto hasta el más largo y mantiene los que son necesarios para preservar la aproximación de la distancia.abarcandoUn subgrafo se expande cuando incluye todos los vértices del grafo dado. Los casos importantes incluyen árboles de expansión, subgráficos de expansión que son árboles y coincidencias perfectas, subgráficos de expansión que son coincidencias. Un subgrafo de expansión también se puede llamar factor, especialmente (pero no solo) cuando es regular.escasoUn gráfico disperso es aquel que tiene pocas aristas en relación con su número de vértices. En algunas definiciones, la misma propiedad también debería ser cierta para todos los subgráficos del gráfico dado.espectralespectroEl espectro de un gráfico es la colección de valores propios de su matriz de adyacencia. La teoría de gráficos espectrales es la rama de la teoría de gráficos que utiliza espectros para analizar gráficos. Véase también expansión espectral.separar1. Un grafo dividido es un grafo cuyos vértices se pueden dividir en un grupo y un conjunto independiente. Una clase relacionada de gráficos, los gráficos de doble división, se utilizan en la demostración del teorema del gráfico perfecto fuerte.2. Una división de un gráfico arbitrario es una partición de sus vértices en dos subconjuntos no vacíos, de modo que los bordes que abarcan este corte forman un subgráfico bipartito completo. Las divisiones de un gráfico se pueden representar mediante una estructura de árbol denominada descomposición dividida. Una división se denomina división fuerte cuando no está atravesada por ninguna otra división. Una división se llama no trivial cuando ambos lados tienen más de un vértice. Un gráfico se llama primo cuando no tiene divisiones no triviales.cuadrado1. El cuadrado de una gráfica G es la potencia gráfica G; en la otra dirección, G es la raíz cuadrada de G. El medio cuadrado de un gráfico bipartito es el subgráfico de su cuadrado inducido por un lado de la bipartición.2. Un gráfico cuadrado es un gráfico plano que se puede dibujar de modo que todas las caras acotadas sean ciclos de 4 y todos los vértices de grado ≤ 3 pertenezcan a la cara exterior.3. Un gráfico de cuadrícula cuadrada es un gráfico de celosía definido a partir de puntos en el plano con coordenadas enteras conectadas por aristas de longitud unitaria.estableUn conjunto estable es sinónimo de un conjunto independiente.estrellaUna estrella es un árbol con un vértice interno; de manera equivalente, es un grafo bipartito completo K _{1, n} para algún n ≥ 2. El caso especial de una estrella con tres hojas se llama garra.fuerzaLa fuerza de un gráfico es la relación mínima entre el número de aristas eliminadas del gráfico y los componentes creados, sobre todas las eliminaciones posibles; es análogo a la tenacidad, basado en la remoción de vértices.fuerte1. Para conectividad fuerte y componentes fuertemente conectados de grafos dirigidos, vea conectado y componente. Una orientación fuerte es una orientación que está fuertemente conectada; ver orientación.2. Para conocer el teorema del gráfico perfecto fuerte, véase perfecto.3. Un grafo fuertemente regular es un grafo regular en el que cada dos vértices adyacentes tienen el mismo número de vecinos compartidos y cada dos vértices no adyacentes tienen el mismo número de vecinos compartidos.4. Un grafo fuertemente cordal es un grafo cordal en el que cada ciclo par de longitud seis o más tiene una cuerda impar.5. Un grafo fuertemente perfecto es un grafo en el que cada subgrafo inducido tiene un conjunto independiente que cumple con todas las camarillas máximas. Los gráficos de Meyniel también se denominan "gráficos muy fuertemente perfectos" porque en ellos, cada vértice pertenece a un conjunto independiente.subbosqueUn subgrafo de un bosque.subgrafoUn subgrafo de un grafo G es otro grafo formado a partir de un subconjunto de los vértices y aristas de G. El subconjunto de vértices debe incluir todos los extremos del subconjunto de aristas, pero también puede incluir vértices adicionales. Un subgrafo expansivo es aquel que incluye todos los vértices del grafo; un subgrafo inducido es aquel que incluye todas las aristas cuyos extremos pertenecen al subconjunto de vértices.subárbolUn subárbol es un subgrafo conexo de un árbol. A veces, para árboles con raíz, los subárboles se definen como un tipo especial de subgrafo conectado, formado por todos los vértices y aristas accesibles desde un vértice elegido.sucesorUn vértice que viene después de un vértice dado en un camino dirigido.superconcentradorUn superconcentrador es un grafo con dos subconjuntos designados y de igual tamaño de vértices I y O, de modo que por cada dos subconjuntos de igual tamaño S de I y T O existe una familia de caminos disjuntos que conectan cada vértice en S con un vértice en t _ Algunas fuentes requieren además que un superconcentrador sea un gráfico acíclico dirigido, con I como fuentes y O como sumideros.supergrafoUn gráfico formado al agregar vértices, aristas o ambos a un gráfico dado. Si H es un subgrafo de G, entonces G es un supergrafo de H.

T

theta1. Un gráfico theta es la unión de tres trayectorias internamente disjuntas (simples) que tienen los mismos dos vértices finales distintos.2. El gráfico theta de una colección de puntos en el plano euclidiano se construye construyendo un sistema de conos que rodean cada punto y agregando un borde por cono, hasta el punto cuya proyección sobre un rayo central del cono es más pequeña.3. El número de Lovász o función theta de Lovász de un gráfico es un gráfico invariante relacionado con el número de clique y el número cromático que se puede calcular en tiempo polinomial mediante programación semidefinida.gráfico de ThomsenEl gráfico de Thomsen es un nombre para el gráfico bipartito completo .topológico1. Un grafo topológico es una representación de los vértices y aristas de un grafo por puntos y curvas en el plano (no necesariamente evitando los cruces).2. La teoría topológica de grafos es el estudio de las incrustaciones de grafos.3. La clasificación topológica es el problema algorítmico de organizar un gráfico acíclico dirigido en un orden topológico, una secuencia de vértices tal que cada borde va desde un vértice anterior a un vértice posterior en la secuencia.totalmente desconectadoSinónimo de sin bordes.recorridoUn sendero cerrado, un paseo que comienza y termina en el mismo vértice y no tiene aristas repetidas. Los recorridos de Euler son recorridos que utilizan todos los bordes del gráfico; ver Euleriano.torneoUn torneo es una orientación de un gráfico completo; es decir, es un grafo dirigido tal que cada dos vértices están conectados exactamente por una arista dirigida (que va en solo una de las dos direcciones entre los dos vértices).rastreableUn gráfico trazable es un gráfico que contiene un camino hamiltoniano.senderoUn paseo sin aristas repetidas.transitivoQue tiene que ver con la propiedad transitiva. El cierre transitivo de un grafo dirigido dado es un grafo en el mismo conjunto de vértices que tiene una arista de un vértice a otro siempre que el grafo original tenga un camino que conecte los mismos dos vértices. Una reducción transitiva de un grafo es un grafo mínimo que tiene la misma clausura transitiva; Los gráficos acíclicos dirigidos tienen una reducción transitiva única. Una orientación transitiva es una orientación de un gráfico que es su propio cierre transitivo; existe solo para gráficos de comparabilidad.transponerEl gráfico de transposición de un gráfico dirigido dado es un gráfico en los mismos vértices, con cada borde invertido en la dirección. También se le puede llamar el inverso o el reverso del gráfico.árbol1. Un árbol es un grafo no dirigido que es a la vez conexo y acíclico, o un grafo dirigido en el que existe un recorrido único desde un vértice (la raíz del árbol) hasta todos los vértices restantes.2. Un k -árbol es un gráfico formado al unir (k + 1) -camarillas en k -camarillas compartidas. Un árbol en el sentido ordinario es un 1 -árbol según esta definición.descomposición del árbolUna descomposición en árbol de un grafo G es un árbol cuyos nodos están etiquetados con conjuntos de vértices de G; estos conjuntos se llaman bolsas. Para cada vértice v, las bolsas que contienen v deben inducir un subárbol del árbol, y para cada arista uv debe existir una bolsa que contenga tanto a u como a v. El ancho de la descomposición de un árbol es uno menos que el número máximo de vértices en cualquiera de sus bolsas; el ancho de árbol de G es el ancho mínimo de cualquier descomposición de árbol de G.ancho del árbolEl ancho de árbol de un gráfico G es el ancho mínimo de una descomposición de árbol de G. También se puede definir en términos del número de camarilla de una terminación cordal de G, el orden de un refugio de G o el orden de una zarza de G.triánguloUn ciclo de longitud tres en un gráfico. Un gráfico sin triángulos es un gráfico no dirigido que no tiene ningún subgráfico de triángulos.Turan1. Pal Turan2. Un grafo de Turán es un grafo multipartito completo balanceado.3. El teorema de Turán establece que los grafos de Turán tienen el máximo número de aristas entre todos los grafos libres de clique de un orden dado.4. El problema de la fábrica de ladrillos de Turán pide el número mínimo de cruces en un dibujo de un grafo bipartito completo.

Tu

no dirigidoUn grafo no dirigido es un grafo en el que los dos extremos de cada arista no se distinguen entre sí. Véase también dirigida y mixta. En un gráfico mixto, un borde no dirigido es nuevamente uno en el que los puntos finales no se distinguen entre sí.uniformeUna hipergrafía es k -uniforme cuando todas sus aristas tienen k extremos, y uniforme cuando es k -uniforme para algún k. Por ejemplo, los gráficos ordinarios son lo mismo que los hipergráficos de 2 uniformes.universal1. Un gráfico universal es un gráfico que contiene como subgráficos todos los gráficos de una familia de gráficos dada, o todos los gráficos de un tamaño u orden dado dentro de una familia de gráficos dada.2. Un vértice universal (también llamado vértice o vértice dominante) es un vértice que es adyacente a todos los demás vértices 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 grafos, un vértice que se cuantifica universalmente en una fórmula puede llamarse vértice universal para esa fórmula.gráfico no ponderadoUn gráfico a cuyos vértices y aristas no se les ha asignado un peso s; lo contrario de un gráfico ponderado.gráfico de utilidadEl gráfico de utilidad es un nombre para el gráfico bipartito completo .

V

VVéase conjunto de vértices.valenciaSinónimo de grado.vérticeUn vértice (vértices en plural) es (junto con los bordes) una de las dos unidades básicas a partir de las cuales se construyen los gráficos. Los vértices de los gráficos a menudo se consideran objetos atómicos, sin estructura interna.corte de vérticeconjunto separadorUn conjunto de vértices cuya eliminación desconecta el gráfico. Un corte de un vértice se denomina punto de articulación o vértice de corte.conjunto de vérticesEl conjunto de vértices de un gráfico G dado, a veces denotado por V (G).vérticesVéase vértice.viendo1. Vadim G. Vizing2. El teorema de Vizing de que el índice cromático es como máximo un grado más que el grado máximo.3. La conjetura de Vizing sobre el número de dominación de productos cartesianos de grafos.volumenLa suma de los grados de un conjunto de vértices.

W

WLa letra W se usa en notación para gráficos de ruedas y gráficos de molinos de viento. La notación no está estandarizada.Wagner1. Klaus Wagner2. El gráfico de Wagner, una escalera de Möbius de ocho vértices.3. El teorema de Wagner que caracteriza grafos planos por sus menores prohibidos.4. El teorema de Wagner que caracteriza los grafos libres de K ₅ -minor.caminarUn paseo es una secuencia finita o infinita de aristas que une una secuencia de vértices. Los paseos también se denominan a veces cadenas. Un recorrido es abierto si sus vértices primero y último son distintos, y cerrado si se repiten.débilmente conectadoUn grafo dirigido se llama débilmente conectado si al reemplazar todas sus aristas dirigidas con aristas no dirigidas se produce un grafo conectado (no dirigido).pesoUn valor numérico, asignado como una etiqueta a un vértice o borde de un gráfico. El peso de un subgrafo es la suma de los pesos de los vértices o aristas dentro de ese subgrafo.gráfico ponderadoUn gráfico a cuyos vértices o aristas se les ha asignado un peso s. Un gráfico ponderado por vértices tiene pesos en sus vértices y un gráfico ponderado por bordes tiene pesos en sus bordes.bien coloreadoUn gráfico bien coloreado es un gráfico cuyas codiciosas coloraciones utilizan el mismo número de colores.bien cubiertoUn gráfico bien cubierto es un gráfico cuyos conjuntos independientes máximos tienen el mismo tamaño.ruedaUn gráfico de rueda es un gráfico formado al agregar un vértice universal a un ciclo simple.ancho1. Un sinónimo de degeneración.2. Para otras invariantes gráficas conocidas como ancho, consulte ancho de banda, ancho de rama, ancho de camarilla, ancho de ruta y ancho de árbol.3. El ancho de una descomposición de árbol o descomposición de camino es uno menos que el tamaño máximo de una de sus bolsas, y puede usarse para definir ancho de árbol y ancho de camino.4. El ancho de un gráfico acíclico dirigido es la máxima cardinalidad de una anticadena.molinoUn gráfico de molino de viento es la unión de una colección de camarillas, todas del mismo orden entre sí, con un vértice compartido que pertenece a todas las camarillas y todos los demás vértices y aristas son distintos.