Lenceria, flores y bordes biconnected perfectos: necesita ayuda para entender de una reclamación

Question

Estoy leyendo un temprano de papel por Deming en Koenig gráficos 1, y estoy atascado tratando de entender una reclamación en el papel.

Preliminares

Deje $G$ a (finito, grafo, simple) gráfico. Fijar un máximo coincidente $M$$G$. Los bordes en $M$ son pesados; los que no están en $M$ se dice ser de luz. Un vértice $v$ $G$ dijo estar expuesta relativa a $M$ si $v$ no es el punto final de cualquier pesados borde de $G$. Una alternancia de camino desde el vértice $u$ hasta el vértice $v$ es un camino de $p(u,v)$, cuyos bordes son alternativamente ligeros y pesados; esta ruta puede comenzar o terminar con un poquito de borde o una pesada borde.

Un extraño ciclo de $v_{0},v_{1},\dotsc,v_{2k},v_{0}\;;\;k\geq1$ se llama una flor si los bordes $v_{1}v_{2},v_{3}v_{4},\dotsc,v_{2k-1}v_{2k}$ son pesados. El vértice $v_{0}$ en una flor que se llama la flor de la punta.

Supongamos que hay una ruta alterna $v_{1},v_{2},\dotsc,v_{2k}\;;\;k\geq1$ $G$ donde los bordes $v_{1}v_{2}$ $v_{2k-1}v_{2k}$ son pesados y los vértices $v_{1}$ $v_{2k}$ son flor de consejos. "Una configuración de este tipo de" se llama una flor par de $G$.

(Puedo agregar las comillas porque no es claro para mí lo que el autor quiere decir en una configuración de este tipo: ¿que significa sólo el camino de $v_{1},v_{2},\dotsc,v_{2k}$, o si también se incluyen las flores cuyos consejos se $v_{1}$$v_{2k}$?)

La reclamación

Deje $G$ un gráfico con un perfecto maridaje $M$, e $x_{1}x_{2}$ $y_{1}y_{2}$ ser pesados en los bordes, que pertenecen a una flor de par $B$ con respecto a la concordancia de $M$. A continuación, para cada una de las $i,j=1,2$, hay una ruta alterna $p(x_{i},y_{j})$ comenzando y terminando con la luz de los bordes y la contenida en $B$.

Mi pregunta

Considere el siguiente gráfico. Éste satisface las condiciones de la demanda: Se tiene un perfecto maridaje (indicado por el "pesado" de los bordes) y contiene/es una flor de par (dependiendo de cómo se interprete la definición de una flor de par por encima) con respecto a esta coincidencia. Ahora $x_{1}x_{2}$ $y_{1}y_{2}$ son pesados los bordes, que pertenecen a la flor de par (de interpretación), pero no hay ninguna ruta alterna $p(x_{1},y_{2})$ que comienza y termina con la luz de los bordes. ¿Por qué?

Deming citas Edmonds' Caminos, árboles y flores de papel para la terminología, hasta e incluyendo la flor de punta. Sólo para estar seguro, he comprobado este último documento: Edmonds utiliza el "camino", que significa "camino simple", por lo que no puede ser que Deming significa "la alternancia de a pie" aquí cuando dice: "la alternancia de ruta".

Lo que me estoy perdiendo aquí?

Información adicional

(Puede ser de ayuda en la resolución de mi pregunta.)

Deming pasa a definir un par de pesados bordes $x_{1}x_{2}$ $y_{1}y_{2}$ a ser biconnected si hay alternancia de caminos $p(x_{i},y_{j})$ $i=1,2\;;\;j=1,2$ que comienzan y terminan con la luz de los bordes. A continuación, afirma que cualquier par de biconnected pesado bordes está contenida en una flor de par de la gráfica.

Imagen mencionado en el comentario a SE318 la respuesta

1 la Independencia de los Números de los Gráficos -- Una Extensión de la Koenig-Egervary Teorema. Robert W. Deming, Matemáticas Discretas, 27 (1979) 23-33. PDF

Answer 1

En lugar de "flor de par" Sterboul definido un "$M$-posy". He aquí el pasaje de Schrijver:

