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

14

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

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

Saurabh
quelle
2
Gegenbeispiel für einen gerichteten Graphen, der nicht stark verbunden ist: Eckpunkte , Kanten A C , A D , B D , die Pfade A C und B D haben keinen gemeinsamen Eckpunkt. A,B,C,DACADBDACBD
SDCVVC
@sdcvvc, du könntest es als Antwort geben.
2
@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
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:

21

Es sei angenommen , daß für Widerspruch P1=v0,,vk und P2=u0,,uk sind zwei Pfade inG der Längek ohne gemeinsam genutzten Ecken.

Wenn G verbunden ist, gibt es einen Pfad P , der vi mit uj für einige i,j[1,k] so dass P keine anderen Eckpunkte mit P1P2 als vi und uj teilt . Sprich : P=vi,x0,,xb,uj (beachten Sie, dass es keine sein kann xi Eckpunkte, dhb kann0 - die Bezeichnung ist etwas mangelhaftobwohl).

Ohne Verlust der Allgemeinheit können wir annehmen, dass i,jk2(wir können die Nummerierung jederzeit umkehren). Dann können wir einen neuen Weg konstruierenP=v0,,vi,x1,,xb,uj,,u0(durch entlang gehenP1aufvi, dann über die Brücke gebildet durchPbisuj, dann entlangP2 bis u0 ).

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
jk2b=0
1
b0Pvi 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
quelle