ラプラシアンの可能性に関するサルタン王の物語

「窓の下の3人の女の子は夕方遅くに回転しました。」







さて、スピン方法。 もちろん彼らは回転しませんでしたが、お互いが好きでした。 ミスサルタンコンテストの条件によると、女の子は自分の中で最高のものを選ばなければなりませんでした。



「ある種の奇妙なコンテスト」と女の子たちは心配していました。 そして、それは本当でした。 コンテストのルールによると、参加者のいいねの重みは、他の人から好きなものをいくつ受け取るかによって異なります。 これはどういう意味ですか-最後まで女の子の誰も理解していませんでした。

「それがどれほど複雑か」と、少女たちは「もし私が女王だったら」という歌で憧れ、励ましました。



すぐに「王様が部屋に入った-その主権の側」（図に示されている）。 「会話を通して...」、まあ、当然のことながら。

「優しさのハスキーを集めます-隣接行列を形成します」と彼は活発に言いました。

アレナ、バーバラ、ソフィアという名前の美しい少女たちは恥ずかしかったが、ハスキー（バラライカから）は伝染した。



そこにあったものは次のとおりです。

• アレナはソフィアから1匹、バーバラから2匹を受け取りました。
• バーバラは、アレナとソフィアから同類を受けました。
• そして、ソフィアはアリーナから2つのいいね！とバーバラから1つのいいね！

王はハスキーを取り、ナッツをねじり、車輪を軽くたたき、鼻を突っ込み、唇を叩き、歯を噛み、病棟に追い込み、結果を発表しました。



ソフィアは同類の最大の重み（7ポイント）を獲得しましたが、アレナ（15ポイント）はタイトル「ミスサルタン」を獲得しました。





結果が発表された後、女の子は急いで 、皇帝に彼らに言うように頼みました-これらの奇妙な数字はどこから来たのですか？

1.バランス方程式

私たちの世界の中心はバランスです。 これは、ある場所に何かが到着した場合、別の場所で同じくらい消えたということです。



物理学者は、連続および連続媒体の連続性の方程式によってこのバランスを実証します。 しかし、現代の世界では、 タンクウェッジは個別のシステム、つまりグラフによって駆動されます。



グラフには、ストリームが流れるノードがあります（まあ、どのように流れるか-ショックがあり不規則に）。 バランスの原則は単純です-グラフノードでは、そこから流出した量と流入した量の差が残ります。 また、ノードからストリームはどこに流れますか？ 正しく-他のノードへ;したがって、ストリームは他のノードからもノードに流れます。



次の式でこの単語のセットを記述します。







ここに i番目のノードへの入力量を示し、 -ノードフローからの発信数 -ノード内の残りの変更。



はい、ウォレットの残高はこのバランスの式に従います。 そして、すべてのアカウンティングはそれに基づいています-彼らは特別な名前を思いつきました：発信フロー-クレジット、着信フロー-デビット。



誰が、なぜ自然の（物理）システムにバランスの原理を導入したかはわかりませんが、人工システム（アカウンティング、評価、カルマなど）の基礎にバランスの原理を置く方が良いです。 世界がバランスよく生き残っていれば、そのようなシステムにはチャンスがあります。



多くの場合（特に評価競争の場合）、ノード内の残りの部分を考慮する必要はありません。 つまり、それは常にゼロです-どれだけ流入したか-流出しました。 バランスがゼロのゼロコストゲーム。 そのようなシステムの場合、方程式は単純化されます。







かっこいい。 しかし、これまでのところほとんど役に立たない。

潜在的なバランス

ストリームがノードiからノードjに流れることができるという事実について話したとき、これらのノード間に何らかの接続があることを暗示しました。 それ以外の場合、ストリームは流れません。 グラフのノードの接続性は通常、隣接行列と呼ばれ、その要素は 。 フローの場合、隣接行列は導電率行列とも呼ばれます。 その要素は、グラフのエッジの帯域幅を反映しています。



接続があります-フローがあり、接続がありません-フローがありません。 接続が強いほど、フローが大きくなると仮定するのは論理的です。

したがって、ノード間のフローは接続ノードの大きさに比例します。 しかし、比例係数は何に等しいのでしょうか？



答えは少し霧になります-ノードからのフローはノードの電位に比例します 。

この答えの本質は、ノードに潜在的な可能性があることです そして、この可能性は、発信ストリームの大きさを直接決定します。 たとえば、2つのノードがあり、その間の伝導率が両方向で同じ場合（ ）、ノード間の合計フローは、これらのノードの電位差によって決定されます。 電気ネットワークの存在は、それが本当に機能することを証明しています。



