«Три дівиці під вікном пряли пізно ввечері.»
Ну як пряли. Чи не пряли, звичайно, а лайкали один на одного. За умовами конкурсу «Міс Салтан» дівиці повинні були вибрати між собою кращу.
«Якийсь дивний конкурс», - турбувалися дівиці. І це було правдою. За правилами конкурсу вага лайка учасника залежав від того, скільки лайків він отримує від інших. Що це означає, - ніхто з дівчат до кінця не розумів.
«Як все складно», - сумували дівчата і підбадьорювали себе піснею «Якби я була царицею».
Незабаром «в світлицю увійшов цар - сторони тієї государ» (показаний на малюнку). «У всі час розмови ...», - ну зрозуміло в загальному.
«Збираємо лайки ніжності - формуємо матрицю суміжності», - бадьоро заримував він.
Дівчата-красуні з іменами Алена, Варвара і Софія збентежилися, але лайки (з балалайки) передали.
Ось що там було:
- Олена отримала 1 лайк від Софії і 2 лайка від Варвари.
- Варвара отримала по лайку від Олени і Софії.
- А Софія отримала 2 лайка від Олени та 1 від Варвари.
Цар взяв лайки, покрутив гайки, постукав по колесах, пошмигал носом, прицмокнув губами, поскріпел зубами, зганяв в палати і оголосив результати.
Найбільшу вагу лайків (7 балів) отримала Софія, але титул «міс Салтан» дістався Олені (15 балів).
вектор потенціалів дорівнює (5, 4, 7), а вектор потоків - (15, 12, 14).
1. Рівняння балансу
В основі нашого світу лежить баланс. Це означає, що якщо в одному місці щось прибуло, то в іншому місці стільки ж вибуло.
Фізики демонструють даний баланс рівнянням безперервності для суцільних і безперервних середовищ. Але в сучасному світі рулять танкові клини дискретні системи - графи.
У графа є вузли, через які тече потік (ну як тече - поштовхами і нерегулярно). Принцип балансу простий - у вузлі графа залишається різниця між тим, скільки з нього витекло і скільки в нього втекла. А куди тече потік з вузла? Правильно - в інші вузли, відповідно втікає потік в вузол теж з інших вузлів.
Запишемо це безліч слів формулою:
Тут позначає кількість вхідного потоку в i -й вузол, - кількість що виходить з вузла потоку, - зміна залишку в вузлі.
Так, залишки в наших гаманцях підпорядковуються даному рівнянню балансу. І весь бухгалтерський облік на ньому заснований, - навіть назви спеціальні придумали: вихідний потік - кредит, що входить - дебет.
Невідомо, хто і чому ввів принцип балансу в природні (фізичні) системи, але в основу штучних систем (облік, рейтинги, карми і ін.) Краще закладати принцип балансу. Якщо світ вижив на балансі, то і у такої системи є шанс.
У багатьох ситуаціях (зокрема з нашим конкурсом оцінок) облік залишку в вузлі не потрібен. Тобто він завжди нульовий - скільки втекла - стільки й витекло. Гра з нульовою вартістю нульовим залишком. Для таких систем рівняння спрощується:
Круто. Але поки малокорисні.
баланс потенціалів
Коли ми говорили про те, що потік може текти з вузла i у вузол j. ми мали на увазі, що є певний зв'язок між даними вузлами. Інакше потоку просто не по чому текти. Можливості підключення вузлів графа зазвичай називають матрицею суміжності (зв'язності). її елементи позначають через. Стосовно до потокам матрицю суміжності також називають матрицею провідності. Її елементи відображають пропускну здатність ребер графа.
Є зв'язок - є потік, немає зв'язку - немає потоку. Логічно припустити, що чим сильніше зв'язок - тим більше потік.
Отже, потік між вузлами пропорційний величині зв'язку вузлів. Але чому дорівнює коефіцієнт пропорційності?
Відповідь буде трохи туманний - потік з вузла пропорційний якомусь потенціалу вузла.
Суть даної відповіді в тому, що вузли мають якесь потенціалом і даний потенціал безпосередньо визначає величину вихідного потоку. Якщо, наприклад, у нас є два вузла, провідність між якими однакова в обох напрямках (), то сумарний потік між вузлами буде визначатися різницею потенціалів даних вузлів. Існування електричних мереж доводить, що це реально працює.
Зв'язок потоку з потенціалами і провідність виражається простою формулою:
Підставляючи (1.3) в рівняння балансу (1.2) отримуємо систему рівнянь для розрахунку потенціалів вузлів:
В даному рівнянні відомими є провідності, а невідомими - потенціали.
Кількість рівнянь в системі дорівнює кількості вузлів графа. Рішення системи балансових рівнянь є прямим завданням розрахунку потенціалів (і потоків) графа.
У рівнянні (1.4) ми використовували поняття загальної провідності вихідних з вузла зв'язків - ступінь вузла:
Рейтинги і самооцінки
«Все це здорово,» - сказали дівчата, позіхаючи. - «Але до чого тут лайки?»
У системах голосування, при яких учасники оцінюють один одного, оцінки беруться з урахуванням ваги голосу кожного учасника. А вага голосу знову ж таки залежить від того, як даного учасника оцінили інші.
Пов'язуємо з потоками. Коли i -й учасник з вагою голосу оцінює j -го учасника з оцінкою (кількістю лайків) то він ділиться з ним своїм потоком. Накопичувати залишки тут ні до чого, тому кожен учасник ділиться з іншими всім, що отримав.
Вага голосу учасника - це потенціал, матриця лайків - це матриця суміжності (зв'язності), а підсумкова оцінка - сумарний отриманий (він же відданий) потік.
Для ранжирування учасників (визначення кращих) нам треба вирішити рівняння балансу (1.4), тобто визначити ваги учасників, які збалансують систему.
2. лапласіан
Коли я був молодим і дурним вперше зіткнувся з рівнянням балансу (1.4), я вже вмів програмувати і знав про цикли. Тому вирішував його як програміст - методом послідовних ітерацій. Задаємо початковий вектор потенціалів, множимо його на матрицю суміжності, ділимо на ступеня вузлів, отримуємо новий вектор потенціалів і т. Д. Як правило, процес сходиться. А згадав я про молодість, прочитавши статтю про цінності п'яниці. яка в загальному і спонукала мене «расчехлить формули».
Пам'ятаю «вау-ефект», коли я дізнався про те, що є й інший спосіб розрахунку потенціалів, про який, мабуть, знали ще наші діди Лаплас і Кірхгоф. Спосіб грунтується на властивостях матриць-лапласіанов. Тут уже недавно згадували Лапласіан в безперервних середовищах. Дискретні Лапласіан не менше цікаві і важливі.
Для того, щоб визначити матрицю Лапласіан по заданій матриці суміжності, використовуємо ведення вище поняття ступеня вузлів. Ступені вузлів розташуємо по діагоналі Лапласіан, а інші елементи візьмемо з матриці суміжності з протилежним знаком. Отриману матрицю називають також матрицею Кірхгофа:
Тут можна подивитися лапласіан від наших лайків
Приймемо, що провідність виходять з вузла i дуг задається в i-му стовпці матриці. Відповідно в i -му рядку матриці - провідність входять в вузол дуг. Тоді сума елементів кожного стовпця Лапласіан дорівнює нулю.
Взагалі кажучи, матриці даного виду утворюють окремий клас, - Лапласіан. Визначник лапласіанов завжди дорівнює нулю, тому, наприклад, для них не існує звичайної оберненої матриці. Але зате є інша (псевдо) зворотна, є і своя одинична матриця. Отримати лапласіан можна не тільки наведеними вище перетворенням. Наприклад, перетворення девіації теж дає лапласіан на виході.
Лапласіан можуть бути симетричними - в них потенціали всіх вузлів рівні між собою - для нашої задачі вони поки що нецікаві.
Матриця Кірхгофа відноситься до класу лапласіанов.
потенціали лапласіанов
У лінійної алгебри є поняття додаткового мінору матриці - це визначник матриці, отриманої з вихідної викреслюванням рядків і стовпців. Додаткові мінори грають велику роль в лапласіанах.
Потенціалом 1-го порядку Лапласіан називається визначник матриці, отриманий викреслюванням з вихідного Лапласіан одного рядка і одного стовпця.
Оскільки ми прийняли, що в наших лапласіанах сума кожного стовпчика нульова, то значення потенціалу визначається тільки викресленої колонкою, - рядок може бути будь-хто. Зручно викреслювати ту ж рядок, що і колонка, - тоді не треба думати про знак визначника.
Отже, якщо позначити через додатковий мінор матриці, то визначення потенціалу Лапласіан можна записати як
Так ось ці потенціали 1-го порядку від матриці Кирхгофа і є шуканим рішенням рівняння (1.4).
Дивно. Не потрібні ніякі цикли, початкові привласнення, твір матриць і ін. Видалив рядок / стовпчик, порахував визначник - отримав відповідь.
Властивості потенціалів 1-го порядку
- Потенціал вузла є сумою творів (кортежів) проводимостей ребер графа за всіма можливими шляхами в даний вузол, виключаючи контури (цикли).
- Кількість множників у творі на 1 менше розмірності (кількості вузлів) графа.
- Потенціал вузла не залежить від провідності виходять з нього дуг.
- Кожен кортеж (шлях) у натуральному вираженні для потенціалу вузла складається з дуг, які виходять з усіх вузлів, крім цього. В одному кортежі немає двох дуг, що виходять з одного вузла, але можуть бути дуги, що входять в один вузол.
- У кожному кортежі (шляху) обов'язково присутній дуга, що входить у вузол (замкнутість).
- У вираженні для потенціалу відсутні кортежі, що містять цикли (контури).
- Кількість кортежів в вираженні для потенціалу визначається відомою формулою Келі, і швидко росте з ростом вузлів графа. Для 4-х вузлів маємо 4 ^ 2 = 16 доданків, для п'яти - 5 ^ 3 = 125 і т. Д.
- У симетричному графі потенціали всіх вузлів рівні - наслідок того, що структура вираження для потенціалів всіх вузлів одна і та ж (різниця лише в напрямку).
Графічна структура потенціалу графа з 4-х вузлів
Для визначення потоку через вузол досить помножити потенціал вузла на його ступінь:
Ми отримали, що хотіли.
Для розрахунку ваги голосу (потенціалу) учасника викреслюємо відповідний рядок і стовпець і вважаємо визначник. Отримуємо 3 потенціалу:
Це вага голосу кожного учасника. Тепер вважаємо потоки і визначаємо, хто скільки голосів набрав:
Олена набрала найбільше голосів.
Як вважати потенціали великих графів
Якщо граф великий (багато вузлів), то вважати вектор потенціалоф через обчислення визначників миноров Лапласіан незручно (затратно). У таких ситуаціях краще використовувати звернення матриці. Алгоритм наступний:
- У матриці Лапласіан замінюємо перший рядок на вектор (1, 0, 0, ...).
- Вважаємо зворотну матрицю від отриманої і знаходимо її детермінант.
- Ділимо значення першої колонки отриманої зворотної матриці на її детермінант. Це і є шуканий вектор потенціалів. У першому рядку - потенціал першого вузла, в другій - другий і т. Д.
- Якщо абсолютне значення потенціалу неважливо, то вважати і ділити на детермінант необов'язково.
Ранжування об'єктів на основі потенціалів і потоків
Що саме має бути підставою для ранжирування, - потенціали або потоки, - вимагає окремого розгляду в кожній задачі, оскільки визначається прикладним аспектом.
результати турнірів
Сучасний і правильний підхід - вважати зважені окуляри, тобто використовувати розрахунок потенціалів і потоків. Ще один плюс - при даній системі практично виключена поділ місць - не треба думати про те, що робити при рівності очок.
Якраз нещодавно в Москві закінчився турнір претендентів (вітаємо Сергія Карякіна з перемогою!), За підсумками якого велика кількість учасників поділило місця (2-3, 4-7). Використовуючи метод потенціалів, спробуємо розібратися, хто ж яке місце зайняв насправді.
Результати турніру - це матриця суміжності графа. У термінах лайків програш учасника - це проставлення лайка переможцю (хоча і звучить трохи незвично). Від того, хто програв до переможця йде потік зважених очок.
А що таке потенціал стосовно гравцям?
Потенціал - це показана учасником сила гри (в даному турнірі). Чим вище потенціал учасника - тим більшу цінність мають окуляри, отримані від нього іншими.
Чи можливо, щоб менш сильний гравець набрав більшу кількість очок, ніж сильніший? Так, таке цілком можливо, хоч і буває не так часто. Наприклад, на згаданому турнірі претендентів сила учасника і набрані ним очки збіглися - ранжування по потенціалом і потокам виявилися еквівалентними.
Для зацікавлених подробицями
Ми унормовували потенціали і потоки так, щоб їх сума дорівнювала 100.
Каруана все-таки другий, а Гирі - 4-й.
потенціали п'яниці
Останній приклад, який ми розглянемо в даній статті - це розрахунок цінності карт в народній грі «П'яниця».
Дякую за даний приклад astgtciv. Без його статті. можливо, не було б і цієї.
Подробиці про постановку задачі є в згаданій статті, - карти б'ють один одного по правилам старшинства, але пи цьому шістка б'є туза.
Дане завдання хороша тим, що значення потенціалів (хм, а потоки тут що значать?) Можуть бути виражені в явному вигляді - нескладними формулами.
Загальний вигляд матриці суміжності відповідає результатам карткових порівнянь - хто кого б'є.
Нумеруя карти від умовного туза до умовної шістці, отримуємо такий вигляд матриці суміжності:
Ключова особливість - в правому нижньому кутку - «шістка б'є туза».
Тоді матриця Кирхгофа матиме вигляд:
Тепер наочно видно, чому потенціал «шістки» дорівнює (n-2)! Тому що викресливши колонку і стовпець шістки, ми отримуємо трикутну матрицю, визначник якої вважається простим множенням елементів головної діагоналі.
Те ж саме справедливо і для туза з тією лише різницею, що у нього в складі множників два рази зустрічається елемент (n-2). Тому відразу видно, що потенціал туза завжди в (n-2) рази більше потенціалу шістки.
Вирази для потенціалів від туза до шістки:
Цікаво, що сума потенціалів всіх карт (крім шістки і туза) дорівнює потенціалу туза:
висновок
Скільки могли намагалися і слухали дівиці оповідь царя Салтана про можливості Лапласіан, та все одно зморив їх міцний сон.
Снилися їм добрі-молодці з великим потенціалом, керуючі великими потоками.
Прийшла і нам пора закруглятися. Використовуйте потенціали!