Вступ
У математиці, як і в житті, невеликі рішення можуть мати великі наслідки. Особливо це стосується теорії графів, галузі, яка вивчає мережі об’єктів і зв’язки між ними. Ось невелика головоломка, яка допоможе вам зрозуміти, чому.
Маючи шість крапок, ваша мета полягає в тому, щоб з’єднати їх одна з одною відрізками так, щоб між будь-якою парою крапок завжди був шлях, причому жоден шлях не перевищував би довжину двох відрізків. Припиніть прокручування на мить і спробуйте знайти рішення.
Якщо ви її розв’язали, я впевнений, що у вас є щось, що виглядає так:
(натисніть тут, щоб відкрити відповідь)
Зауважте, що це справді задовольняє вимоги головоломки. Існує шлях між будь-якими двома точками — те, що теоретики графів називають вершинами — і жоден шлях не є довшим за два відрізки лінії або ребра. (Примітка: у головоломці та в усьому стовпчику шляхи не можуть використовувати одне й те саме ребро більше ніж один раз.) Ваше рішення може виглядати дещо інакше, але ви отримаєте ту саму основну структуру, яку легше побачити, якщо ви трохи пересуваєте вершини.
Ця «зіркова» структура в теорії графів має одну центральну вершину, яка з’єднується з кожною групою інших вершин одним ребром, без ребер між іншими вершинами. Ця зірка — не просто вирішення нашої головоломки; це єдине рішення. (Ви отримаєте можливість довести це у вправах у кінці колонки.)
Ця головоломка ілюструє, як локальні обмеження, як-от заборона шляхів довжиною 3 або більше, іноді можуть змусити глобальні структури, такі як зірка, з’явитися в результаті. Використання подібних зв’язків може бути потужним інструментом для розуміння графіків і мереж, особливо коли ви шукаєте певні важливі структури.
Однією з таких структур є «клік» — набір вершин, де кожна вершина безпосередньо з’єднана з кожною іншою вершиною ребром. Кліки важливі, оскільки вони визначають зони максимального зв’язку та залежності. Наприклад, у мережі маршрутів авіаліній кліка представляє групу міст, які з’єднані між собою прямими рейсами в обох напрямках. Це джерело сили в мережі, оскільки ви можете дістатися до будь-якого міста за один рейс, і якщо маршрут скасовано, ви все одно зможете з відносною легкістю приєднатися до будь-якого пункту призначення.
Навпаки, «антикліка» — це набір вершин, жодна з яких не пов’язана безпосередньо з іншими. На карті польотів це представляє групу міст, між якими немає прямих рейсів. Можливо, ви все ще зможете дістатися з точки А в точку Б за допомогою антикліку, але не напряму. Спочатку вам доведеться виїхати за межі групи, тому дорога туди коштуватиме вам: часу, грошей або, загалом, ефективності. У певному сенсі антикліки визначають області максимальної незалежності в мережі, і з цієї причини вони також відомі як незалежні набори. (Ви також можете побачити, що ці набори в інших місцях називають «кокліками» або «стабільними наборами».)
Знаходження великих клік або великих незалежних множин, або навіть просто гарантія їхнього існування, виявляється важливою частиною аналізу графіків і мереж. І ось тут з’являється гіпотеза Ердеша-Хайнала. Вона говорить, що якщо ви забороните певні локальні структури на графах, то певних глобальних структур — зокрема, відносно великих клік або відносно великих незалежних наборів — не уникнути. Це одне з багатьох відкритих питань приписується Паулю Ердешу, відомий математичний кочівник, який мандрував світом, ділячись кавою та припущеннями з тисячами співробітників. Коли гіпотеза Ердеша-Хайнала справедлива, вона надає інформацію, яку можуть використовувати вчені в таких різноманітних галузях, як біологія, логістика та інформатика, щоб зробити ще більш переконливі висновки щодо глобальних структур їхніх мереж.
Насправді ми вже бачили гіпотезу Ердеша-Хайнала в дії. У нашій оригінальній головоломці форми зірки було неминуче, і, як виявилося, ця форма гарантує великий незалежний набір. П'ять вершин, з'єднаних з центром зірки, не мають інших зв'язків один з одним. Ви можете побачити цю незалежну множину, ігноруючи центральну вершину та ребра, які з’єднуються з нею.
Зауважте, що існування цього незалежного набору попереджає нас про вразливість у нашій мережі. Якби це була карта польотів, і центральне місто стало б недоступним, ніхто б нікуди не зміг полетіти.
У нашій головоломці заборона локальної структури шляхів довжиною 3 або більше гарантує незалежний набір розміром 5. Однак ця головоломка спирається на те, чого немає в гіпотезі Ердеша-Хайнала, а саме на те, що існує шлях між будь-якими двома вершинами. Це означає, що графік має бути «зв’язаним», і це не є частиною гіпотези Ердеша-Хайнала. Чи не уникнути великої незалежної множини, якщо такий граф не обов’язково зв’язний?
Щоб побачити, чи можна уникнути великого незалежного набору в нашому графіку, давайте подумаємо як математик і почнемо з розгляду крайніх випадків. Якщо від нас не вимагають підключати все, що робити, якщо ми нічого не підключаємо?
Якщо взагалі не додавати ребер, то ми отримуємо найбільший незалежний набір, усі шість вершин. Насправді будь-яку вершину, яка не з’єднується з ребром, можна додати до будь-якої існуючої незалежної множини, щоб збільшити її, тому, щоб отримати менші незалежні множини, ми, ймовірно, хочемо, щоб кожна вершина мала принаймні одне ребро. А як щодо чогось подібного?
Цей граф складається з двох частин, і ви можете отримати незалежний набір розміром 4, вибравши дві вершини на кінцях кожної частини. Зверніть увагу, що жодна з чотирьох вибраних вершин не з’єднана ребром з жодною з інших, таким чином утворюючи незалежну множину.
А як щодо такого графіка?
Цей граф складається з трьох незв’язаних частин, і ви можете отримати незалежний набір розміром 3, вибравши одну вершину з кожної частини.
Виявляється, це найменший незалежний набір, який ми можемо отримати за даних умов. Іншими словами, у графі з шістьма вершинами заборонні шляхи довжиною 3 гарантують незалежний набір, який є принаймні половиною розміру оригінального графа, який є досить великим, коли мова йде про графи.
Насправді відбувається щось більш загальне. Усі графіки, які ми досліджували, мають одну важливу спільну рису: усі вони є наборами зірок!
Граф ліворуч — це дві зірки по три вершини, а граф праворуч — три зірки по дві вершини кожна. Навіть граф без ребер можна уявити як шість зірок з однією вершиною кожна. Правило, яке забороняє шляхи довжиною 3, змушує граф бути набором зірок, і це вірно незалежно від того, чи ви починаєте з шести вершин, чи з 600. Тому, коли справа доходить до пошуку незалежних наборів, єдине питання полягає в тому, скільки роз’єднаних зірок ви закінчуєте вгору з.
Загалом, якщо ви отримаєте багато зірок, легко отримати великий незалежний набір. Оскільки зірки не пов’язані одна з одною, ви можете просто вибрати одну вершину з кожної зірки, тому це гарантує незалежний набір, щонайменше стільки ж, скільки кількість зірок. У прикладі вище праворуч ви можете взяти по одній вершині з кожної з трьох зірок розміру 2 і створити незалежний набір розміру 3.
З іншого боку, якщо ви отримаєте лише кілька зірок, самі зірки мають бути достатньо великими, щоб врахувати всі вершини початкового графа, і ми вже бачили, як отримати відносно великий незалежний набір із зірки — просто взяти все, крім центральної вершини. Наприклад, якщо граф складається лише з двох зірок, то одна із зірок гарантовано містить принаймні половину вершин вихідного графа, і це гарантує незалежний набір приблизно вдвічі менший за вихідний граф. У нашому прикладі ми можемо створити ще більшу незалежну множину, об’єднавши незалежні множини з роз’єднаних зірок. (Наскільки малим може бути найбільший можливий незалежний набір? Більше про це див. у вправах.)
Загалом, для графа, який є лише набором незв’язаних зірок, великого незалежного набору не уникнути. Великі зірки утворюють великі незалежні набори, але маленькі зірки означають багато зірок, які також створюють великі незалежні набори. Цей підхід працює не лише для нашого простого прикладу. Він також підказує, як вирішити більш складну проблему.
Припустимо, у вас є графік із n вершин, і ви накладаєте наступне локальне обмеження: жодні три вершини не можуть бути з’єднані одна з одною. Це було б схоже на розробку карти польотів із конкретною метою мінімізації локально надлишкових маршрутів. Якщо ви можете дістатися між A і B і між B і C, то вам не дозволено створювати окремий прямий маршрут між A і C.
Іншими словами, не може бути клік розміром 3. З точки зору геометрії, граф «без трикутників».
Чи повинен граф без трикутників мати відносно великий незалежний набір? Відповідь - так, і, як і раніше, секрет криється в зірках. Ми можемо показати, що граф без трикутника з n вершини повинні мати незалежний набір розміром принаймні приблизно $latex sqrt{n}$, що є відносно великим за стандартами теорії графів. Давайте пройдемося по аргументу, використовуючи наступний графік без трикутників як приклад.
Почніть із вибору будь-якої вершини на графі та розглядання всіх її сусідів — вершин, з’єднаних із нею ребром.
Жоден із цих сусідів обраної вами вершини не з’єднаний один з одним — тому що це утворить трикутник, а це граф без трикутників — тому кожна вершина та її набір сусідів по суті утворюють зірку.
Незважаючи на те, що ця зірка пов’язана з іншими вершинами графа, ми можемо використовувати її властивості, щоб гарантувати великий незалежний набір. Головне – сформувати зірку, а потім видалити її та всі краї, які з’єднуються з нею.
Тепер знайдіть зірочку на графіку, що залишився, і також видаліть її.
У цьому прикладі тепер у нас залишилося дві одиничні вершини — самі одновершинні зірки — і ми формуємо незалежний набір розміром 4, додаючи центральні вершини з двох інших зірок, які ми знайшли. Оскільки наш вихідний граф має дев’ять вершин і $latex sqrt{9}=3$, наш незалежний набір розміром 4 відповідає нашій гіпотезі.
Цей аргумент працює загалом для будь-якого графа без трикутників. Ключ у тому, щоб просто продовжувати знаходити та видаляти зірки та ребра, які з’єднуються з ними, доки ви не врахуєте всі вершини. Зробивши це, просто порахуйте кількість зірок.
Скажімо, ви закінчите з k зірки. Якщо $latex k > sqrt{n}$, ви можете сформувати незалежний набір розмірів k взявши центральну вершину кожної зірки. Це працює, тому що жодні дві центральні вершини будь-яких двох зірок не можуть бути з’єднані одна з одною, оскільки це зробило б їх сусідами у вихідному графі.
Якщо $latex k < sqrt{n}$, то ця менша кількість зірок гарантує, що принаймні одна із зірок має бути відносно великою. Насправді він повинен мати принаймні $latex sqrt{n}$ вершин. чому Тому що все n вершини графа повинні бути знайдені серед k зірки. Якщо всі k зірки мали менше ніж $latex sqrt{n}$ вершин кожна, то загальна кількість вершин у графі була б меншою ніж $latex k помножених на sqrt{n}$. Але оскільки $latex k < sqrt{n}$, це означає, що загальна кількість вершин у графі має бути меншою ніж $latex sqrt{n}, помножена на sqrt{n} = n$. Оскільки ми знаємо, що графік має n вершин, припущення, що зірки малі, залишає деякі вершини неврахованими, що означає, що принаймні одна із зірок повинна мати принаймні $latex sqrt{n}$ вершин. А зірка розміром $latex sqrt{n}$ гарантує незалежний набір розміром принаймні $latex sqrt{n} -1$, що приблизно дорівнює $latex sqrt{n}$. (Теоретиків графів зазвичай цікавить розмір підграфа відносно вихідного розміру графа, тому $latex sqrt{n}$ є набагато важливішим, ніж $latex – 1$.)
Як і в нашому оригінальному прикладі, цей результат про графи без трикутників пов’язаний з гіпотезою Ердеша-Хайнала. Якщо граф не містить трикутників, він не може мати клік, більший за розмір 2, оскільки клік розміром 3 або більше потребує трикутника. Заборона трикутників означає заборону великим клікам, і це змушує з’являтися великі незалежні набори, як і передбачає гіпотеза Ердеша-Хайнала.
Нещодавно математики довели набагато більше. Гіпотезу Ердеша-Хайнала було доведено у всіх випадках, коли заборонений підграф складається з чотирьох або менше вершин (як квадрат або шлях довжиною 4). А в 2021 році група математиків доведений що якщо граф не містить п’ятикутників — тобто петлі, яка з’єднує п’ять вершин — то як наслідок має існувати надзвичайно велика кліка або надзвичайно велика незалежна множина. Це здивувало деяких математиків, які доводили це, оскільки вони очікували, що гіпотеза Ердеша-Хайнала буде хибною для п'ятикутників. Це був ще один напрочуд потужний математичний результат, який став результатом мислення локально, щоб діяти глобально.
Вступ
Вступ
1. Припустимо, що найбільша незалежна множина, яку ви можете знайти в графі, має розмір 1. Що ви можете сказати про граф?
Натисніть, щоб отримати відповідь 1:
Це означає, що в графі існує кожне можливе ребро. У цьому випадку сам граф є клікою. Ми називаємо такі графи «повними графами».
Вступ
2. Поясніть, чому в зв’язному графі без шляхів довжиною 3 або більше неможливо отримати нічого, крім зірки.
Натисніть, щоб отримати відповідь 2:
Якщо є лише одна вершина, це зірка, і ми готові. Якщо вершин дві, їх необхідно з'єднати, утворюючи двовершину зірку. Якщо є три вершини, то між ними можуть існувати три можливі ребра. Відповідно до умов, три вершини повинні утворювати шлях довжиною 2, ось так:
Це тому, що якби будь-яке з цих ребер було відсутнє, то графік не був би зв’язаним, але якщо б ви додали третє ребро, ви б створили трикутник, який дасть вам шлях довжиною 3.
Якщо є ще якісь вершини, де вони можуть з’єднатися? Це має бути середня вершина і лише середня вершина. З’єднання з вершиною на будь-якому кінці одразу створить шлях довжиною 3. Таким чином, результатом буде група вершин, усі з’єднані одним ребром із центральною вершиною. Іншими словами, зірка.
Вступ
3. Нехай граф с n вершини не має шляхів довжиною 3. Наскільки великий незалежний набір гарантується в такому графі?
Натисніть, щоб отримати відповідь 3:
If n є парним, $latex frac{n}{2}$; якщо n є непарним, $latex frac{n+1}{2}$. Іншими словами, «стеля» $latex frac{n}{2}$, написана $latex lceil{frac{n}{2}}rceil$.
Ми вже знаємо, що такий граф має бути набором незв’язаних зірок, а оскільки зірки є роз’єднаними, ми завжди можемо сформувати незалежну множину, об’єднавши незалежні множини кожної окремої зірки. Ми також знаємо, що кожна зірка може додати всі свої вершини, крім однієї, до незалежного набору, просто опустивши центр. Зокрема, якщо зірка має розмір m > 1, то це може сприяти m − 1 її вершини до незалежної множини. Стратегія полягає в тому, щоб зробити m − 1 якомога менше для кожної зірки, і для цього потрібно зробити якомога більше зірок із двома вершинами.
If n парне, ви отримуєте купу таких пар:
І ви формуєте незалежний набір, беручи одну вершину з кожної, отримуючи незалежний набір, розмір якого дорівнює кількості зірок: $latex frac{n}{2}$.
If n дивно, у вас залишиться одна вершина, коли ви об’єднаєте вершини.
Тут незалежний набір буде складатися з однієї вершини з кожної з пар $latex frac{n-1}{2}$ плюс залишена вершина для незалежного набору розміром $latex frac{n-1}{2} + 1 = frac{n+1}{2}$.
- Розповсюдження контенту та PR на основі SEO. Отримайте посилення сьогодні.
- PlatoData.Network Vertical Generative Ai. Додайте собі сили. Доступ тут.
- PlatoAiStream. Web3 Intelligence. Розширення знань. Доступ тут.
- ПлатонЕСГ. Автомобільні / електромобілі, вуглець, CleanTech, Енергія, Навколишнє середовище, Сонячна, Поводження з відходами. Доступ тут.
- BlockOffsets. Модернізація екологічної компенсаційної власності. Доступ тут.
- джерело: https://www.quantamagazine.org/math-that-lets-you-think-locally-but-act-globally-20230721/
- : має
- :є
- : ні
- :де
- ][стор
- $UP
- 1
- 2021
- a
- Здатний
- МЕНЮ
- вище
- рахунки
- Achieve
- Діяти
- дію
- насправді
- доданий
- додати
- авіакомпанія
- Alerts
- ВСІ
- дозволено
- вже
- Також
- завжди
- серед
- an
- Аналізуючи
- та
- Інший
- відповідь
- будь-який
- все
- де-небудь
- підхід
- ЕСТЬ
- області
- аргумент
- навколо
- AS
- припущення
- At
- уникнути
- BE
- стали
- оскільки
- було
- перед тим
- Парі
- між
- Великий
- більший
- найбільший
- біологія
- Біт
- обидва
- гроно
- але
- by
- call
- прийшов
- CAN
- Може отримати
- випадок
- випадків
- Центр
- центральний
- певний
- шанс
- вибір
- Вибирати
- вибраний
- Міста
- Місто
- клацання
- кліка
- кави
- збір
- Колекції
- Колонка
- об'єднання
- приходить
- загальний
- складний
- комп'ютер
- Інформатика
- Умови
- припущення
- З'єднуватися
- підключений
- З'єднувальний
- Зв'язки
- зв'язок
- з'єднує
- Наслідки
- беручи до уваги
- складається
- містити
- містить
- контрастність
- сприяти
- Коштувати
- може
- створювати
- залежність
- проектування
- призначення
- різний
- прямий
- безпосередньо
- відключившись
- Різне
- do
- робить
- Ні
- зроблений
- Не знаю
- малювати
- Випадання
- кожен
- простота
- легше
- легко
- край
- ефективність
- або
- в іншому місці
- з'являтися
- кінець
- закінчується
- досить
- рівним
- особливо
- істотний
- по суті
- Навіть
- Кожен
- все
- приклад
- перевищує
- існувати
- існування
- існуючий
- існує
- очікуваний
- Пояснювати
- Розвіданий
- екстремальний
- факт
- false
- знаменитий
- кілька
- менше
- поле
- Поля
- знайти
- виявлення
- Перший
- політ
- Авіаквитки
- після
- для
- Примусово
- Війська
- форма
- форми
- знайдений
- чотири
- від
- Загальне
- в цілому
- отримати
- отримання
- Давати
- даний
- дає
- Глобальний
- Глобально
- мета
- буде
- графік
- графіки
- Group
- гарантувати
- гарантований
- гарантії
- було
- Половина
- рука
- обробляти
- Мати
- допомога
- тут
- тримає
- Як
- How To
- Однак
- HTTPS
- i
- ідентифікувати
- if
- ілюструє
- негайно
- важливо
- накладений
- неможливе
- in
- В інших
- недоступний
- дійсно
- незалежність
- незалежний
- індивідуальний
- інформація
- зацікавлений
- IT
- ЙОГО
- сам
- просто
- тримати
- ключ
- Знати
- відомий
- великий
- більше
- найбільших
- найменш
- залишити
- Залишки
- довжина
- менше
- дозволяє
- використання
- лежить
- життя
- як
- Лінія
- трохи
- місцевий
- локально
- логістика
- довше
- подивитися
- шукати
- ВИГЛЯДИ
- серія
- made
- журнал
- зробити
- Робить
- багато
- карта
- математики
- математичний
- максимальний
- Може..
- значити
- засоби
- Середній
- може бути
- мінімізація
- відсутній
- момент
- гроші
- більше
- рухатися
- багато
- повинен
- а саме
- обов'язково
- сусіди
- мережу
- мереж
- немає
- Номади
- Зверніть увагу..
- зараз
- номер
- об'єкти
- of
- on
- один раз
- ONE
- тільки
- відкрити
- or
- оригінал
- Інше
- інші
- наші
- з
- поза
- над
- пара
- пар
- частина
- приватність
- шлях
- Пол
- частина
- частин
- plato
- Інформація про дані Платона
- PlatoData
- плюс
- точка
- це можливо
- потужний
- Прогнози
- досить
- ймовірно
- Проблема
- виробляти
- властивості
- Доведіть
- доведений
- забезпечує
- головоломка
- Квантамагазин
- питання
- питань
- досягати
- причина
- нещодавно
- називають
- пов'язаний
- Відносини
- відносний
- щодо
- решті
- видаляти
- видалення
- представляє
- вимагати
- вимагається
- Вимога
- обмеження
- Обмеження
- результат
- показувати
- право
- грубо
- Маршрут
- маршрути
- Правило
- то ж
- say
- говорить
- наука
- Вчені
- прокрутки
- секрет
- побачити
- бачив
- сегменти
- вибирає
- окремий
- комплект
- набори
- Форма
- поділ
- Показувати
- простий
- з
- один
- SIX
- Розмір
- трохи відрізняється
- невеликий
- менше
- So
- рішення
- деякі
- що в сім'ї щось
- Source
- площа
- стандартів
- Star
- Зірки
- старт
- Як і раніше
- Стоп
- Стратегія
- сила
- більш сильний
- структура
- Дослідження
- підграф
- такі
- Запропонує
- здивований
- Приймати
- взяття
- terms
- ніж
- Що
- Команда
- Графік
- світ
- їх
- Їх
- самі
- потім
- теорія
- Там.
- Ці
- вони
- річ
- думати
- Мислення
- третій
- це
- хоча?
- думка
- тисячі
- три
- через
- по всьому
- Таким чином
- час
- times
- до
- занадто
- інструмент
- Усього:
- подорожувати
- поїздки
- правда
- намагатися
- повороти
- два
- при
- розуміння
- до
- us
- використання
- використовуваний
- використання
- вразливість
- хотіти
- було
- шлях..
- we
- webp
- були
- Що
- коли
- Чи
- який
- ВООЗ
- чому
- волі
- з
- слова
- Work
- тренування
- працює
- світ
- б
- дав би
- письмовий
- так
- поступаючись
- Ти
- вашу
- зефірнет