Grafo dirigido, partición de

Question

Deje $D=(V,E)$ ser un número finito de grafo dirigido sin nodos aislados(desde cada nodo hay al menos un borde de entrar y salir de una, yo.e no hay fuentes o sumideros). Para $v \in V$ definir los siguientes conjuntos: $$v^+= \left\{w \in V|(v,w)\in E \right\}, v^-= \left\{w \in V|(w,v)\in E \right\}$$

Para algunos $S \subseteq V, S^+= \bigcup_{v \in S} v^+, S^-= \bigcup_{v \in S} v^-$

Ahora definir dos gráficos relacionados, $G_{cp}=(V,E_{cp}),G_{ce}=(V,E_{ce})$ tal que para dos nodos distintos $v,w \in V$ tenemos $vw \in E_{cp}$ fib $v^+ \cap w^+ \neq \emptyset$ $vw \in E_{ce}$ fib $v^- \cap w^- \neq \emptyset$ Deje $B_1,B_2,...,B_p$ ser los conjuntos de nodos de los componentes conectados de $G_{cp}$ $A_1,A_2,...,A_k$ el conjunto de componentes conectados de $G_{ce}$. Obviamente esos conjuntos son dos particiones de $V$

Demostrar que $(B^+_1,B^+_2,...,B^+_p)$ $(A^-_1,A^-_2,...,A^-_k)$ representan las particiones de $V$. También demostrar que $p=k$ (que es tanto gráficos tienen el mismo número de componentes conectados).

Para demostrar la primera parte he pensado en tomar algunos arbitraria $v \in V$ y de demostrar que $v$$(B^+_1,B^+_2,...,B^+_p)$. A continuación, una prueba por contradicción puede ser necesario para completar la primera parte, pero yo no puedo parecer para realizar la conexión. Yo no sé ni cómo empezar demostrando $p=k$

Nota adicional

La notación de cp y ce viene de "presa común" y "enemigo común"

Actualización

Me las arreglé para esbozar una prueba de la primera parte a lo largo de las líneas que se habla. La prueba por contradicción de las obras. Todavía necesito ayuda en la comprobación de $p=k$

Answer 1

(Estoy cambiando por completo esta respuesta, dado que cada nodo tiene entrantes y salientes bordes).

En primer lugar, nos muestran que la $\{B_1^+, \dotsc, B_p^+\}$ es una partición de a $V$. Si un vértice $v$ en dos de estos conjuntos, decir $v \in B_1^+ \cap B_2^+$, entonces hay una arista de algunos $x \in B_1$$v$, y un borde de algunos $y \in B_2$$v$. A continuación, $x$ $y$ comparten la presa $v$, por lo que hay una ventaja en $G_{cp}$$x$$y$, contradiciendo que se encuentran en diferentes componentes conectados de $G_{cp}$.

Por lo tanto, los conjuntos de $B_i^+$ son disjuntas. Cada conjunto es no vacío, porque todos los vértices tienen bordes salientes. Cada vértice es uno de estos conjuntos, ya que todos los vértices tienen bordes entrantes (y los conjuntos de $B_i$ forma una partición).

Un totalmente similar a prueba muestra que los conjuntos de $A_1^-, \dotsc, A_k^-$ forma una partición de $V$.

Ahora vamos a comprobar que cada conjunto $B_i^+$ es en realidad uno de los conjuntos de $A_j$. Supongamos que $u$ $v$ son dos vértices en $B_1^+$. Vamos a demostrar que están en la misma componente conectado de $G_{ce}$. Si $u$ $v$ son presa al mismo vértice en $B_1$, a continuación, comparten un enemigo común, por lo tanto son adyacentes en $G_{ce}$. De lo contrario, deje $b_1, b_t \in B_1$ que hay un borde de$b_1$$u$, un borde de$b_t$$v$, y hay un camino de $G_{cp}$ $b_1$ $b_t$de longitud mínima, pasando de $b_1, b_2, \dotsc, b_t$. (Esta ruta debe existir desde $B_1$ está conectado a un componente de $G_{cp}$.)

En esta figura, los bordes negros están en $D$, bordes rojos están en $G_{cp}$, azul y los bordes son en $G_{ce}$. Dada la sólida bordes, llegamos a la conclusión de que los guiones de los bordes debe existir.

Debido a $b_1$ $b_2$ son adyacentes en $G_{cp}$, que comparten una presa común, decir $u_1$ (esto no puede ser $u$, ya que de lo contrario nos encontraríamos con una ruta más corta de a $b_i$s.) A continuación, $u$ $u_1$ comparten un enemigo común de $b_1$, por lo tanto son adyacentes en $G_{ce}$. Procedimiento, debido a que $b_i$ $b_{i+1}$ son adyacentes en $G_{cp}$, ellos comparten una presa común $u_i$ (que es distinto de todos los anteriores $u_j$, ya que de lo contrario podríamos encontrar una ruta más corta.) A continuación, $u_{i-1}$ $u_i$ comparten un enemigo común de $b_i$, por lo tanto son adyacentes en $G_{ce}$. Finalmente, habiendo construido un camino de $u$ a un nodo $u_{t-1}$ que es una presa común a$b_{t-1}$$b_t$, podemos ver que $u_{t-1}$ es adyacente a $v$ $G_{ce}$ desde $b_t$ es un enemigo para ambos.

Por lo tanto, $u$ $v$ están en la misma componente conectado de $G_{ce}$. Esto demuestra que cada conjunto $B_i^+$ está contenida en uno de los conjuntos de $A_j$. Desde la colección de $\{B_1^+, \dotsc, B_p^+\}$ $\{A_1, \dotsc, A_k\}$ son ambas particiones, y todos los juegos en uno están contenidas en los juegos de los otros, los conjuntos en efecto, coinciden: por lo tanto no es un bijection de la $B_i$s al $A_j$s y $p = k$.

Un argumento similar muestra que cada una de las $A_j^-$ es uno de los conjuntos de $B_i$. Los mapas $B_i \mapsto B_i^+$ $A_j \mapsto A_j^-$ son mutuamente inversas bijections.