TEORÍA DE TÉRMINOS DE GRAFOS

En la teoría de conjuntos y sus aplicaciones a través de las matemáticas , una clase es una colección de conjuntos (o, a veces, otros objetos matemáticos) que pueden definirse sin ambigüedades mediante una propiedad que comparten todos sus miembros. La definición precisa de "clase" depende del contexto fundacional. En el trabajo sobre la teoría de conjuntos de Zermelo-Fraenkel , la noción de clase es informal, mientras que otras teorías de conjuntos, como la teoría de conjuntos de von Neumann-Bernays-Gödel , axiomatizan la noción de "clase adecuada", por ejemplo, como entidades que no son miembros de otra entidad

Una clase que no es un conjunto (informalmente en Zermelo – Fraenkel) se llama una clase apropiada , y una clase que es un conjunto a veces se llama una clase pequeña . Por ejemplo, la clase de todos los números ordinales y la clase de todos los conjuntos son clases apropiadas en muchos sistemas formales.

En los escritos teóricos establecidos de Quine, la frase "clase máxima" se usa a menudo en lugar de la frase "clase apropiada" enfatizando que en los sistemas que él considera, ciertas clases no pueden ser miembros, y por lo tanto son el término final en cualquier cadena de membresía a la que ellos pertenecen.

Fuera de la teoría de conjuntos, la palabra "clase" a veces se usa como sinónimo de "conjunto". Este uso data de un período histórico en el que las clases y los conjuntos no se distinguieron como lo son en la terminología moderna de la teoría de conjuntos. Muchas discusiones sobre "clases" en el siglo XIX y anteriores se refieren realmente a conjuntos, o tal vez se llevan a cabo sin considerar que ciertas clases pueden dejar de ser conjuntos.

Ejemplos [ editar ]

La colección de todos los objetos algebraicos de un tipo dado generalmente será una clase apropiada. Los ejemplos incluyen la clase de todos los grupos , la clase de todos los espacios vectoriales y muchos otros. En la teoría de categorías , una categoría cuya colección de objetos forma una clase adecuada (o cuya colección de morfismos forma una clase adecuada) se denomina categoría grande .

Los números surrealistas son una clase adecuada de objetos que tienen las propiedades de un campo .

Dentro de la teoría de conjuntos, muchas colecciones de conjuntos resultan ser clases apropiadas. Los ejemplos incluyen la clase de todos los conjuntos, la clase de todos los números ordinales y la clase de todos los números cardinales.

Una forma de demostrar que una clase es adecuada es colocarla en biyección con la clase de todos los números ordinales. Este método se utiliza, por ejemplo, en la prueba de que no hay una red completa libre en tres o más generadores .

Paradojas [ editar ]

Las paradojas de la ingenua teoría de conjuntos pueden explicarse en términos del supuesto tácito inconsistente de que "todas las clases son conjuntos". Con una base rigurosa, estas paradojas sugieren pruebas de que ciertas clases son adecuadas (es decir, que no son conjuntos). Por ejemplo, la paradoja de Russell sugiere una prueba de que la clase de todos los conjuntos que no se contienen es adecuada, y la paradoja de Burali-Forti sugiere que la clase de todos los números ordinaleses correcto Las paradojas no surgen con las clases porque no existe una noción de clases que contengan clases. De lo contrario, uno podría, por ejemplo, definir una clase de todas las clases que no se contienen, lo que llevaría a una paradoja de Russell para las clases. Un conglomerado , por otro lado, puede tener clases apropiadas como miembros, aunque la teoría de los conglomerados aún no está bien establecida. ^{[ cita requerida ]}

Clases en teorías de conjuntos formales [ editar ]

La teoría de conjuntos ZF no formaliza la noción de clases, por lo que cada fórmula con clases debe reducirse sintácticamente a una fórmula sin clases. ^[1] Por ejemplo, uno puede reducir la fórmula$${\ displaystyle A = \ {x \ mid x = x \}} a $${\ displaystyle \ forall x (x \ en A \ leftrightarrow x = x)}. Semánticamente, en un metalenguaje , las clases se pueden describir como clases de equivalencia de fórmulas lógicas: Si$${\ displaystyle {\ mathcal {A}}}es una estructura que interpreta ZF, entonces la expresión del generador de clases de lenguaje de objetos$${\ displaystyle \ {x \ mid \ phi \}} se interpreta en $${\ displaystyle {\ mathcal {A}}} por la colección de todos los elementos del dominio de $${\ displaystyle {\ mathcal {A}}} en la que $${\ displaystyle \ lambda x \ phi}sostiene; por lo tanto, la clase se puede describir como el conjunto de todos los predicados equivalentes a$${\ displaystyle \ phi} (incluso $${\ displaystyle \ phi}sí mismo). En particular, se puede identificar la "clase de todos los conjuntos" con el conjunto de todos los predicados equivalentes a$${\ displaystyle x = x.}