流れと電位および伝導率との関係は、簡単な式で表されます。







バランス方程式（1.2）に（1.3）を代入すると、ノードのポテンシャルを計算するための方程式系が得られます。







この方程式では、導電率は既知であり、電位は不明です。

システム内の方程式の数は、グラフ内のノードの数に等しくなります。 平衡方程式系の解は、グラフのポテンシャル（およびフロー）を計算する直接のタスクです。



方程式（1.4）では、ノードから生じる結合の一般的な伝導率の概念、つまりノードの次数を使用しました。

評価と自尊心

「これはすべて素晴らしい」と少女たちはあくびをした。 -「しかし、どこが好きですか？」



参加者が互いに評価する投票システムでは、各参加者の投票の重みに基づいて評価が行われます。 また、声の重みは、他の人がこの参加者をどのように評価したかに依存します。



ストリームに接続します。 投票の重みを持つi番目の参加者 評価でj番目の参加者を推定します（いいねの数による） 彼は彼と彼の流れを共有します 。 残り物を保存する必要はないので、各参加者は受け取ったすべてを他の参加者と共有します。



参加者の体重は潜在的です 、同様のマトリックスは隣接（接続性）マトリックスであり、最終グレードは受信した（また与えられた）ストリームの合計です 。



参加者をランク付けする（最良を決定する）には、バランス式（1.4）を解く必要があります。つまり、システムのバランスをとる参加者の重みを決定します。

2.ラプラシアン

バランスの方程式（1.4）に出会ったのは初めてで愚かだったとき、私はすでにプログラミングの方法とサイクルについて知っていました。 したがって、私はプログラマーとしてそれを解決しました-逐次反復の方法によって。 ポテンシャルの初期ベクトルを設定し、隣接行列を乗算し、ノードの次数で除算し、ポテンシャルの新しいベクトルを取得します。原則として、プロセスは収束します。 そして、酔っぱらいの価値に関する記事を読んだ後、私は若者について思い出しました。



私たちの祖父であるラプラスとキルヒホフも知っていたように、ポテンシャルを計算する別の方法があることを知ったとき、「ワウ効果」を覚えています。 この方法は、ラプラシアン行列の特性に基づいています。 ここで、連続メディアのラプラシアンは最近思い出した 。 離散ラプラシアンも同様に興味深く、重要です。



与えられた隣接行列によってラプラシアン行列を決定するために、上記のノードの次数の概念を使用します。 ノードの次数をラプラシアンの対角線に沿って配置し、反対の符号を持つ隣接行列から残りの要素を取得します。 結果の行列は、キルヒホッフ行列とも呼ばれます。











ノードiから発生するアークの伝導率は、マトリックスのi番目の列で指定されると仮定します。 したがって、マトリックスのi番目の行には、ノードに入るアークの導電率があります。 その場合、ラプラシアンの各列の要素の合計はゼロになります。



一般的に言えば、この形式の行列は別のクラス、 ラプラシアンを形成します。 ラプラシアンの行列式は常にゼロに等しいため、たとえば、それらの行列には通常の逆行列はありません。 しかし、別の（疑似）逆行列があり、独自の単位行列もあります。 ラプラシアンは、上記の変換だけでなく取得できます。 たとえば、偏差変換では、出口でラプラシアンも得られます。



ラプラシアンは対称にすることができます-それらでは、すべてのノードのポテンシャルは互いに等しくなります-私たちの問題のために、それらはまだ興味深くありません。



キルヒホッフ行列は、ラプラシアンのクラスに属します。

ラプラシアンポテンシャル

線形代数には、行列の追加のマイナー（補因子）の概念があります -これは、行と列を削除することにより（符号を考慮して）元から得られる行列の行列式です。 コファクターはラプラシアンで大きな役割を果たします。



ラプラシアンの1次ポテンシャルは、元のラプラシアンから1行1列削除した行列の行列式です。



ラプラシアンでは各列の合計がゼロであることを受け入れたため、電位の値は、取り消し線の列によってのみ決定されます-行は任意です。 列と同じ行を消すと便利です-行列式の符号について考える必要はありません。



したがって、 行列の追加マイナー、ラプラシアンのポテンシャルの定義は次のように記述できます。







したがって、キルヒホッフ行列のこれらの一次ポテンシャルは、式（1.4）の望ましい解です。

すごい サイクル、初期割り当て、行列の積などは必要ありません行/列を削除し、行列式を数えました-回答を受け取りました。









ノードを通過するフローを決定するには、ノードのポテンシャルに次数を掛けるだけで十分です。







欲しいものが手に入りました。

