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.
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ę?
graph-theory
graphs
combinatorics
Saurabh
źródło
źródło
Odpowiedzi:
Załóżmy, że w przeciwieństwieP1=⟨v0,…,vk⟩ i P2=⟨u0,…,uk⟩ dwie ścieżki w G o długości k bez wspólną wierzchołków.
AG jest połączony jest ścieżka P′ łączący vi do uj jakiegoś i,j∈[1,k] , takie, że P′ akcji ma wierzchołki P1∪P2 innej niż vi i uj . Powiedzmy P′=⟨vi,x0,…,xb,uj⟩ (uwaga, że nie może być żadnychxi wierzchołki, czylib może być0 - zapis jest nieco niedoborem chociaż).
Bez utraty ogólności możemy założyć, żei,j≥⌈k2⌉ (zawsze możemy odwrócić numerację). Następnie można skonstruować nowe ścieżkiP∗=⟨v0,…,vi,x1,…,xb,uj,…,u0⟩ (przechodząc wzdłużP1 dovi , a następnie przez most utworzony przezP′ zuj , a następnie wzdłużP2 dou0 ).
źródło
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.
źródło