5 votos

¿Es cierto que todos los caminos entre dos vértices comparten un punto común?

Estoy atascado en el siguiente problema de teoría de grafos:

supongamos que para dos vértices $u$ y $v$ en un grafo no dirigido $G$ cualquier par de caminos entre $u$ y $v$ comparten un vértice común (diferente de $u$ y $v$ ), entonces existe un vértice $w$ ( $w\neq u,v$ ), que se encuentra en todos los caminos entre $u$ y $v$ .

No sé si esta afirmación es cierta, pero no se me ocurre ningún contraejemplo.

3voto

Misha Puntos 1723

Este es un caso especial de Teorema de Menger .

Si dos de ellos $u,v$ -comparten un vértice común, entonces el número máximo de vértices disjuntos $u,v$ -sendas que podemos encontrar es en $1$ por lo que, por el teorema de Menger, existe una $u,v$ -corte de tamaño $1$ que es el vértice $w$ .

Esto es suponiendo que no estemos en uno de los varios casos triviales:

  • Si no hay $u,v$ -entonces es vacuamente cierto que dos cualesquiera comparten un vértice. Sea $w$ sea cualquier vértice que no sea $u$ y $v$ y la conclusión sigue siendo válida.
  • Pero si no hay más vértices que $u$ y $v$ Estamos en problemas.
  • Si $u$ y $v$ son adyacentes, y no hay otros $u,v$ -sendas, sigue siendo vacuamente cierto que cualesquiera dos $u,v$ -las trayectorias comparten un vértice. Pero no hay ningún vértice $w$ que no sea $u$ y $v$ que se encuentra en el camino que consiste sólo en la arista $uv$ Por lo tanto, en este caso la conclusión no es válida.

1voto

Rob Lachlan Puntos 7880

Si la propiedad no es verdadera habría tres caminos $\alpha$ , $\beta$ y $\gamma$ cada uno de los cuales se encuentra con los otros dos en al menos un vértice pero sin tener un vértice común, excepto los puntos finales.

Dejemos que $G^\prime$ sea el subgrafo formado únicamente por los vértices y aristas que componen los caminos $\alpha$ , $\beta$ y $\gamma$ .

Este gráfico $G^\prime$ es planar porque no contiene $K_{3,3}$ y no $S_5$ . Así que incrústelo en $\Bbb R^2$ .

La región exterior $F$ tiene la propiedad de que $\Bbb R^2\setminus\overline F$ es un conjunto abierto conectado en $\Bbb R^2$ . De hecho, la única forma de que no se pueda conectar es que exista un punto $w\in\Bbb R^2\setminus F$ desconectándolo, pero este punto sería común a los tres caminos y diferente a los puntos finales.

Por lo tanto, el límite de $w\in\Bbb R^2\setminus F$ es un ciclo que incluye $u$ y $v$ y nunca pasa dos veces por los mismos vértices. Pero cualquier ciclo de este tipo define dos caminos (el camino "superior" y el camino "inferior", si ponemos $G^\prime$ horizontalmente en el plano) que se encuentran sólo en los puntos extremos.

0 votos

No entiendo por qué la primera frase de tu prueba es cierta.

0 votos

@snowAuoue, trabajando por contradicción, asumo que no hay tal $w$ existe. Así, dados dos caminos, asumo un tercero que no se encuentra con los dos primeros en sus vértices comunes.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X