Udowodnij, że co dwie najdłuższe ścieżki mają co najmniej jeden wspólny wierzchołek

14

Jeśli wykres jest połączony i nie ma ścieżki o długości większej niż k , udowodnij, że co dwie ścieżki w G o długości k mają co najmniej jeden wspólny wierzchołek. GkGk

Myślę, że ten wspólny wierzchołek powinien znajdować się na środku obu ścieżek. Ponieważ jeśli tak nie jest, możemy mieć ścieżkę długości . Czy mam rację?>k

Saurabh
źródło
2
Przeciwprzykład dla wykresu skierowanego, który nie jest silnie połączony: wierzchołki , krawędzie A C , A D , B D , ścieżki A C i B D nie mają wspólnego wierzchołka. A,B,C,DACADBDACBD
sdcvvc
@ sdcvvc, możesz podać to jako odpowiedź.
2
@sdcvvc Myślę, że pytanie ogranicza się do nieukierunkowanych grafów.
Raphael
Czy możesz potwierdzić (lub osłabić), że jest wykresem niekierowanym i rozważasz tylko proste (= bez cyklu) ścieżki? G
Gilles „SO- przestań być zły”
@Gilles Tak, wykres nie jest przekierowany, a ścieżka jest ścieżką zawierającą wyraźne krawędzie i wierzchołki.
Saurabh,

Odpowiedzi:

21

Załóżmy, że w przeciwieństwie P1=v0,,vk i P2=u0,,uk dwie ścieżki w G o długości k bez wspólną wierzchołków.

A G jest połączony jest ścieżka P łączący vi do uj jakiegoś i,j[1,k] , takie, że P akcji ma wierzchołki P1P2 innej niż vi i uj . Powiedzmy P=vi,x0,,xb,uj(uwaga, że nie może być żadnychxi wierzchołki, czylibmoże być0- zapis jest nieco niedoborem chociaż).

Bez utraty ogólności możemy założyć, że i,jk2(zawsze możemy odwrócić numerację). Następnie można skonstruować nowe ścieżkiP=v0,,vi,x1,,xb,uj,,u0(przechodząc wzdłużP1dovi, a następnie przez most utworzony przezPzuj, a następnie wzdłużP2dou0).

Pk+1Gk

k

Luke Mathieson
źródło
I think you need jk2, otherwise the new path is not necessarily longer. Note that b=0 is possible.
Raphael
1
@Raphael Yes, I didn't explicitly state it (and used slightly misleading notation), but b can quite happily be 0, the bridge always adds at least one edge though, even if the only vertices in P are vi and uj. On the first point, note that I've constructed the path from v0viuju0, so jk2 is right. If it went to uk then jk2 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
źródło