Para caracterizar los gráficos de $G$$ν(G) = τ (G)$, Sterboul definido, para cualquier gráfico de $G = (V,E)$ y cualquier coincidencia de $M$$G$, $M$- posy a ser un de longitud $M$-alternando cerrado a pie $(v_0, v_1, . . . , v_t)$, $v_{i−1}v_i ∈ M$ si $i$ es incluso, que no existe $i < j$ $i$ impar y $j$ a, $v_1, . . . , v_j$ todos distintos, $v_{j+1}, . . . , v_t$ todos distintos, y

(30.54) $v_i = v_t,$ $v_{i+1} = v_{t−1}, . . . , v_j = v_{t+i−j}$ .

Lema 30.13 α. Si existe una longitud de $M$-alternando cerrado a pie $C = (v_0, v_1, . . . , v_t)$ $v_i = v_j$ $i, j$ de distinta paridad, entonces existe un $M$-posy.

Ambas cosas se han elaborado son $M$-posys. Como se puede ver es bastante peludo para escribir una definición formal plenamente la captura de la imagen.

---

EDIT: Mientras que yo todavía no he averiguado qué es exactamente Deming "biconnected" bordes, su resultado final en esa sección, su teorema 2, arroja algo de luz sobre lo que él está tratando de decir:

Teorema 2. Cualquier grafo G es K-E iff para cualquier máxima coincidente M, la extensión de G' no contiene par de biconnected pesado bordes.

Su definición de la extensión de gráfico es sencillo (y se ilustra con ejemplos así hay duda de lo que significa):

Para la construcción de $G'$, vamos a $X$ el conjunto de los expuestos en los vértices de $G$ en relación a un máximo la coincidencia de $M$. Para cada una de las $x \in X$, añadir un nuevo vértice $x'$ y nuevas aristas $xx'$ y $\{x'y : y \text{ is adjacent to } x\}$. $M' = M \cup \{xx' : x \in X\}$ es un perfecto maridaje para $G'$.

(Expuesto vértice significa que no se incluyen en el partido.)

Ayuda a comparar Deming teorema 2 con su equivalente teorema de 30.13 en Schrijver (que estoy abreviar un poco):

G tiene el Koenig propiedad iff para cada uno un máximo de tamaño de coincidencia M no hay M-flor y no M-posy

donde M-flor se define como la cara de la versión de la M-posy:

