Demostración del teorema del separador plano

Question

No puedo entender la prueba del Teorema del Separador Planar

Todo grafo planar de n vértices tiene un separador de 2/3 que contiene como máximo $\sqrt{8n}$ vértices.

Demostración del teorema 10 Separadores de gráficos

Repasemos la prueba.

Dejemos que $G$ sea un grafo plano incrustado con $n \geq 3$ vértices, y que $k = \sqrt{2n}$ Sin pérdida de generalidad, podemos suponer que $G$ no tiene bucles ni aristas paralelas, y que cada cara es un triángulo delimitado por tres aristas distintas. Para cualquier ciclo simple $C$ en G, sea $In(C)$ y $Out(C)$ denotan los vértices dentro y fuera de $C$ r, respectivamente. Ningún vértice de $In(C)$ es adyacente a cualquier vértice de $Out(C)$ . Dejemos que $C$ sea un ciclo simple que cumpla tres condiciones:

1. $C$ tiene como máximo $2k$ vértices.

2. $|Out(C)| < 2n/3$ .

3. Sujeto a las condiciones 1 y 2, la diferencia |In(C)| y |Out(C)| es lo más pequeña posible.

Sea D el subgrafo de G en el interior cerrado de C. Para dos vértices cualesquiera $u$ y $v$ en $C$ , dejemos que $c(u, v)$ denotan su distancia en $C$ y que $d(u, v)$ denotan su distancia en $d$ .

Reclamación 1 . $d(u, v) = c(u, v)$ para todos los vértices $u$ y $v$ en $C$ .

Es evidente que tenemos $d(u, v) \leq c(u, v)$ para todos $u$ y $v$ porque $C$ es un subgrafo de $D$ . Supongamos que hay vértices distintos $u$ y $v$ tal que $d(u, v) < c(u, v)$ elija un par de este tipo para que $d(u, v)$ se minimiza. Sea un camino más corto desde $u$ a $v$ en D. Si contiene cualquier otro vértice $w$ en C, entonces $d(u, w) + d(w, v) = d(u, v) < c(u, v) \leq c(u, w) + c(w, v)$ Así que, o bien $d(u, w) < c(u, w)$ o $d(w, v) < c(w, v)$ cualquiera de las dos posibilidades contradice nuestra elección de $u$ y $v$ .

Cómo es posible, echa un vistazo a la imagen. Es evidente que el camino en $D$ es más corto que el camino en $C$ . La parte con vértice adicional $w$ no se entendió en absoluto, al final tenemos la contradicción de la elección de $u$ y $v$ .

Reclamación 2 . $C$ tiene exactamente $2k$ vértices.

No puedo conseguirlo también, porque la prueba se basa en la afirmación 1.

Por favor, ¿puede arrojar luz sobre la prueba?

Gracias.

Anexo :

1. Tenemos 3 condiciones que $C$ debe satisfacer
2. Para derivar una contradicción, tenemos la suposición $|In(C)| \geq 2n/3$
3. Elegimos $w$ y $v$ tal que $d(u,v)$ se minimiza y se demuestra que $d(u, w) < c(u, w)$ o $d(w, v) < c(w, v)$ Cualquiera de las dos posibilidades contradice nuestra elección de $u$ y $v$ . Pero esto está completamente bien con la minimización $d(u,w)$ ¿Cuál es la contradicción?
4. Resulta que podemos encontrar una mejor separación $C^{+}$ que satisface (1.1) y (1.2) (con la suposición de que 2 es verdadera, que ya es errónea), pero no satisface (1.3), y la conclusión de que la afirmación es verdadera. Pero, ¿cómo es que la contradicción de nuestra elección de $u$ y $v$ ?

Lo siento, no es una complicación en términos de matemáticas, pero está muy mezclado en términos de lógica.

Answer 1

No contradice su elección de $u,v$ . La elección de $u,v$ es asegurarse de que el camino mínimo que conecta $u,v$ no se cruza con $C$ para que el camino conectado $u,v$ divide $D$ en dos (y no más) regiones.

La contradicción se deriva de hacer que la diferencia entre el número de puntos en In(C) y Out(C) sea lo más pequeña posible en el inicial descripción de la curva $C$ .

Editar : Ah, te preocupa la parte en la que el autor asume por contradicción...

La cuestión es ésta. Tienes condiciones

1. $C$ tiene como máximo $2k$ vértices
2. $Out(C)$ tiene como máximo $2n/3 - 1$ vértices
3. Condición de optimización.

Una vez que haya elegido tal $C$ , si $In(C)$ también tiene como máximo $2n/3 -1$ vértices, entonces $C$ es un separador plano de 2/3 con un máximo de 2k vértices, como exige el teorema. Por tanto, basta con demostrar que es imposible que $In(C)$ para tener más de $2n/3$ vértices. Para ello, los autores demuestran que si $|In(C)| \geq 2n/3$ obtendrá una contradicción.

Para construir la contradicción, el autor demuestra que si $|In(C)| \geq 2n/3$ puede construir un $C'$ tal que satisfaga 1 y 2, pero optimice mejor 3 (lo que contradiría nuestra elección original de $C$ siendo el optimizador). La construcción de $C'$ va básicamente por el corte $In(C)$ a la mitad utilizando un minimizador de longitud entre dos puntos de $C$ . (Se trata de utilizar el hecho de que una de las dos mitades tendrá Interior al menos $n/3$ .) Si el minimizador de trayectorias corta $C$ en más de dos piezas, no se puede garantizar que ninguna pieza tenga interior más de $2n/9$ . Por lo tanto, hay que asegurarse de que el minimizador de trayectorias sólo corte $C$ por la mitad. Y por lo tanto el minimizador de la trayectoria se requiere para no intersecar $C$ . La elección de $u,v$ y la subsecuente mini prueba por contradicción garantiza que.