En teoría de grafos , el teorema de Graham-Pollak establece que las aristas de una-El gráfico completo de vértice no se puede dividir en menos de gráficos bipartitos completos . [1] Fue publicado por primera vez por Ronald Graham y Henry O. Pollak en dos artículos en 1971 y 1972, en relación con una aplicación a los circuitos de conmutación telefónica. [2] [3]
Desde entonces, el teorema se ha vuelto bien conocido y se ha estudiado y generalizado repetidamente en la teoría de grafos, en parte debido a su elegante demostración utilizando técnicas de la teoría de grafos algebraica . [4] [5] [6] [7] [8] Más enérgicamente, Aigner y Ziegler (2018) escriben que todas las demostraciones están de alguna manera basadas en álgebra lineal : "no se conoce ninguna prueba combinatoria para este resultado". [1]
Construcción de una partición óptima.
Una partición en exactamente Es fácil obtener gráficos bipartitos completos: simplemente ordene los vértices y, para cada vértice, excepto el último, forme una estrella que lo conecte con todos los vértices posteriores en el orden. [1] También son posibles otras particiones.
Prueba de optimalidad
La demostración del teorema de Graham-Pollak descrita por Aigner y Ziegler (2018) (siguiendo a Tverberg 1982 ) define una variable real para cada vértice , dónde denota el conjunto de todos los vértices del gráfico. Deje que los lados izquierdo y derecho delse denotará el gráfico bipartito y , respectivamente y para cualquier conjunto de vértices definen ser la suma de las variables de los vértices en :
Entonces, en términos de esta notación, el hecho de que los gráficos bipartitos dividan los bordes del gráfico completo se puede expresar como la ecuación
Ahora considere el sistema de ecuaciones lineales que establece y para cada . Cualquier solución a este sistema de ecuaciones obedecería también a las ecuaciones no lineales
Pero una suma de cuadrados de variables reales solo puede ser cero si todas las variables individuales son cero, la solución trivial del sistema de ecuaciones lineales. Si hubiera menos de gráficos bipartitos completos, el sistema de ecuaciones tendría menos de ecuaciones en incógnitas y tendría una solución no trivial, una contradicción. Entonces, el número de gráficos bipartitos completos debe ser al menos. [1] [4]
Problemas relacionados
Etiquetado de distancia
Graham y Pollak estudian un problema de etiquetado de gráficos más general , en el que los vértices de un gráfico deben etiquetarse con cadenas de igual longitud de los caracteres "0", "1" y "✶", de tal manera que la distancia entre dos vértices cualesquiera equivalen al número de posiciones de cadena donde un vértice está etiquetado con un 0 y el otro está etiquetado con un 1. Un etiquetado como este sin caracteres "✶" daría una incrustación isométrica en un hipercubo , algo que solo es posible para gráficos que son cubos parciales , y en uno de sus artículos, Graham y Pollak llaman a un etiquetado que permite que los caracteres "✶" se incrusten en un "cubo aplastado". [3]
Para cada posición de las cadenas de etiquetas, se puede definir un gráfico bipartito completo en el que un lado de la bipartición consiste en los vértices etiquetados con 0 en esa posición y el otro lado consiste en los vértices etiquetados con 1, omitiendo los vértices etiquetados con "✶ ". Para el gráfico completo, cada dos vértices están a una distancia uno del otro, por lo que cada borde debe pertenecer exactamente a uno de estos gráficos completos. De esta manera, un etiquetado de este tipo para el gráfico completo corresponde a una partición de sus bordes en gráficos bipartitos completos, con las longitudes de las etiquetas correspondientes al número de gráficos en la partición. [3]
Conjetura de Alon-Saks-Seymour
Noga Alon , Michael Saks y Paul Seymour formularon una conjetura a principios de la década de 1990 que, de ser cierta, generalizaría significativamente el teorema de Graham-Pollak: conjeturaron que, siempre que una gráfica de número cromático tiene sus bordes divididos en subgrafos bipartitos completos, al menos Se necesitan subgrafos. De manera equivalente, su conjetura establece que las uniones de bordes disjuntos de Los gráficos bipartitos completos siempre se pueden colorear con como máximo colores. La conjetura fue refutada por Huang y Sudakov en 2012, quienes construyeron familias de gráficos formados como uniones de bordes disjuntos de gráficos bipartitos completos que requieren colores. [9]
Tabique biclique
El problema de la partición biclicua toma como entrada un gráfico arbitrario no dirigido y solicita una partición de sus bordes en un número mínimo de gráficos bipartitos completos. Es NP-hard , pero manejable con parámetros fijos . El mejor algoritmo de aproximación conocido para el problema tiene una relación de aproximación de. [10] [11]
Referencias
- ^ a b c d Aigner, Martin ; Ziegler, Günter M. (2018), Proofs from THE BOOK (6.a ed.), Springer, págs. 79–80, doi : 10.1007 / 978-3-662-57265-8 , ISBN 978-3-662-57265-8
- ^ Graham, RL ; Pollak, HO (1971), "Sobre el problema de direccionamiento para la conmutación de bucle", The Bell System Technical Journal , 50 : 2495-2519, doi : 10.1002 / j.1538-7305.1971.tb02618.x , MR 0289210
- ^ a b c Graham, RL ; Pollak, HO (1972), "Sobre la incrustación de gráficos en cubos aplastados", Teoría de gráficos y aplicaciones (Proc. Conf., Western Michigan Univ., Kalamazoo, Michigan, 1972; dedicado a la memoria de JWT Youngs) , Lecture Notes en Matemáticas, 303 , págs. 99-110, MR 0332576
- ^ a b Tverberg, H. (1982), "Sobre la descomposición deen gráficos bipartitos completos ", Journal of Graph Theory , 6 (4): 493–494, doi : 10.1002 / jgt.3190060414 , MR 0679606
- ^ Peck, GW (1984), "Una nueva demostración de un teorema de Graham y Pollak", Matemáticas discretas , 49 (3): 327–328, doi : 10.1016 / 0012-365X (84) 90174-2 , MR 0743808
- ^ Cioabă, Sebastian M .; Tait, Michael (2013), "Variaciones sobre un tema de Graham y Pollak", Matemáticas discretas , 313 (5): 665–676, doi : 10.1016 / j.disc.2012.12.001 , MR 3009433
- ^ Vishwanathan, Sundar (2013), "Una prueba de conteo del teorema de Graham-Pollak", Matemáticas discretas , 313 (6): 765–766, doi : 10.1016 / j.disc.2012.12.017 , MR 3010739
- ^ Líder, Imre ; Tan, Ta Sheng (2018), "Límites mejorados para el problema de Graham-Pollak para hipergráficos", Electronic Journal of Combinatorics , 25 (1): Paper No. 1.4, MR 3761918
- ^ Huang, Hao; Sudakov, Benny (2012), "Un contraejemplo de la conjetura de Alon-Saks-Seymour y problemas relacionados", Combinatorica , 32 (2): 205-219, arXiv : 1002.4687 , doi : 10.1007 / s00493-012-2746-4 , Señor 2927639
- ^ Fleischner, Herbert; Mujuni, Egbert; Paulusma, Daniël; Szeider, Stefan (2009), "Cubriendo gráficos con pocos subgrafos bipartitos completos", Informática teórica , 410 (21-23): 2045-2053, doi : 10.1016 / j.tcs.2008.12.059 , MR 2519293
- ^ Chandran, Sunil; Issac, Davis; Karrenbauer, Andreas (2017), "Sobre la complejidad parametrizada de la cubierta y tabique biclicua", en Guo, Jiong; Hermelin, Danny (eds.), 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) , Leibniz International Proceedings in Informatics (LIPIcs), 63 , Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, págs. 11: 1 –11: 13, doi : 10.4230 / LIPIcs.IPEC.2016.11 , ISBN 978-3-95977-023-1