Probar que cada dos caminos más largos tienen al menos un vértice en común

14

Si un gráfico está conectado y no tiene una ruta con una longitud mayor que , demuestre que cada dos rutas en de longitud tienen al menos un vértice en común. GkGk

Creo que ese vértice común debería estar en el medio de ambos caminos. Porque si este no es el caso, entonces podemos tener una ruta de longitud . Estoy en lo cierto?>k

Saurabh
fuente
2
Contraejemplo para un gráfico dirigido que no está fuertemente conectado: vértices , aristas A C , A D , B D , las rutas A C y B D no tienen vértices comunes. A,B,C,DACADBDACBD
sdcvvc el
@sdcvvc, puede proporcionarlo como respuesta.
2
@sdcvvc Supongo que la pregunta está restringida a gráficos no dirigidos.
Raphael
¿Puedes confirmar (o estar enfermo) que es un gráfico no dirigido y que solo estás considerando rutas simples (= sin ciclo)? G
Gilles 'SO- deja de ser malvado'
@Gilles Sí, el gráfico no está dirigido y la ruta es un recorrido que contiene bordes y vértices distintos.
Saurabh

Respuestas:

21

Supongamos por contradicción que P1=v0,,vk y P2=u0,,uk dos caminos en G de longitud k sin vértices compartidos.

Cuando G está conectado, hay una ruta P conecta vi a uj para algunos i,j[1,k] modo que P no comparte vértices con P1P2 no sean vi y uj . Digamos P=vi,x0,,xb,uj(nota que puede no haberxi vértices, es decir,bpuede ser0- la notación es un poco deficiente aunque).

Sin pérdida de generalidad, podemos suponer que i,jk2(siempre podemos revertir la numeración). Entonces podemos construir un nuevo caminoP=v0,,vi,x1,,xb,uj,,u0(por ir a lo largo deP1avi, a continuación, a través del puente formado porPauj, luego a lo largo deP2au0).

Obviously P has length at least k+1, but this contradicts the assumption that G has no paths of length greater than k.

So then any two paths of length k must intersect at at least one vertex and your observation that it must be in the middle (if there's only one) follows as you reasoned.

Luke Mathieson
fuente
I think you need jk2, otherwise the new path is not necessarily longer. Note that b=0 is possible.
Raphael
1
b0Pviujv0viuju0jk2ukjk2 would be the right condition.
Luke Mathieson
1

You are right that the common vertex must occur in the middle of both paths.

However that intuition will not solve the actual problem you're trying to solve.

Instead try to demonstrate that, given any point in the path, the path segment from (and including) that point to one of the ends of the original path must have strictly greater than half as many nodes as the full path.

Once you have shown that, you will be able to both solve the problem that you were asked and verify your conjecture.

btilly
fuente