Debido a que las clases no tienen ningún estado formal en la teoría de ZF, los axiomas de ZF no se aplican inmediatamente a las clases. Sin embargo, si un cardenal inaccesible $${\ displaystyle \ kappa}se supone, entonces los conjuntos de menor rango forman un modelo de ZF (un universo Grothendieck ), y sus subconjuntos pueden considerarse como "clases".

En ZF, el concepto de una función también se puede generalizar a clases. Una función de clase no es una función en el sentido habitual, ya que no es un conjunto; es más bien una fórmula$${\ displaystyle \ Phi (x, y)} con la propiedad que para cualquier conjunto $${\ displaystyle x} no hay más de un conjunto $${\ displaystyle y} tal que el par $${\ displaystyle (x, y)} satisface $${\ displaystyle \ Phi.} Por ejemplo, la función de clase que asigna cada conjunto a su sucesor puede expresarse como la fórmula $${\ displaystyle y = x \ cup \ {x \}.} El hecho de que el par ordenado $${\ displaystyle (x, y)} satisface $${\ displaystyle \ Phi} puede expresarse con la notación abreviada $${\ displaystyle \ Phi (x) = y.}

Otro enfoque lo adoptan los axiomas von Neumann – Bernays – Gödel (NBG); Las clases son los objetos básicos en esta teoría, y un conjunto se define como una clase que es un elemento de otra clase. Sin embargo, los axiomas de existencia de clase de NBG están restringidos para que solo cuantifiquen sobre conjuntos, en lugar de sobre todas las clases. Esto hace que NBG sea una extensión conservadora de ZF.

La teoría de conjuntos de Morse-Kelley admite las clases adecuadas como objetos básicos, como NBG, pero también permite la cuantificación sobre todas las clases adecuadas en sus axiomas de existencia de clase. Esto hace que MK sea estrictamente más fuerte que NBG y ZF.

En otras teorías de conjuntos, como New Foundations o la teoría de los semisets , el concepto de "clase apropiada" todavía tiene sentido (no todas las clases son conjuntos) pero el criterio de la edad no está cerrado bajo los subconjuntos. Por ejemplo, cualquier teoría de conjuntos con un conjunto universal tiene clases apropiadas que son subclases de conjuntos.

En la teoría de gráficos , el teorema de Vizing establece que cada gráfico simple no dirigido puede ser coloreado con bordes usando una cantidad de colores que es como máximo uno más grande que el grado máximo Δ del gráfico. Siempre son necesarios al menos Δ colores, por lo que los gráficos no dirigidos se pueden dividir en dos clases: gráficos de "clase uno" para los que son suficientes los colores Δ , y gráficos de "clase dos" para los que son necesarios los colores Δ + 1 . El teorema lleva el nombre de Vadim G. Vizing, quien lo publicó en 1964.

Ejemplos [ editar ]

Cuando Δ = 1 , el gráfico G debe ser una coincidencia, sin dos bordes adyacentes, y su número cromático de borde es uno. Es decir, todos los gráficos con Δ ( G ) = 1 son de clase uno.

Cuando Δ = 2 , el gráfico G debe ser una unión disjunta de caminos y ciclos . Si todos los ciclos son pares, pueden ser de 2 bordes alternando los dos colores alrededor de cada ciclo. Sin embargo, si existe al menos un ciclo impar, entonces no es posible la coloración de 2 bordes. Es decir, un gráfico con Δ = 2 es de clase uno si y solo si es bipartito .

Los multigrafos en general no obedecen el teorema de Vizing. Por ejemplo, el multigrafo formado al duplicar cada borde de un triángulo tiene un grado máximo de cuatro pero no puede ser coloreado con menos de seis colores.

Prueba [ editar ]

