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.
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?
graph-theory
graphs
combinatorics
Saurabh
fuente
fuente
Respuestas:
Supongamos por contradicción queP1=⟨v0,…,vk⟩ y P2=⟨u0,…,uk⟩ dos caminos en G de longitud k sin vértices compartidos.
CuandoG está conectado, hay una ruta P′ conecta vi a uj para algunos i,j∈[1,k] modo que P′ no comparte vértices con P1∪P2 no sean vi y uj . Digamos P′=⟨vi,x0,…,xb,uj⟩ (nota que puede no haberxi vértices, es decir,b puede ser0 - la notación es un poco deficiente aunque).
Sin pérdida de generalidad, podemos suponer quei,j≥⌈k2⌉ (siempre podemos revertir la numeración). Entonces podemos construir un nuevo caminoP∗=⟨v0,…,vi,x1,…,xb,uj,…,u0⟩ (por ir a lo largo deP1 avi , a continuación, a través del puente formado porP′ auj , luego a lo largo deP2 au0 ).
ObviouslyP∗ 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 lengthk 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.
fuente
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.
fuente