Beweisen Sie, dass alle zwei längsten Pfade mindestens einen Scheitelpunkt gemeinsam haben

Wenn ein Graph verbunden ist und keinen Pfad mit einer Länge größer als , beweisen Sie, dass alle zwei Pfade in der Länge mindestens einen Scheitelpunkt gemeinsam haben. $G$ $k$ $G$ $k$

Ich denke, dass dieser gemeinsame Scheitelpunkt in der Mitte beider Pfade liegen sollte. Wenn dies nicht der Fall ist, können wir einen Pfad mit einer Länge . Habe ich recht? $>k$

graph-theory graphs combinatorics Saurabh
quelle

Gegenbeispiel für einen gerichteten Graphen, der nicht stark verbunden ist: Eckpunkte

, Kanten

, die Pfade

und

haben keinen gemeinsamen Eckpunkt.

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, du könntest es als Antwort geben.

@sdcvvc Ich denke, die Frage ist auf ungerichtete Grafiken beschränkt.

Raphael

Können Sie bestätigen (oder bestätigen), dass

ein ungerichteter Graph ist und Sie nur einfache (= zyklenfreie) Pfade in Betracht ziehen ?

G

$G$

Gilles 'SO- hör auf böse zu sein'

@Gilles Ja, der Graph ist ungerichtet und der Pfad ist begehbar. Er enthält unterschiedliche Kanten und Scheitelpunkte.

Saurabh

Antworten:

Es sei angenommen , daß für Widerspruch $P_{1} = \langle v_{0},\ldots,v_{k}\rangle$ und $P_{2} = \langle u_{0},\ldots,u_{k}\rangle$ sind zwei Pfade in $G$ der Länge $k$ ohne gemeinsam genutzten Ecken.

Wenn $G$ verbunden ist, gibt es einen Pfad $P'$ , der $v_{i}$ mit $u_{j}$ für einige $i,j \in [1,k]$ so dass $P'$ keine anderen Eckpunkte mit $P_{1} \cup P_{2}$ als $v_{i}$ und $u_{j}$ teilt . Sprich : $P' = \langle v_{i},x_{0},\ldots,x_{b},u_{j}\rangle$ (beachten Sie, dass es keine sein kann $x_{i}$ Eckpunkte, dh $b$ kann $0$ - die Bezeichnung ist etwas mangelhaftobwohl).

Ohne Verlust der Allgemeinheit können wir annehmen, dass $i,j \geq \lceil\frac{k}{2}\rceil$ (wir können die Nummerierung jederzeit umkehren). Dann können wir einen neuen Weg konstruieren $P^{*} = \langle v_{0},\ldots,v_{i},x_{1},\ldots,x_{b},u_{j},\ldots,u_{0}\rangle$ (durch entlang gehen $P_{1}$ auf $v_{i}$ , dann über die Brücke gebildet durch $P'$ bis $u_{j}$ , dann entlang $P_{2}$ bis $u_{0}$ ).

Offensichtlich hat $P^{*}$ eine Länge von mindestens $k+1$ , was jedoch der Annahme widerspricht, dass $G$ keine Pfade mit einer Länge von mehr als $k$ .

Dann müssen sich zwei Pfade der Länge $k$ an mindestens einem Scheitelpunkt schneiden, und Ihre Beobachtung, dass sie in der Mitte liegen muss (falls es nur einen gibt), folgt den von Ihnen gemachten Überlegungen.

Luke Mathieson
quelle

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

$j \leq \lfloor\frac{k}{2}\rfloor$

b = 0

$b=0$

b

$b$

0

$0$

P^{'}

$P'$

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
quelle