El teorema de Fulkerson-Chen-Anstee es un resultado de la teoría de grafos , una rama de la combinatoria . Proporciona uno de los dos enfoques conocidos para resolver el problema de realización de dígrafos , es decir, proporciona una condición necesaria y suficiente para pares de números enteros no negativos. ser los pares de grado - grado de un grafo dirigido simple ; una secuencia que obedece a estas condiciones se denomina "digráfica". DR Fulkerson [1] (1960) obtuvo una caracterización análoga al teorema clásico de Erdős-Gallai para gráficos, pero en contraste con esta solución con exponencialmente muchas desigualdades. En 1966 Chen [2] mejoró este resultado al exigir la restricción adicional de que los pares de enteros deben ordenarse en un orden lexicográfico no creciente que conduce a n desigualdades. Anstee [3] (1982) observó en un contexto diferente que es suficiente tener. Berger [4] reinventó este resultado y da una prueba directa.
Declaración
Una secuencia de pares enteros no negativos con es digrafico si y solo si y la siguiente desigualdad es válida para k tal que:
Versiones más fuertes
Berger demostró [4] que basta con considerar lala desigualdad tal que con y para .
Otras notaciones
El teorema también se puede enunciar en términos de matrices cero-uno . La conexión se puede ver si uno se da cuenta de que cada gráfico dirigido tiene una matriz de adyacencia donde las sumas de las columnas y las sumas de las filas corresponden a y . Tenga en cuenta que la diagonal de la matriz solo contiene ceros. Existe una conexión con la relación de mayorización . Definimos una secuencia con . Secuenciatambién se puede determinar mediante un diagrama de Ferrers corregido . Considere las secuencias, y como -dimensionales vectores , y . Desdeaplicando el principio de doble conteo , el teorema anterior establece que un par de sucesiones enteras no negativas sin aumentar es digrafico si y solo si vector mayoriza .
Generalización
Una secuencia de pares enteros no negativos con es digrafico si y solo si y existe una secuencia tal que la pareja es digrafico y mayoriza . [5]
Caracterizaciones para problemas similares
Teoremas similares describen las secuencias de grados de gráficos simples, gráficos dirigidos simples con bucles y gráficos bipartitos simples. El primer problema se caracteriza por el teorema de Erdős-Gallai . Los dos últimos casos, que son equivalentes, véase Berger, [4] se caracterizan por el teorema de Gale-Ryser .
Ver también
Referencias
- ^ DR Fulkerson: matrices cero-uno con rastro cero. En: Pacific J. Math. Núm. 12, 1960, págs. 831–836
- ↑ Wai-Kai Chen: Sobre la realización de un ( p , s ) -digraph con grados prescritos. En: Revista del Instituto Franklin No. 6, 1966, págs. 406–422
- ^ Richard Anstee: Propiedades de una clase de matrices (0,1) que cubren una matriz dada. En: Can. J. Math. , 1982, págs. 438–453
- ^ a b c Annabell Berger: Una nota sobre la caracterización de secuencias digráficas en: Matemáticas discretas , 2014, págs. 38–41
- ^ Annabell Berger: La conexión entre el número de realizaciones para secuencias de grado y mayorización En: arXiv1212.5443 , 2012