Докажите, что каждые два самых длинных пути имеют хотя бы одну общую вершину

Если граф $G$ связен и не имеет пути длиной больше $k$ , докажите, что каждые два пути в $G$ длины $k$ имеют хотя бы одну общую вершину.

Я думаю, что эта общая вершина должна быть в середине обоих путей. Потому что, если это не так, то мы можем иметь путь длиной $>k$ . Я прав?

graph-theory graphs combinatorics Саурабх
источник

Контрпример для не сильно связного ориентированного графа: вершины

, ребра

, пути

имеют общей вершины.

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, вы могли бы предоставить это как ответ.

@sdcvvc Я думаю, что вопрос ограничен неориентированными графами.

Рафаэль

Можете ли вы подтвердить (или опровергнуть), что

является неориентированным графом, и вы рассматриваете только простые (= без цикла) пути?

G

$G$

Жиль "ТАК - перестань быть злым"

@Gilles Да, график ненаправленный, и путь - это путь, в котором содержатся различные ребра и вершины.

Саурабх

Ответы:

Предположим противного , что $P_{1} = \langle v_{0},\ldots,v_{k}\rangle$ и $P_{2} = \langle u_{0},\ldots,u_{k}\rangle$ два пути в $G$ длины $k$ без общих вершин.

Поскольку $G$ связно, существует путь $P'$ соединяющий $v_{i}$ с $u_{j}$ для некоторого $i,j \in [1,k]$ такой, что $P'$ разделяет вершин с $P_{1} \cup P_{2}$ кроме $v_{i}$ и $u_{j}$ . Скажем $P' = \langle v_{i},x_{0},\ldots,x_{b},u_{j}\rangle$ (обратите вниманиечто там может быть не $x_{i}$ вершина, то есть, $b$ может быть $0$ - обозначение немного дефицитныехотя).

Без ограничения общности можно считать, что $i,j \geq \lceil\frac{k}{2}\rceil$ (мы всегда можем изменить нумерацию). Тогда мы можем построить новый путь $P^{*} = \langle v_{0},\ldots,v_{i},x_{1},\ldots,x_{b},u_{j},\ldots,u_{0}\rangle$ (идя по $P_{1}$ к $v_{i}$ , затем через мост формируется через $P'$ до $u_{j}$ , то вдоль $P_{2}$ до $u_{0}$ ).

Очевидно, что $P^{*}$ имеет длину, по крайней мере, $k+1$ , но это противоречит предположению, что $G$ не имеет путей длины, превышающих $k$ .

Таким образом, любые два пути длины $k$ должны пересекаться хотя бы с одной вершиной, и ваше наблюдение, что оно должно быть посередине (если есть только один), следует вашим рассуждениям.

Люк Мэтисон
источник

Я думаю, что вам нужно

, иначе новый путь не обязательно будет длиннее. Обратите внимание, что

возможно.

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

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

b = 0

$b=0$

Рафаэль

@Raphael Да, я не явно указать это (и используется немного вводит в заблуждение обозначения), но

вполне может счастливо быть

, мост всегда добавляет по меньшей мере один край , хотя, даже если только вершины

являются

. По первому пункту обратите внимание, что я построил путь из

, поэтому

b

$b$

0

$0$

P^{'}

$P'$

v_{i}

$v_{i}$

u_{j}

$u_{j}$

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

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

правильно. Если это пошло к

тогда

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

$j \geq \lceil\frac{k}{2}\rceil$

u_{k}

$u_{k}$

будет правильным условием.

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

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

Люк Мэтисон

Вы правы, что общая вершина должна находиться в середине обоих путей.

Однако эта интуиция не решит реальную проблему, которую вы пытаетесь решить.

Вместо этого попытайтесь продемонстрировать, что для любой точки пути сегмент пути (и включая), который указывает на один из концов исходного пути, должен иметь строго больше половины узлов, чем полный путь.

Как только вы докажете это, вы сможете как решить проблему, о которой вас спрашивали, так и проверить свою гипотезу.

btilly
источник