Стратегічна задача на оптимізацію кількості інформаційних зв’язків

Стратегічна задача на  оптимізацію кількості

 інформаційних  зв’язків між користувачами.

У деякій освітній системі є n працівників. Між деякими із них здійснюються двосторонні мобільні зв'язки.

 Відомо, що з мобільного телефону будь-якого працівника можна додзвонитися до будь-якого мобільного іншого працівника. 

Провайдер-фірма хоче вибрати декілька працівників і назвати їх вузловими  операторами таким чином, що із будь-якого  мобільного системи освіти існує прямий зв'язок до деякого вузлового оператора системи освіти. 

Яку найменшу  кількість вузлових міст треба обрати, щоб гарантовано, навіть у найгіршому випадку, вистачило усіх цих  зв'язків  провайдер-фірмі.

Відповідь: m(n)=n-[n/3]-1.

Вказівка. Переформулюємо умову задачі на мові теорії графів. Потрібно знайти таке мінімальне число s,  що у будь-якому зв’язному графі, у якого n вершин можна відмітити не більше ніж s його вершин таким чином, що у будь-якої вершини знайдеться відмічена сусідня вершина(вважаємо,  що сусідня вершина зветься сусідкою).

Доведемо, що s >= n-[n/3]-1. Розглянемо граф з чотирма вешинами v⁽⁰⁾, v⁽¹⁾_j, v⁽²⁾ _j, v⁽³⁾_j , j = 1, . . . , [n/3], та ребрами (v⁽⁰⁾, v⁽¹⁾_j), (v⁽¹⁾, v⁽²⁾_j),  (v⁽²⁾, v⁽³⁾_j), j = 1, . . . , [n/3].

Нехай k - довільне число від 1 до [n/3]. У вершин v⁽²⁾ _k, v⁽³⁾_k  повинна бути відмічена сусідка, а це значить обов’язково буде відмічена v⁽²⁾ _k, як єдина сусідка v⁽³⁾_k  і одна з вершин v⁽¹⁾_j, v⁽³⁾_j повинна бути відмічена, оскільки інших сусідів у   v⁽²⁾ _k  немає. Таким чином, всього повинно бути відмічено  не менше  2*[n/3]-1 вершини.

Доведемо, що s <= n-[n/3]-1. Можна вважати, що заданий граф являється деревом, так як в протилежному випадку можна виділити скріплююче дерево і довести твердження для нього.  Виберемо в якості кореня висячу вершину і назвемо її v⁽⁰⁾,а інші розташуємо по рівнях стандартним чином.  Розфарбуємо вершини в три кольори так, що  вершини на рівнях 3k+1 пофарбовані в один колір, на рівнях виду 3k+2 пофарбовані в другий колір, а інші в третій колір. За принципом Діріхле знайдеться такий колір, в який пофарбовано що найменше  [n/3]+1 вершини. Відмітимо вершини інших кольорів. Тоді ми відмітили не більше n-[n/3]-1 вершин, і у будь-якої невисячої вершини є відмічена сусідня вершина. Нехай v – висяча вершина(v не дорівнює v⁽⁰⁾),  нехай v₁ – батько– батько v₁. ВІдмітимо, що v₂ існує, так як рівнів не менше трьох. Якщо у v не існує відміченої v, v₂ сусідньої вершини, то v₁ – невідмічена, а значіть, відмічені  v та  v₂. Приберемо мітку з вершини v, та відмітимо вершину v₁. Тоді кількість відмічених вершин не зміниться, у всіх вершин, у яких   була відмічена сусідка, вона залишається, а також вона і у вершини v тепер буде відмічена сусідка. Аналогічно зробимо для кореневої вершини. Зробивши, при необхідності подібну операцію скінчену кількість разів, ми отримаємо те, що у всіх вершин була відмічена сусідка. Що і вимагало довести.