En teoría de grafos , el teorema de Gallai – Hasse – Roy – Vitaver es una forma de dualidad entre los colores de los vértices de un grafo no dirigido dado y las orientaciones de sus bordes. Establece que el número mínimo de colores necesarios para colorear correctamente cualquier gráfico G es igual a uno más la longitud de una ruta más larga en una orientación de G elegida para minimizar la longitud de esta ruta. [1] Las orientaciones para las que el camino más largo tiene una longitud mínima siempre incluyen al menos una orientación acíclica . [2]
Una implicación del teorema es que cada orientación de una gráfica con número cromático k contiene una trayectoria dirigida simple con k vértices; [3] esta ruta se puede restringir para que comience en cualquier vértice que pueda alcanzar todos los demás vértices del grafo orientado. [4] [5]
Ejemplos de
Un gráfico bipartito puede orientarse de un lado al otro de la bipartición; el camino más largo en esta orientación tiene solo dos vértices. Por el contrario, si un gráfico está orientado sin rutas de tres vértices, entonces cada vértice debe ser una fuente (sin bordes entrantes) o un sumidero (sin bordes salientes) y la partición de los vértices en fuentes y sumideros muestra que es bipartito.
En cualquier orientación de un gráfico de ciclo de longitud impar, no es posible que las aristas alternen en orientación alrededor del ciclo, por lo que dos aristas consecutivas deben formar una ruta con tres vértices. En consecuencia, el número cromático de un ciclo impar es tres.
Prueba
Para demostrar que el número cromático es mayor o igual que el número mínimo de vértices en un camino más largo, suponga que una gráfica dada tiene un color con k colores, para algún número k . Luego, se puede orientar acíclicamente numerando colores y dirigiendo cada borde desde su punto final con el número más bajo hasta el punto con el número más alto. Con esta orientación, los números aumentan estrictamente a lo largo de cada ruta dirigida, por lo que cada ruta puede incluir como máximo un vértice de cada color, para un total de como máximo k vértices por ruta.
Para probar que el número cromático es menor o igual que el número mínimo de vértices en un camino más largo, suponga que un gráfico dado tiene una orientación con como máximo k vértices por camino dirigido simple, para algún número k . A continuación, los vértices de la gráfica pueden ser coloreadas con k colores por elegir un máximo acíclico subgrafo de la orientación y, a continuación, la coloración de cada vértice por la longitud de la trayectoria más larga en el subgrafo elegido que termina en ese vértice. Cada borde dentro del subgrafo está orientado desde un vértice con un número más bajo hasta un vértice con un número más alto y, por lo tanto, está correctamente coloreado. Para cada borde que no esté en el subgrafo, debe existir un camino dirigido dentro del subgrafo que conecte los mismos dos vértices en la dirección opuesta, de lo contrario el borde podría haber sido incluido en el subgrafo elegido; por lo tanto, el borde está orientado de un número más alto a un número más bajo y nuevamente está coloreado apropiadamente. [1]
La demostración de este teorema fue utilizada como un caso de prueba para una formalización de la inducción matemática por Yuri Matiyasevich . [6]
Interpretación teórica de categorías
El teorema también tiene una interpretación natural en la categoría de gráficos dirigidos y homomorfismos de gráficos . Un homomorfismo es un mapa de los vértices de un gráfico a los vértices de otro que siempre asigna bordes a bordes. Por tanto, una coloración k de un gráfico G no dirigido puede describirse mediante un homomorfismo de G al gráfico completo K k . Si el gráfico completo se da una orientación, se convierte en un torneo , y la orientación se puede levantar de nuevo a través de la homomorfismo para dar una orientación de G . En particular, la coloración dada por la longitud del camino entrante más largo corresponde de esta manera a un homomorfismo a un torneo transitivo (un grafo completo orientado acíclicamente), y cada coloración puede describirse por un homomorfismo a un torneo transitivo de esta manera.
Teniendo en cuenta homomorfismos en la otra dirección, a G en lugar de a partir de G , un grafo dirigido G es acíclico y tiene en la mayoría de k vértices en su camino más largo si y sólo si no hay homomorfismo del gráfico de ruta P k + 1 a G .
Por lo tanto, el teorema de Gallai-Hasse-Roy-Vitaver se puede enunciar de manera equivalente de la siguiente manera: [2]
Por cada grafo dirigido G , existe un homomorfismo de G a la k -vertex transitivo torneo si y sólo si no hay homomorfismo de la ( k camino + 1) -vertex a G .
En el caso de que G sea acíclico, esto también puede verse como una forma del teorema de Mirsky de que la cadena más larga en un conjunto parcialmente ordenado es igual al número mínimo de antichains en los que se puede dividir el conjunto. [7] Esta afirmación se puede generalizar a partir de rutas a otros gráficos dirigidos: para cada polytree P hay un gráfico dirigido dual D tal que, para cada gráfico dirigido G , hay un homomorfismo de G a D si y solo si no hay un homomorfismo de P a G . [8]
Historia
El teorema de Gallai-Hasse-Roy-Vitaver ha sido redescubierto repetidamente. [2] Lleva el nombre de publicaciones independientes de Tibor Gallai , [9] Maria Hasse , [10] B. Roy, [11] y LM Vitaver. [12] Roy atribuye el enunciado del teorema a una conjetura de un libro de texto de teoría de grafos de 1958 de Claude Berge . [11]
Referencias
- ^ a b Hsu, Lih-Hsing; Lin, Cheng-Kuan (2009), "Teorema 8.5", Teoría de grafos y redes de interconexión , Boca Raton, Florida: CRC Press, págs. 129–130, ISBN 978-1-4200-4481-2, MR 2454502.
- ^ a b c Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2012), "Teorema 3.13", Esparcimiento: Gráficos, Estructuras y Algoritmos , Algoritmos y Combinatoria, 28 , Heidelberg: Springer, p. 42, doi : 10.1007 / 978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058.
- ^ Chartrand, Gary ; Zhang, Ping (2009), "Teorema 7.17 (Teorema de Gallai-Roy-Vitaver)", Teoría de gráficos cromáticos , Matemáticas discretas y sus aplicaciones, Boca Raton, Florida: CRC Press, ISBN 978-1-58488-800-0, MR 2450569.
- ^ Li, Hao (2001), "Una generalización del teorema de Gallai-Roy", Gráficos y combinatoria , 17 (4): 681–685, doi : 10.1007 / PL00007256 , MR 1876576.
- ^ Chang, Gerard J .; Tong, Li-Da; Yan, Jing-Ho; Yeh, Hong-Gwa (2002), "Una nota sobre el teorema de Gallai-Roy-Vitaver", Matemáticas discretas , 256 (1-2): 441-444, doi : 10.1016 / S0012-365X (02) 00386-2 , Señor 1927565.
- ^ Матиясевич, Ю. В. (1974), "Одна схема доказательств в дискретной математике" [A cierto esquema para pruebas en discreta matemáticas], Исследования по конструктивной математике и математической логике [ Estudios en matemáticas constructivas y la lógica matemática. Parte VI. Dedicado a AA Markov con motivo de su 70º cumpleaños ], Zapiski Naučnyh Seminarov Leningradskogo Otdelenija Matematičeskogo Instituta im. VA Steklova Akademii Nauk SSSR (LOMI) (en ruso), 40 , págs. 94–100, MR 0363823.
- ^ Mirsky, Leon (1971), "Un teorema de descomposición dual de Dilworth", American Mathematical Monthly , 78 (8): 876–877, doi : 10.2307 / 2316481 , JSTOR 2316481.
- ^ Nešetřil, Jaroslav ; Tardif, Claude (2008), "Un enfoque dualista para delimitar el número cromático de un gráfico", European Journal of Combinatorics , 29 (1): 254-260, doi : 10.1016 / j.ejc.2003.09.024 , MR 2368632.
- ^ Gallai, Tibor (1968), "Sobre gráficos y circuitos dirigidos", Teoría de los gráficos (Actas del coloquio celebrado en Tihany 1966) , Budapest: Akadémiai Kiadó, págs. 115-118.
- ^ Hasse, Maria (1965), "Zur algebraischen Begründung der Graphentheorie. I", Mathematische Nachrichten (en alemán), 28 (5-6): 275-290, doi : 10.1002 / mana.19650280503 , MR 0179105.
- ^ a b Roy, B. (1967), "Nombre chromatique et plus longs chemins d'un graphe" (PDF) , Rev. Française Informat. Recherche Opérationnelle (en francés), 1 (5): 129-132, doi : 10.1051 / m2an / 1967010501291 , MR 0225683.
- ^ Витавер, Л. М. (1962), "Нахождение минимальных раскрасок вершин графа с помощью булевых степеней матрицы смежностей [Determinación de la coloración mínima de vértices de un gráfico por medio de poderes booleanas de la incidencia matriz]", Doklady Akademii Nauk SSSR (en ruso), 147 : 758 –759, MR 0145509.