Esta prueba está inspirada en Diestel (2000) .

Deje G  = ( V ,  E ) ser un gráfico simple no dirigido. Procedemos por inducción en m , el número de aristas. Si el gráfico está vacío, el teorema es trivial. Dejar que m  > 0 y supongamos que un adecuado (Δ + 1) existe -Edge-coloración para todos G  -  xy donde xy  ∈  E .

Decimos que falta el color α ∈ {1, ..., Δ + 1 } en x  ∈  V con respecto al color de borde apropiado (Δ + 1) c si c ( xy ) ≠ α para todo y  ∈ N ( x ) . Además, deje que la ruta α / β de x denote la ruta máxima única que comienza en x con el borde de color α y alterna los colores de los bordes (el segundo borde tiene color β , el tercer borde tiene color α y así sucesivamente), su longitud puede ser 0 .

Sea β el color que falta en y _k con respecto a c ₀ , entonces β también falta en y _k con respecto a c _i para todos 0 ≤  i  ≤  k . Tenga en cuenta que no puede faltar β en x , de lo contrario podríamos extender fácilmente c _k , por lo tanto, un borde con color β incide en x para todo c _j . De la maximidad de k , existe 1 ≤  i  <  ktal que c ₀ ( xy _i ) = β . De la definición de c ₁ , ..., c _k esto se cumple:

c ₀ ( xy _i ) =  c _i −1 ( xy _i ) =  c _k ( xy _i −1 ) = β

Sea P la ruta α / β de y _k con respecto a c _k . De (1), P tiene que terminar en x . Pero α falta en x , por lo que tiene que terminar con un borde de color β . Por lo tanto, el último borde de P es y _i −1 x . Ahora, dejemos que P ' sea ​​la ruta α / β desde y _i −1 con respecto a c _i −1 . Dado que P ' está determinado de forma única y los bordes internos deP no se cambia en c ₀ , ..., c _k , la ruta P ' usa los mismos bordes que P en orden inverso y visita y _k . El borde que conduce a y _k tiene claramente un color α . Pero β falta en y _k , entonces P ' termina en y _k . Lo cual es una contradicción con (1) anterior.

Clasificación de gráficos [ editar ]

Varios autores han proporcionado condiciones adicionales que clasifican algunos gráficos como de clase uno o clase dos, pero no proporcionan una clasificación completa. Por ejemplo, si los vértices del grado máximo Δ en un gráfico G forman un conjunto independiente , o más generalmente si el subgrafo inducido para este conjunto de vértices es un bosque, entonces G debe ser de clase uno. ^[1]

Erdős y Wilson (1977) mostraron que casi todos los gráficos son de clase uno. Es decir, en el modelo Erdős-Rényi de gráficos aleatorios, en el que todos los gráficos de n -vértices son igualmente probables, sea p ( n ) la probabilidad de que un gráfico de n -vértices extraído de esta distribución sea de clase uno; entonces p ( n ) se acerca a uno en el límite cuando n va al infinito. Para límites más precisos sobre la velocidad a la que p ( n ) converge en uno, vea Frieze et al. (1988) .

Gráficos planos [ editar ]

Vizing (1965) mostró que un gráfico plano es de clase uno si su grado máximo es al menos ocho. En contraste, observó que para cualquier grado máximo en el rango de dos a cinco, existen gráficos planos de la clase dos. Para el grado dos, cualquier ciclo impar es un gráfico de este tipo, y para el grado tres, cuatro y cinco, estos gráficos pueden construirse a partir de sólidos platónicos reemplazando un borde simple por un camino de dos bordes adyacentes.

En la conjetura del gráfico plano de Vizing , Vizing (1965) afirma que todos los gráficos simples y planos con un grado máximo de seis o siete son de clase uno, cerrando los casos posibles restantes. Sanders y Zhao (2001) probaron parcialmente la conjetura del gráfico plano de Vizing al mostrar que todos los gráficos planos con un grado máximo de siete son de clase uno. Por lo tanto, el único caso de la conjetura que permanece sin resolver es el de grado máximo seis. Esta conjetura tiene implicaciones para la conjetura de coloración total .

Las gráficas planas de la clase dos construidas por subdivisión de los sólidos platónicos no son regulares: tienen vértices de grado dos, así como vértices de grado superior. El teorema de cuatro colores (probado por Appel y Haken (1976) ) sobre la coloración de vértices de gráficos planos, es equivalente a la afirmación de que cada gráfico plano regular sin puente de 3 es de clase uno ( Tait 1880 ).

