LINUX.ORG.RU
ФорумTalks

задачка для небольшой разминки

 


0

1

пусть в графе существует (простой) цикл C. И пусть между какими-то двумя узлами v,w этого цикла есть путь длиной k. Покажите, что тогда в этом графе существует (простой) цикл длиной не меньше sqrt(k).

★★☆☆☆

ну тогда очевидно длина цикла С не меньше k+1. k+1 > sqrt(k)

cvs-255 ★★★★★ ()
Ответ на: комментарий от cvs-255

Сам цикл C может быть и короче, потому что не сказано что путь принадлежит циклу.

Zeta_Gundam ()

А почему именно sqrt(k), можно поинтересоваться?

Zeta_Gundam ()
Ответ на: комментарий от cvs-255

ну тогда очевидно длина цикла С не меньше k+1

нет.

dikiy ★★☆☆☆ ()
Ответ на: комментарий от Zeta_Gundam

А почему именно sqrt(k), можно поинтересоваться?

ну такая вот граница

dikiy ★★☆☆☆ ()
Последнее исправление: dikiy (всего исправлений: 1)
Ответ на: комментарий от Zeta_Gundam

Сам цикл C

А какая разница, может и не цикл C, так даже лучше, получается ещё джва цикла (путь длиной k + пути от v к w через C), длина которых больше k

TheAnonymous ★★★★★ ()
Ответ на: комментарий от TheAnonymous

получается ещё джва цикла (путь длиной k + пути от v к w через C), длина которых больше k

не факт, что такие циклы существуют. Для этого пути от v к w через C должны не пересекаться с путем, который k.

dikiy ★★☆☆☆ ()

Ещё можно тупо мотать круги через C, пока длина не превзойдёт sqrt(k)

TheAnonymous ★★★★★ ()
Ответ на: комментарий от TheAnonymous

а что нужен простой цикл, условия не было

очевидно, что подразумеваются именно такие.

dikiy ★★☆☆☆ ()

Кто-то в пятом классе знал, что такое граф?

DELIRIUM ★★★★☆ ()
Ответ на: комментарий от German_1984

А если бы тебе сказали, что в титуле какой-то цикл?

DELIRIUM ★★★★☆ ()

Рассмотрим путь v=v0, v1, v2,..., vk=w. Пусть S={i | vi принадлежит C}. Очевидно, 0 и k принадлежат S. Если #S >= sqrt(k), то цикл C содержит как минимум sqrt(k) вершин, то есть имеет длину не меньше sqrt(k). Предположим, что #S < sqrt(k); перенумеруем элементы S: S = {i0=0, i1, i2,..., in=k}. Тогда (i1-i0) + (i2-i1) + ... + (in-i{n-1}) = in-i0 = k, и количество слагаемых равно #S-1 < sqrt(k). Значит, при каком-то j, ij - i{j-1} > sqrt(k); в противном случае вся сумма была бы не больше sqrt(k)*(#S-1) < k. По определению S, все вершины vm при i{j-1}<m<ij не принадлежат циклу C; значит, добавив к отрезку нашего пути между i{j-1} и ij кусок цикла C, соединяющий ij с i{j-1}, мы получаем простой цикл, и его длина будет не меньше sqrt(k).

Miguel ★★★★★ ()
Ответ на: комментарий от Miguel

Предположим, что #S < sqrt(k); перенумеруем элементы S: S = {i0=0, i1, i2,..., in=k}. Тогда (i1-i0) + (i2-i1) + ... + (in-i{n-1}) = in-i0 = k,

вот тут непонятно. Почему in=k? Или эта нумерация как-то связана с v0...vk?

dikiy ★★☆☆☆ ()
Ответ на: комментарий от DELIRIUM

Сейчас и в 6 классе не знают. Но бегут и постят свои догадки на ЛОР.

burato ★★ ()
Ответ на: комментарий от Miguel

все верно.

PS
можно получить кстати еще лучшую оценку, но идея все равно та же.

dikiy ★★☆☆☆ ()
Закрыто добавление комментариев для недавно зарегистрированных пользователей (со score < 50)