Сказ царя Салтана о потенциале лапласиана
«Три девицы под окном пряли поздно вечерком.»
Ну как пряли. Не пряли, конечно, а лайкали другна друга. По условиям конкурса «мисс Салтан» девицы должны были выбрать меж собой лучшую.
«Какой-то странный конкурс», — беспокоились девицы. И это было правдой. По правилам конкурса вес лайка участника зависел от того, сколько лайков он получает от других. Что это значит, — никто из девиц до конца не понимал.
«Как все сложно», — тосковали девушки и подбадривали себя песней «Кабы я была царицей».
Вскоре «в светлицу вошел царь — стороны той государь» (показан на рисунке). «Во все время разговора...», — ну понятно в общем.
«Собираем лайки нежности — формируем матрицу смежности», — бодро срифмовал он.
Девицы-красавицы с именами Алена, Варвара и Софья засмущались, но лайки (из балалайки) передали.
Вот что там было:
Царь взял лайки, покрутил гайки, постучал по колесам, пошмыгал носом, причмокнул губами, поскрипел зубами, сгонял в палаты и объявил результаты.
Наибольший вес лайков (7 баллов) получила Софья, но титул «мисс Салтан» достался Алене (15 баллов).
После объявления результатов девицыбросились обратились к царю с просьбой рассказать,- откуда взялись эти странные цифры?
В основе нашего мира лежит баланс. Это означает, что если в одном месте что-то прибыло, то в другом месте столько же убыло.
Физики демонстрируют данный баланс уравнением непрерывности для сплошных и непрерывных сред. Но в современном мире руляттанковые клинья дискретные системы — графы.
У графа есть узлы, через которые течет поток (ну как течет — толчками и нерегулярно). Принцип баланса прост — в узле графа остается разница между тем, сколько из него вытекло и сколько в него втекло. А куда течет поток из узла? Правильно — в другие узлы, соответственно втекает поток в узел тоже из других узлов.
Запишем это множество слов формулой:
Здесь обозначает количество входящего потока в i-й узел, — количество исходящего из узла потока, — изменение остатка в узле.
Да, остатки в наших кошельках подчиняются данному уравнению баланса. И весь бухгалтерский учет на нем основан, — даже названия специальные придумали: исходящий поток — кредит, входящий — дебет.
Неизвестно, кто и почему ввел принцип баланса в естественные (физические) системы, но в основу искусственных систем (учет, рейтинги, кармы и пр.) лучше закладывать принцип баланса. Если мир выжил на балансе, то и у такой системы есть шанс.
В многих ситуациях (в частности с нашим конкурсом оценок) учет остатка в узле не нужен. То есть он всегда нулевой — сколько втекло — столько и вытекло. Игра снулевой стоимостью нулевым остатком. Для таких систем уравнение упрощается:
Круто. Но пока малополезно.
Когда мы говорили о том, что поток может течь из узла i в узел j, мы подразумевали, что есть некая связь между данными узлами. Иначе потоку просто не по чему течь. Связность узлов графа обычно называют матрицей смежности (связности), ее элементы обозначают через . Применительно к потокам матрицу смежности также называют матрицей проводимости. Ее элементы отражают пропускную способность ребер графа.
Есть связь — есть поток, нет связи — нет потока. Логично предположить, что чем сильнее связь — тем больше поток.
Итак, поток между узлами пропорционален величине связи узлов. Но чему равен коэффициент пропорциональности?
Ответ будет немного туманный — поток из узла пропорционален некоему потенциалу узла.
Суть данного ответа в том, что узлы обладают неким потенциалом и данный потенциал непосредственно определяет величину исходящего потока. Если, например, у нас есть два узла, проводимость между которыми одинакова в обоих направлениях ( ), то суммарный поток между узлами будет определяться разностью потенциалов данных узлов. Существование электрических сетей доказывает, что это реально работает.
Связь потока с потенциалами и проводимостью выражается простой формулой:
Подставляя (1.3) в уравнение баланса (1.2) получаем систему уравнений для расчета потенциалов узлов:
В данном уравнении известными являются проводимости, а неизвестными — потенциалы.
Количество уравнений в системе равно количеству узлов графа. Решение системы балансовых уравнений является прямой задачей расчета потенциалов (и потоков) графа.
В уравнении (1.4) мы использовали понятие общей проводимости исходящих из узла связей — степень узла:
«Все это здорово,» — сказали девушки, зевая. — «Но причем тут лайки?»
В системах голосования, при которых участники оценивают друг друга, оценки берутся с учетом веса голоса каждого участника. А вес голоса опять же зависит от того, как данного участника оценили другие.
Связываем с потоками. Когда i-й участник с весом голоса оценивает j-го участника с оценкой (количеством лайков) то он делится с ним своим потоком . Копить остатки тут ни к чему, поэтому каждый участник делится с остальными всем, что получил.
Вес голоса участника — это потенциал , матрица лайков — это матрица смежности (связности), а итоговая оценка — суммарный полученный (он же отданный) поток .
Для ранжирования участников (определения лучших) нам надо решить уравнение баланса (1.4), то есть определить веса участников, которые сбалансируют систему.
Когда ябыл молодым и глупым впервые столкнулся с уравнением баланса (1.4), я уже умел программировать и знал про циклы. Поэтому решал его как программист — методом последовательных итераций. Задаем начальный вектор потенциалов, умножаем его на матрицу смежности, делим на степени узлов, получаем новый вектор потенциалов и т. д. Как правило, процесс сходится. А вспомнил я про молодость, прочитав статью о ценностях пьяницы, которая в общем и побудила меня «расчехлить формулы».
Помню «вау-эффект», когда я узнал о том, что есть и другой способ расчета потенциалов, о котором, видимо, знали ещенаши деды Лаплас и Кирхгоф. Способ основывается на свойствах матриц-лапласианов. Тут уже недавно вспоминали лапласианы в непрерывных средах. Дискретные лапласианы не менее интересны и важны.
Для того, чтобы определить матрицу лапласиана по заданной матрице смежности, используем веденное выше понятие степени узлов. Степени узлов расположим по диагонали лапласиана, а остальные элементы возьмем из матрицы смежности с обратным знаком. Получившуюся матрицу называют также матрицей Кирхгофа:
Примем, что проводимость исходящих из узла i дуг задается в i-м столбце матрицы. Соответственно в i-й строке матрицы – проводимость входящих в узел дуг. Тогда сумма элементов каждого столбца лапласиана равна нулю.
Вообще говоря, матрицы данного вида образуют отдельный класс, — лапласианы. Определитель лапласианов всегда равен нулю, поэтому, например, для них не существует обычной обратной матрицы. Но зато есть другая (псевдо)обратная, есть и своя единичная матрица. Получить лапласиан можно не только приведенным выше преобразованием. Например, преобразование девиации тоже дает лапласиан на выходе.
Лапласианы могут быть симметричными — в них потенциалы всех узлов равны между собой — для нашей задачи они пока неинтересны.
Матрица Кирхгофа относится к классу лапласианов.
В линейной алгебре есть понятие дополнительного минора (кофактора) матрицы — это определитель матрицы, полученной из исходной вычеркиванием строк и столбцов (с учетом знака). Кофакторы играют большую роль в лапласианах.
Потенциалом 1-го порядка лапласиана называется определитель матрицы, полученный вычеркиванием из исходного лапласиана одной строки и одного столбца.
Поскольку мы приняли, что в наших лапласианах сумма каждого столбца нулевая, то значение потенциала определяется только вычеркнутой колонкой, — строка может быть любой. Удобно вычеркивать ту же строку, что и колонка, — тогда не надо думать о знаке определителя.
Итак, если обозначить через дополнительный минор матрицы, то определение потенциала лапласиана можно записать как
Так вот эти потенциалы 1-го порядка от матрицы Кирхгофа и являются искомым решением уравнения (1.4).
Удивительно. Не нужны никакие циклы, начальные присваивания, произведение матриц и пр. Удалил строку/колонку, посчитал определитель — получил ответ.
Для определения потока через узел достаточно умножить потенциал узла на его степень:
Мы получили, что хотели.
Если граф большой (много узлов), то считать вектор потенциалов через вычисление определителей миноров лапласиана неудобно (затратно). В таких ситуациях лучше использовать обращение матрицы. Алгоритм следующий:
По итогам нашего примера получилось так, что наибольший вес голоса получила Софья, но больше всего баллов набрала Алена.
Это означает, что авторитетные и избранные — это не одно и тоже.
Что именно должно служить основанием для ранжирования, — потенциалы или потоки,- требует отдельного рассмотрения в каждой задаче, поскольку определяется прикладным аспектом.
Рассмотрим применение системы ранжирования применительно к определениям итогов шахматного турнира. Справедлива ли нынешняя система определения победителя простой суммой очков? На наш взгляд, она имеет лишь одно достоинство — простота. Но в век смартфонов кого волнует простота?
Несправедливо то, что выигрыш сильного по сути приравнивается в «простой системе» выигрышу у слабого.
Современный и правильный подход — считать взвешенные очки, то есть использовать расчет потенциалов и потоков. Еще один плюс — при данной системе практически исключена дележка мест — не надо думать о том, что делать при равенстве очков.
Как раз недавно в Москве закончился турнир претендентов (поздравляем Сергея Карякина с победой!), по итогам которого большое количество участников поделило места (2-3, 4-7). Используя метод потенциалов, попробуем разобраться, кто же какое место занял на самом деле.
Результаты турнира — это матрица смежности графа. В терминах лайков проигрыш участника — это проставление лайка победителю (хотя и звучит немного непривычно). От проигравшего к победителю идет поток взвешенных очков.
А что такое потенциал применительно к игрокам?
Потенциал — это показанная участником сила игры (в данном турнире). Чем выше потенциал участника — тем большую ценность имеют очки, полученные от него другими.
Возможно ли, чтобы менее сильный игрок набрал большее количество очков, чем более сильный? Да, такое вполне возможно, хоть и бывает не так часто. Например, на упомянутом турнире претендентов сила участника и набранные им очки совпали — ранжирование по потенциалам и потокам оказались эквивалентными.
Последний пример, который мы рассмотрим в данной статье — это расчет ценности карт в народной игре «Пьяница».
Спасибо за данный пример astgtciv. Без его статьи, возможно, не было бы и этой.
Подробности о постановке задачи есть в упомянутой статье, — карты бьют друг друга по правилам старшинства, но при этом шестерка бьет туза.
Данная задача хороша тем, что значения потенциалов (хм, а потоки тут что означают?) могут быть выражены в явном виде — несложными формулами.
Общий вид матрицы смежности соответствует результатам карточных сравнений — кто кого бьет.
Нумеруя карты от условного туза к условной шестерке, получаем следующий вид матрицы смежности:
Ключевая особенность — в левом нижнем (и/или правом верхнем) углу — «шестерка бьет туза».
Тогда матрица Кирхгофа будет иметь вид:
Теперь наглядно видно, почему потенциал «шестерки» равен (n-2)! Потому что вычеркнув колонку и строку, соответствующие «шестерке» (это крайние ряды справа и снизу), мы получаем треугольную матрицу, определитель которой считается простым умножением элементов главной диагонали.
То же самое справедливо и для туза (1-я строка и колонка) с той лишь разницей, что у него в составе множителей два раза встречается элемент (n-2). Поэтому сразу видно, что потенциал туза всегда в (n-2) раза больше потенциала шестерки.
Сколько могли старались и слушали девицы сказ царя Салтана про возможности лапласиана, да все равно сморил их крепкий сон.
Снились им добры-молодцы с большим потенциалом, управляющие крупными потоками.
Пришла и нам пора закругляться. Используйте потенциалы!
Ну как пряли. Не пряли, конечно, а лайкали друг
«Какой-то странный конкурс», — беспокоились девицы. И это было правдой. По правилам конкурса вес лайка участника зависел от того, сколько лайков он получает от других. Что это значит, — никто из девиц до конца не понимал.
«Как все сложно», — тосковали девушки и подбадривали себя песней «Кабы я была царицей».
Вскоре «в светлицу вошел царь — стороны той государь» (показан на рисунке). «Во все время разговора...», — ну понятно в общем.
«Собираем лайки нежности — формируем матрицу смежности», — бодро срифмовал он.
Девицы-красавицы с именами Алена, Варвара и Софья засмущались, но лайки (из балалайки) передали.
Вот что там было:
- Алена получила 1 лайк от Софьи и 2 лайка от Варвары.
- Варвара получила по лайку от Алены и Софьи.
- А Софья получила 2 лайка от Алены и 1 от Варвары.
Царь взял лайки, покрутил гайки, постучал по колесам, пошмыгал носом, причмокнул губами, поскрипел зубами, сгонял в палаты и объявил результаты.
Наибольший вес лайков (7 баллов) получила Софья, но титул «мисс Салтан» достался Алене (15 баллов).
Подробнее о матрице лайков
Для матрицы
вектор потенциалов равен (5, 4, 7), а вектор потоков — (15, 12, 14).
вектор потенциалов равен (5, 4, 7), а вектор потоков — (15, 12, 14).
После объявления результатов девицы
1. Уравнение баланса
В основе нашего мира лежит баланс. Это означает, что если в одном месте что-то прибыло, то в другом месте столько же убыло.
Физики демонстрируют данный баланс уравнением непрерывности для сплошных и непрерывных сред. Но в современном мире рулят
У графа есть узлы, через которые течет поток (ну как течет — толчками и нерегулярно). Принцип баланса прост — в узле графа остается разница между тем, сколько из него вытекло и сколько в него втекло. А куда течет поток из узла? Правильно — в другие узлы, соответственно втекает поток в узел тоже из других узлов.
Запишем это множество слов формулой:
Здесь
Да, остатки в наших кошельках подчиняются данному уравнению баланса. И весь бухгалтерский учет на нем основан, — даже названия специальные придумали: исходящий поток — кредит, входящий — дебет.
Неизвестно, кто и почему ввел принцип баланса в естественные (физические) системы, но в основу искусственных систем (учет, рейтинги, кармы и пр.) лучше закладывать принцип баланса. Если мир выжил на балансе, то и у такой системы есть шанс.
В многих ситуациях (в частности с нашим конкурсом оценок) учет остатка в узле не нужен. То есть он всегда нулевой — сколько втекло — столько и вытекло. Игра с
Круто. Но пока малополезно.
Баланс потенциалов
Когда мы говорили о том, что поток может течь из узла i в узел j, мы подразумевали, что есть некая связь между данными узлами. Иначе потоку просто не по чему течь. Связность узлов графа обычно называют матрицей смежности (связности), ее элементы обозначают через
Есть связь — есть поток, нет связи — нет потока. Логично предположить, что чем сильнее связь — тем больше поток.
Итак, поток между узлами пропорционален величине связи узлов. Но чему равен коэффициент пропорциональности?
Ответ будет немного туманный — поток из узла пропорционален некоему потенциалу узла.
Суть данного ответа в том, что узлы обладают неким потенциалом
Связь потока с потенциалами и проводимостью выражается простой формулой:
Подставляя (1.3) в уравнение баланса (1.2) получаем систему уравнений для расчета потенциалов узлов:
В данном уравнении известными являются проводимости, а неизвестными — потенциалы.
Количество уравнений в системе равно количеству узлов графа. Решение системы балансовых уравнений является прямой задачей расчета потенциалов (и потоков) графа.
В уравнении (1.4) мы использовали понятие общей проводимости исходящих из узла связей — степень узла:
Рейтинги и самооценки
«Все это здорово,» — сказали девушки, зевая. — «Но причем тут лайки?»
В системах голосования, при которых участники оценивают друг друга, оценки берутся с учетом веса голоса каждого участника. А вес голоса опять же зависит от того, как данного участника оценили другие.
Связываем с потоками. Когда i-й участник с весом голоса
Вес голоса участника — это потенциал
Для ранжирования участников (определения лучших) нам надо решить уравнение баланса (1.4), то есть определить веса участников, которые сбалансируют систему.
2. Лапласианы
Когда я
Помню «вау-эффект», когда я узнал о том, что есть и другой способ расчета потенциалов, о котором, видимо, знали еще
Для того, чтобы определить матрицу лапласиана по заданной матрице смежности, используем веденное выше понятие степени узлов. Степени узлов расположим по диагонали лапласиана, а остальные элементы возьмем из матрицы смежности с обратным знаком. Получившуюся матрицу называют также матрицей Кирхгофа:
Тут можно посмотреть лапласиан от наших лайков
Примем, что проводимость исходящих из узла 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-й.
Сергей Карякин | Хикару Накамура | Аниш Гири | Виши Ананд | Веселин Топалов | Левон Аронян | Фабиано Каруана | Петр Свидлер | |
U | 17,8 | 11,4 | 12,5 | 13,7 | 6,4 | 12,0 | 13,8 | 12,4 |
J | 14,5 | 11,8 | 13,0 | 13,2 | 9,0 | 12,4 | 13,3 | 12,8 |
М | 1 | 7 | 4 | 3 | 8 | 6 | 2 | 5 |
Каруана все-таки второй, а Гири — 4-й.
Потенциалы пьяницы
Последний пример, который мы рассмотрим в данной статье — это расчет ценности карт в народной игре «Пьяница».
Спасибо за данный пример astgtciv. Без его статьи, возможно, не было бы и этой.
Подробности о постановке задачи есть в упомянутой статье, — карты бьют друг друга по правилам старшинства, но при этом шестерка бьет туза.
Данная задача хороша тем, что значения потенциалов (хм, а потоки тут что означают?) могут быть выражены в явном виде — несложными формулами.
Общий вид матрицы смежности соответствует результатам карточных сравнений — кто кого бьет.
Нумеруя карты от условного туза к условной шестерке, получаем следующий вид матрицы смежности:
Ключевая особенность — в левом нижнем (и/или правом верхнем) углу — «шестерка бьет туза».
Тогда матрица Кирхгофа будет иметь вид:
Теперь наглядно видно, почему потенциал «шестерки» равен (n-2)! Потому что вычеркнув колонку и строку, соответствующие «шестерке» (это крайние ряды справа и снизу), мы получаем треугольную матрицу, определитель которой считается простым умножением элементов главной диагонали.
То же самое справедливо и для туза (1-я строка и колонка) с той лишь разницей, что у него в составе множителей два раза встречается элемент (n-2). Поэтому сразу видно, что потенциал туза всегда в (n-2) раза больше потенциала шестерки.
Сводка формул
Выражения для потенциалов от туза до шестерки:
Интересно, что сумма потенциалов всех карт (кроме шестерки и туза) равна потенциалу туза:
Интересно, что сумма потенциалов всех карт (кроме шестерки и туза) равна потенциалу туза:
Заключение
Сколько могли старались и слушали девицы сказ царя Салтана про возможности лапласиана, да все равно сморил их крепкий сон.
Снились им добры-молодцы с большим потенциалом, управляющие крупными потоками.
Пришла и нам пора закругляться. Используйте потенциалы!