Gráficos en superficies no planas [ editar ]

En 1969, Branko Grünbaum conjeturó que cada gráfico tridimensional con una incrustación poliédrica en cualquier colector orientado en dos dimensiones , como un toro, debe ser de clase uno. En este contexto, una incrustación poliédrica es una incrustación de gráficos de modo que cada cara de la incrustación sea topológicamente un disco y de manera que el gráfico dual de la incrustación sea simple, sin auto-bucles o adyacencias múltiples. Si es cierto, esto sería una generalización del teorema de los cuatro colores, que Tait demostró que es equivalente a la afirmación de que los gráficos 3-regulares con una incrustación poliédrica en una esfera son de clase uno. Sin embargo, Kochol (2009)demostró que la conjetura es falsa al encontrar snarks que tienen incrustaciones poliédricas en superficies orientables de alto género. Sobre la base de esta construcción, también demostró que es NP-completo decir si un gráfico incrustado poliédricamente es de clase uno. ^[2]

Algoritmos [ editar ]

Misra y Gries (1992) describen un algoritmo de tiempo polinómico para colorear los bordes de cualquier gráfico con colores Δ + 1 , donde Δ es el grado máximo del gráfico. Es decir, el algoritmo usa el número óptimo de colores para los gráficos de la clase dos, y usa como máximo un color más del necesario para todos los gráficos. Su algoritmo sigue la misma estrategia que la prueba original de Vizing de su teorema: comienza con un gráfico incoloro y luego encuentra repetidamente una forma de recolorear el gráfico para aumentar el número de bordes coloreados en uno.

Más específicamente, suponga que uv es un borde incoloro en un gráfico parcialmente coloreado. El algoritmo de Misra y Gries puede interpretarse como la construcción de un pseudoforest P dirigido (un gráfico en el que cada vértice tiene como máximo un borde saliente) en los vecinos de u : para cada vecino p de u , el algoritmo encuentra un color c que es no utilizado por cualquiera de los bordes incidente a p , encuentra el vértice q (si existe) para el cual borde uq es de color c , y añade pq como un borde a P . Hay dos casos:

• Si el pseudoforest P construido de esta manera contiene una ruta desde v hasta un vértice w que no tiene bordes salientes en P , entonces hay un color c que está disponible tanto en u como en w . Volver a colorear el borde uw con el color c permite que los colores del borde restantes se desplacen un paso a lo largo de este camino: para cada vértice p en el camino, el borde hacia arriba toma el color que el sucesor de p utilizó en el camino. Esto lleva a una nueva coloración que incluye edge uv .
• Si, por otro lado, el camino que comienza desde v en el pseudoforest P conduce a un ciclo, sea w el vecino de u en el cual el camino se une al ciclo, c sea ​​el color del borde uw , y sea d un color que ninguno de los bordes usa en el vértice u . Entonces intercambio de colores c y d en una cadena Kempe ya sea rompe el ciclo o el borde en el que la trayectoria se une el ciclo, lo que lleva al caso anterior.

Con algunas estructuras de datos simples para realizar un seguimiento de los colores que se utilizan y están disponibles en cada vértice, la construcción de P y los pasos de recoloración del algoritmo se pueden implementar en el tiempo O ( n ) , donde n es el número de vértices en El gráfico de entrada. Dado que estos pasos deben repetirse m veces, con cada repetición aumentando el número de bordes coloreados en uno, el tiempo total es O ( mn ) .

En un informe técnico no publicado, Gabow et al. (1985) afirmó un más rápido$${\ displaystyle O (m {\ sqrt {n}} \ log n)}límite de tiempo para el mismo problema de colorear con Δ + 1 colores.

Historia [ editar ]

Tanto en Gutin y Toft (2000) como en Soifer (2008) , Vizing menciona que su trabajo fue motivado por un teorema de Shannon (1949) que muestra que los multigrafos pueden colorearse como máximo con (3/2) colores Δ . Aunque el teorema de Vizing ahora es material estándar en muchos libros de texto de teoría de gráficos, Vizing tuvo problemas para publicar el resultado inicialmente, y su artículo aparece en una oscura revista, Diskret. Analiz .