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

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

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$

graph-theory graphs combinatorics

— Saurabh
źródło

Przeciwprzykład dla wykresu skierowanego, który nie jest silnie połączony: wierzchołki

, krawędzie

, ścieżki

nie mają wspólnego wierzchołka.

A, B, C, D

$A,B,C,D$

A \to C

$A \to C$

A \to D

$A \to D$

B \to D

$B \to D$

A \to C

$A \to C$

B \to D

$B \to D$

— sdcvvc

@ sdcvvc, możesz podać to jako odpowiedź.

@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

$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:

Załóżmy, że w przeciwieństwie $P_{1} = \langle v_{0},\ldots,v_{k}\rangle$ i $P_{2} = \langle u_{0},\ldots,u_{k}\rangle$ 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 $v_{i}$ do $u_{j}$ jakiegoś $i,j \in [1,k]$ , takie, że $P'$ akcji ma wierzchołki $P_{1} \cup P_{2}$ innej niż $v_{i}$ i $u_{j}$ . Powiedzmy $P' = \langle v_{i},x_{0},\ldots,x_{b},u_{j}\rangle$ (uwaga, że nie może być żadnych $x_{i}$ wierzchołki, czyli $b$ może być $0$ - zapis jest nieco niedoborem chociaż).

Bez utraty ogólności możemy założyć, że $i,j \geq \lceil\frac{k}{2}\rceil$ (zawsze możemy odwrócić numerację). Następnie można skonstruować nowe ścieżki $P^{*} = \langle v_{0},\ldots,v_{i},x_{1},\ldots,x_{b},u_{j},\ldots,u_{0}\rangle$ (przechodząc wzdłuż $P_{1}$ do $v_{i}$ , a następnie przez most utworzony przez $P'$ z $u_{j}$ , a następnie wzdłuż $P_{2}$ do $u_{0}$ ).

$P^{*}$ $k+1$ $G$ $k$

$k$

— Luke Mathieson
źródło

I think you need

j \leq ⌊ \frac{k}{2} ⌋

$j \leq \lfloor\frac{k}{2}\rfloor$ , otherwise the new path is not necessarily longer. Note that

b = 0

$b=0$ is possible.

— Raphael

@Raphael Yes, I didn't explicitly state it (and used slightly misleading notation), but

b

$b$ can quite happily be

0

$0$ , the bridge always adds at least one edge though, even if the only vertices in

P^{'}

$P'$ are

v_{i}

$v_{i}$ and

u_{j}

$u_{j}$ . On the first point, note that I've constructed the path from

v_{0} \to v_{i} \to u_{j} \to u_{0}

$v_{0} \rightarrow v_{i} \rightarrow u_{j}\rightarrow \mathbf{u_{0}}$ , so

j \geq ⌈ \frac{k}{2} ⌉

$j \geq \lceil\frac{k}{2}\rceil$ is right. If it went to

u_{k}

$u_{k}$ then

j \leq ⌊ \frac{k}{2} ⌋

$j \leq \lfloor\frac{k}{2}\rfloor$ would be the right condition.

— Luke Mathieson

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