Задача от теория на графите

[Гост]

Здравейте,

не мога да реша следната задача

В една държава има 2024 града. Между някой от тези градове има директни, използваеми и в двете посоки самолетни връзки. При това няма нито един град, който да има със всички останали 2023 града такава директна връзка. Известно е обаче , че за едно определено цяло положително число к важи следното : За произволен к на брой градове в държавата винаги има един допълнителен/друг град, които има с всеки един от тези к града една директна самолетна връзка.

Да се определи максималната стойност , която к може да има при тези условия.

Как се решава тази задача?

[Гост]

Може ли да дадете следното пояснение.

Какво се има предвид под „ . . . има един допълнителен/друг град, . . .“ в условието по-горе.

Има точно един допълнителен/друг град, т.е. нито 0, нито 2, 3 и т.н. или има поне един, т.е. може да има 2, 3, 4 и т.н.

Ако задачата е превод от английски, по-добре дайте оригиналното условие.

[Гост]

От условието на задачата наистина не става ясно кой от двата случая се има предвид. За съжаление не разполагам с текста на английски, но мога в понеделник да попитам за пояснение.

[Гост]

Все още не е уточнено дали се касае за точно или поне един град. Докато това стане, следното уточнение към условието, което може би е от значение : ....За произволен к на брой градове...да се разбира по-скоро като... за к на брой произволно избрани градове...

Търсим най–голямата стойност на к за която важи– независимо които и да е к града вземем, от тези общо 2024 , винаги ще се намери един друг град извън групата на тези к града който да е свързан с всички тях. Кои градове вземаме не е важно, важното е те да са к на брои. Например ако к=5 тогава които и 5 града от тези общо 2024 да вземем ,стига те да са 5, винаги ще се намери един 6-ти град извън тези 5 който да е свързан с всички от останалите 5.

Може ли така погледнато въпроса дали е точо или поне един град да не е толкова важен ?

[Гост]

Сега най-после дойде пояснението: Касае за ... най-малко един допълнителен град ...


Така текста на задачата става:



В една държава има 2024 града. Между някой от тези градове има директни, използваеми и в двете посоки самолетни връзки. При това няма нито един град, който да има със всички останали 2023 града такава директна връзка. Известно е обаче , че за едно определено цяло положително число к важи следното : За произволен к на брой градове в държавата винаги има най-малко един допълнителен/друг град, които има с всеки един от тези к града една директна самолетна връзка.

Да се определи максималната стойност , която к може да има при тези условия.


Все пак задачата остава трудна за мен.

[Гост]

Авиолинии-page-001.jpg (323.56 KiB) Прегледано 271 пъти

Авиолинии-page-002.jpg (299.29 KiB) Прегледано 271 пъти

Авиолинии-page-003.jpg (275.51 KiB) Прегледано 271 пъти