大きなグラフのポテンシャルを数える方法

グラフが大きい（ノードが多い）場合、ラプラシアンマイナーの行列式を計算して潜在的なポテンシャルベクトルを考慮するのは不便です（コストがかかります）。 このような状況では、マトリックス反転を使用することをお勧めします。 アルゴリズムは次のとおりです。

• ラプラシアン行列では、最初の行をベクトル（1、0、0、...）に置き換えます。
• 得られた行列の逆行列を考慮し、その行列式を見つけます。
• 得られた逆行列の最初の列の値を行列式で除算します。 これが望ましいポテンシャルのベクトルです。 1行目-最初のノードの電位、2行目-2番目など
• ポテンシャルの絶対値が重要でない場合は、行列式でカウントして除算する必要はありません。

ポテンシャルとフローに基づいたオブジェクトのランキング

この例の結果によると、ソフィアが最も多くの体重を獲得しましたが、アランは最も多くのポイントを獲得しました。

これは、権威と選挙が同じものではないことを意味します。



ランク付け、ポテンシャルまたはフローの基礎として正確に機能するものは、適用される側面によって決定されるため、各タスクで個別に考慮する必要があります。

トーナメント結果

チェストーナメントの結果の決定に関連するランキングシステムの適用を検討してください。 勝者を決定するための現在のシステムは単純なポイントですか？ 私たちの意見では、単純さという利点が1つだけあります。 しかし、スマートフォンの時代に、誰がシンプルさを気にしますか？

「単純なシステム」において、強い者の利益が弱い者の利益と本質的に等しいことは不公平です。



近代的で正しいアプローチは、加重ポイントを考慮することです。つまり、ポテンシャルとフローの計算を使用します。 別のプラス-このシステムでは、場所の分割は実質的に除外されます-ポイントが等しい場合に何をすべきかを考える必要はありません。



つい最近、応募者のトーナメントはモスクワで終了しました （セルゲイカルヤキンの勝利を祝福します！）。その結果、多数の参加者が場所を共有しました（2-3、4-7）。 可能性のある方法を使用して、実際に誰がどの場所を取ったかを把握してみましょう。



トーナメント結果は、グラフの隣接行列です。 いいねという点では、メンバーを失うことは勝者をつけるようなものです（少し変わったように聞こえますが）。 敗者から勝者まで、加重ポイントのストリームがあります。



そして、プレーヤーの可能性は何ですか？

可能性は、参加者（このトーナメントで）によって示されるゲームの強さです。 参加者の潜在能力が高いほど、他の人が彼から受け取ったポイントの価値が高くなります。

弱いプレイヤーが強いプレイヤーよりも多くのポイントを獲得することは可能ですか？ はい、これは非常に可能ですが、それほど頻繁には発生しません。 たとえば、前述の応募者のトーナメントでは、参加者の強さと彼が獲得し​​たポイントが一致しました。ポテンシャルとフローによるランキングは同等であることが判明しました。

酔っぱらいの可能性

この記事で検討する最後の例は、民俗ゲーム「The Drunkard」のカードの価値の計算です。

このastgtcivの例をありがとう。 彼の記事がなければ、おそらくこれは起こらなかっただろう。



問題の声明の詳細は言及された記事にあります-カードは年功序列に従って互いに打ち合いますが、同時に6つはエースを打ちます。

この問題は、潜在的な値（うーん、フラックスとはどういう意味ですか）が明確に表現できるという点で優れています-単純な式で。



隣接行列の一般的なビューは、カード比較の結果に対応しています-誰が誰を倒します。

条件付きエースから条件付き6までカードに番号を付けると、次の形式の隣接行列が得られます。







主な機能-左下（および/または右上）の隅にある-「6がエースを打ちます」。

キルヒホッフ行列は次の形式になります。







これで、「6」の可能性が（n-2）である理由が明確にわかります。 「6」に対応する列と行（これらは右と下の極端な行です）を消したため、行列式は主対角の要素の単純な乗算と見なされる三角行列を取得します。

同じことがエース（1行目と1列目）にも当てはまりますが、唯一の違いは、彼が乗数に要素（n-2）を2回持っていることです。 したがって、エースのポテンシャルは常に6のポテンシャルよりも（n-2）倍大きいことがすぐにわかります。

おわりに

少女たちはラプラシアンの可能性についてサルタンの物語を試聴しましたが、それでも彼らの良い睡眠は彼らを台無しにしました。

彼は、大きな流れを管理し、大きな可能性を持つ良き仲間を夢見ていました。



今こそ私たちがやってくる時です。 ポテンシャルを使用してください！