Si usted toma la M-flor y aplicar Deming extensión de la construcción, usted consigue un M-posy; sólo $v_0$ se duplica a un $v_0'$. Así también se puede expresar el teorema como: G tiene el Koenig propiedad iff para cada uno un máximo de tamaño de coincidencia de G' (denotado por M') no es M'-posy. En otras palabras, la forboding/restricción sobre la M-flores y M-posys en el gráfico original se puede expresar sólo una restricción sobre la M-posys en Deming extenstion gráfico. Así que por su "ningún par de biconnected pesados de las aristas en G' lo más probable es significa que ya no hay M'-posy en G'. Todavía no me queda claro qué es exactamente Deming "biconnected pesado bordes", etc.

---

EDIT2: en Realidad, ahora entiendo lo de Deming "biconnected pesado bordes": debe ser de cuatro caminos comenzando y terminando con la luz de los bordes: $x_1y_1$, $x_1y_2$, $x_2y_1$ y $x_2y_2$ deben ser trazados con esta propiedad (pero los cuatro caminos no necesita ser completamente distintos el uno del otro). Esta definición/interpretación es en realidad equivalente a los dos pesados bordes pertenecientes a la opuesta de la flor extremos de un M-possy. Con esta interpretación de la "biconnected pesado bordes" no se puede estar en la misma flor (tendrías luz dos de los bordes en la fila siguiente de la flor del ciclo; y si usted va alrededor de la otra flor que no es un simple camino más), ni pueden ser en el "puente" entre las flores (que no tendrá cuatro simples rutas de entonces). Así, en los dos gráficos/elecciones que has dibujado, el destacado $x_1x_2$ $y_1y_2$ realidad no cumplir Deming def de "biconnected pesado bordes".

Y volviendo a "la demanda", ya que estaba destinado a ser la mitad de esta equivalencia entre "biconnected pesado bordes" y M-posy, que debería haber sido declarado [por Deming] como: Vamos a $G$ un gráfico con un perfecto maridaje $M$, e $x_{1}x_{2}$ $y_{1}y_{2}$ ser pesados en los bordes de cada una perteneciente a un contrario en flor de una flor de par $B$ con respecto a la concordancia de $M$. A continuación, para cada una de las $i,j=1,2$, hay una ruta alterna $p(x_{i},y_{j})$ comenzando y terminando con la luz de los bordes y la contenida en $B$.

---

Tenga en cuenta sin embargo que la equivalencia entre la M-posy y biconnected pesado, de bordes mal, porque no en la otra dirección; después de "la demanda" [que al menos podría ser parcheado] el documento dice que "Un sencillo argumento muestra que un par de biconnected pesado bordes $x_1x_2$$y_1y_2$, están contenidos en una flor de par B." Kundor muestra de que se puede tener biconnected pesado bordes, pero uno (o ambos) de la pareja no necesita pertenecer a un M-posy; esto es debido a que uno (o ambos) de la biconnected pesado bordes pueden pertenecer a una longitud de ciclo de la correspondencia y este ciclo se puede compartir una pesada perimetral con una longitud impar ciclo (es decir, real flor que pertenece a un M-posy) que a su vez pueden compartir otro pesado borde con el otro, incluso de longitud de ciclo. Así que usted consigue algunos "extras" pares de biconnected pesado bordes no beloning a la actual M-posy pero cuya alternancia, cuatro go-entre caminos "pasar a través" del M-posy. (Sin la M-posy facilitar este "crossover" usted no conseguir los 4 caminos). Aquí está un poco crudo imagen de Kundor la idea más general de la configuración:

Deming Teorema 2 todavía es correcta, aunque, sino porque la existencia de un par de biconnected pesado bordes implica la existencia de al menos uno M-posy (de la correspondencia), aunque no todos los biconnected pesado bordes de la necesidad de pertenecer a un M-posy. La prueba de que la existencia de un par de biconnected pesado bordes implica la existencia de un M-posy no es tan trivial/obvio.

Answer 2

Puedo equivocarme, pero una forma de dar sentido a esto... Creo que la pareja de flor literalmente sólo se refiere a las dos flores en cuestión (los en que $v_1$ y $v_{2k}$ son consejos de flor) y no el camino en medio, por lo que su % de bordes $x_1x_2$y $y_1y_2$ no están en el par de flor porque están en el camino, no las flores.

Answer 3

Traté de usar la reclamación sobre biconnected pares de fuertes bordes para aclarar lo que debe ser incluido en la "flor de par." Pero parece problemático!

En esta imagen, $x_1 x_2$ $y_1 y_2$ son una biconnected par de pesados bordes (derecho?). Sin embargo, está contenida en ningún flor de par. La única flores son:

• $a,x_1,x_2,a$
• $b_,x_1,x_2,b$
• $x_1, a, b, x_1$, y
• $x_2, a, b, x_2$.

Cualquier alternando camino, empezando y terminando con la pesada de los bordes, de entre cualquiera de estos blossom consejos, no implican $y_1 y_2$. De ahí que el borde no está involucrado en ningún flor de par en este gráfico, para cualquiera de las posibles definiciones.

Así pues, creo que las reivindicaciones como se dijo, son erróneas. Sin embargo, lo que el autor quiere usar es este:

Un gráfico que contiene un biconnected par de pesados los bordes si y sólo si también contiene una flor de par.

Creo que esto es cierto, a pesar de las declaraciones erróneas de intentar demostrarlo.

En particular, en el reclamo en cuestión, lo que el autor realmente se requiere es:

Deje $G$ un gráfico con un perfecto maridaje $M$, e $B$ ser una flor de par con respecto a la concordancia de $M$. Entonces existen un par de pesados bordes $x_1x_2$ $y_1y_2$ pertenecientes a $B$ tal que para cada una de las $i,j=1,2$, hay una ruta alterna $p(x_i,y_j)$ inicio y terminando con la luz de los bordes y la contenida en $B$.