"Trei fete sub fereastra s-au întors noaptea târziu."
Ei bine, cum s-au întors. Nu se roteau, desigur, dar erau leneși unul altuia. Conform termenului concursului Miss Saltan, fetele trebuiau să aleagă cele mai bune dintre ele.
- O competiție ciudată, fetele erau îngrijorate. Și era adevărat. Conform regulilor concursului, ponderea laicului participantului depindea de cât de mulți îi plac de ceilalți. Ce înseamnă - nici una din fete nu a înțeles pe deplin.
"Cât de dificil este totul", fetele au dorit și s-au încurajat cu piesa "Dacă aș fi o regină".
Curând "regele a intrat în palat - partea acelui suveran" (prezentat în imagine). "În întreaga conversație ..." - ei bine, este de înțeles în general.
"Îi colectăm plăcerile de tandrețe - formăm matricea de contiguitate", a râs bucuros.
Fetele de frumusețe cu numele Alain, Barbara și Sophia erau stânjenite, dar husky (din balalaika) au fost transferate.
Iată ce a fost acolo:
- Alena a primit 1 de la Sophia și 2 de la Varvara.
- Varvara a primit un laic de la Alena și Sophia.
- Și Sophia a primit 2 husky de la Alena și 1 de la Varvara.
Țarul a luat o haină, a răsuci nuca, a bătut pe roți, a mușcat nasul, ia smuls buzele, a scrâșnit dinții, a intrat în camere și a anunțat rezultatele.
Cea mai mare pondere a câinilor (7 puncte) a fost primită de Sofia, dar titlul "Miss Saltan" a fost acordat lui Alena (15 puncte).
vectorul potențial este (5, 4, 7), iar vectorul de flux este (15, 12, 14).
1. Ecuația de echilibru
În inima lumii noastre este echilibrul. Aceasta înseamnă că, dacă ceva a sosit într-un singur loc, atunci într-un alt loc a scăzut la fel.
Fizicienii demonstrează acest echilibru prin ecuația continuității pentru mass-media continuă și continuă. Dar în lumea modernă, panourile rezervoarelor sunt controlate de sisteme discrete - grafice.
Graficul are noduri prin care fluxul curge (bine, deoarece curge - prin ciocniri și neregulate). Principiul echilibrului este simplu - în nodul graficului există o diferență între cât de mult a curgat și cât de mult a intrat în el. Și unde curge fluxul din nod? Corect - în alte noduri, respectiv, fluxul curge și în nod, din alte noduri.
Noi scriem acest set de cuvinte după formula:
Aici se denumește cantitatea fluxului de intrare la nodul i, - cantitatea de ieșire din nodul fluxului, - schimbarea restului în nod.
Da, rămășițele din portofele noastre sunt supuse ecuației de echilibru. Și toate contabilitatea se bazează pe aceasta, - chiar și numele speciale au venit: fluxul de ieșire este creditul, intrarea este debitul.
Nu se știe cine și de ce a introdus principiul echilibrului în sistemele fizice (fizice), dar baza sistemelor artificiale (contabilitate, evaluări, karma, etc.) este mai bine să stabilească principiul echilibrului. Dacă lumea a supraviețuit în echilibru, atunci un astfel de sistem are o șansă.
În multe situații (în special, cu concursul nostru de evaluare), nu este necesar să se țină cont de restul din nod. Asta este, este întotdeauna zero - cât de mult a intrat - atât de mult a izbucnit. Un joc cu valoare zero cu sold zero. Pentru astfel de sisteme ecuația este simplificată:
Se răcește. Dar până acum nu este de folos.
Balanța potențială
Când am vorbit despre faptul că un flux poate curge de la nodul i la nodul j. am vrut să spunem că există o legătură între aceste noduri. Altfel, fluxul pur și simplu nu are nimic de curgere. Conectivitatea nodurilor unui grafic este numită, de obicei, matricea adjacency. elementele sale sunt notate cu. În cazul fluxurilor, matricea de contiguitate este numită și matricea de conductivitate. Elementele sale reflectă lățimea de bandă a marginilor graficului.
Există o conexiune - există un flux, nu există legătură - nu există nici un flux. Este logic să presupunem că, cu cât conexiunea este mai puternică, cu atât este mai mare fluxul.
Deci, fluxul dintre noduri este proporțional cu valoarea conexiunii nodurilor. Dar care este coeficientul de proporționalitate egal cu?
Răspunsul este puțin cam neclar - fluxul din nod este proporțional cu un potențial al nodului.
Esența acestui răspuns este că nodurile au un anumit potențial și acest potențial determină în mod direct cantitatea fluxului de ieșire. Dacă, de exemplu, avem două noduri a căror conductivitate este aceeași în ambele direcții (), atunci fluxul total dintre noduri va fi determinat de diferența de potențial dintre aceste noduri. Existența rețelelor electrice demonstrează că funcționează cu adevărat.
Legătura dintre debit și potențial și conductivitate este exprimată printr-o formulă simplă:
Substituind (1.3) în ecuația de echilibru (1.2), obținem un sistem de ecuații pentru calculul potențialilor nodurilor:
Conductivitatea este cunoscută în această ecuație, iar necunoscutele sunt potențialele.
Numărul de ecuații din sistem este egal cu numărul de noduri din grafic. Soluția sistemului de ecuații de echilibru este o sarcină directă de a calcula potențialele (și fluxurile) graficului.
În ecuația (1.4) am folosit noțiunea de conductivitate generală a legăturilor de ieșire de la nod - gradul nodului:
Evaluările și auto-evaluările
- Totul e minunat, spuse fetele, căscând. - Dar unde îi plac?
În sistemele de vot, în care participanții se evaluează, scorurile sunt luate ținând cont de greutatea fiecărui participant. Și greutatea vocii depinde din nou de modul în care participantul a fost evaluat de alții.
Ne conectăm cu fluxurile. Atunci când participantul al II-lea cântărește pe cel de-al J-lea cu ratingul (numărul de plăceri), el împărtășește fluxul cu el. Nu este nevoie să salvați rămășițele aici, astfel încât fiecare participant să împărtășească cu ceilalți ceea ce a primit.
Greutatea vocii participantului este potențialul, matricea preferată - aceasta este matricea contiguității (conectivitate), iar scorul final este fluxul total primit (același dat).
Pentru a clasifica participanții (determinați cei mai buni), trebuie să rezolvăm ecuația de echilibru (1.4), adică să determinăm ponderile participanților care echilibrează sistemul.
2. Laplacienii
Când eram tânără și proastă pentru prima dată când am întâlnit ecuația de echilibru (1.4), știam deja cum să programez și știu despre cicluri. De aceea am rezolvat-o ca programator - prin metoda iterațiilor succesive. Definim vectorul inițial al potențialelor, îl înmulțim cu matricea de adjacență, împărțim prin puterile nodurilor, obținem un nou vector al potențialelor, etc. Ca regulă, procesul converge. Și mi-am amintit despre tineret, după ce am citit un articol despre valorile unui bețiv. care, în general, m-au determinat să "descifrez formule".
Îmi amintesc de "efectul wow" când am aflat că există un alt mod de a calcula potențialele pe care, aparent, și bunicii noștri Laplace și Kirchhoff știau de asemenea. Metoda se bazează pe proprietățile matricelor Laplacian. Aici am amintit recent Laplacienii în medii continue. Laplacienii discrete nu sunt mai puțin interesanți și importanți.
Pentru a determina matricea Laplacian dintr-o matrice de adjuvant dată, vom folosi noțiunea de grad de noduri de mai sus. Gradele de noduri sunt aranjate de-a lungul diagonalei Laplacianului, iar restul elementelor sunt luate din matricea de adjacență cu semnul opus. Matricea rezultată este numită și matricea Kirchhoff:
Aici puteți vedea Laplacianul din placerea noastră
Presupunem că conductivitatea arcurilor care apar din nodul i este dată în coloana i a matricei. În consecință, rândul i al matricei este conductivitatea arcurilor care intră în nod. Atunci suma elementelor din fiecare coloană a Laplacianului este zero.
În general, matricile de acest tip formează o clasă separată, Laplacienii. Determinantul Laplacianului este întotdeauna zero, prin urmare, de exemplu, nu există o matrice inversă obișnuită pentru ele. Dar există un alt (pseudo) invers, există, de asemenea, o unitate matrice. Laplacianul poate fi obținut nu numai prin transformarea de mai sus. De exemplu, transformarea deviației dă și Laplacianului o ieșire.
Laplacienii pot fi simetrici - în ei potențialul tuturor nodurilor este egal cu celălalt - pentru sarcina noastră ei sunt încă neinteresanți.
Matricea Kirchhoff aparține clasei Laplacienilor.
Laplacian potențiale
În algebra liniară, există noțiunea unei minore adiționale a matricei - acesta este factorul determinant al matricei obținute din ștergerea inițială a rândurilor și coloanelor. Minorii adiționali joacă un rol important în Laplacieni.
Potențialul primului ordin al Laplacianului este determinantul matricei, obținut prin ștergerea unei linii și a unei coloane din Laplacianul original.
Deoarece am presupus că la Laplacienii noștri suma fiecărei coloane este zero, atunci valoarea potențialului este determinată numai de coloana traversată, - șirul poate fi orice. Este convenabil să ștergeți aceeași linie ca și coloana - atunci nu vă gândiți la semnul determinantului.
Astfel, dacă denotăm printr-o minoritate suplimentară a matricei, atunci definiția potențialului Laplacian poate fi scrisă ca
Deci, aceste potențiale de ordinul întâi din matricea Kirchhoff sunt soluția dorită a ecuației (1.4).
Este uimitor. Nu sunt necesare cicluri, sarcini inițiale, produse de matrice, etc. Am șters rândul / coloana, am numărat determinantul, am primit răspunsul.
Proprietățile potențialelor de ordinul I
- Potențialul nodului este suma produselor (tuple) ale conductivității marginilor graficelor de-a lungul tuturor căilor posibile către nodul dat, excluzând contururile (cicluri).
- Numărul de factori din produs este 1 mai mic decât dimensiunea (numărul de noduri) din grafic.
- Potențialul nodului nu depinde de conductivitățile arcurilor care decurg din el.
- Fiecare nod (cale) în expresia potențialului nodului constă din arce care provin din toate nodurile, cu excepția celui dat. Într-o singură tuplă, nu există două arce provenite de la același nod, dar pot exista arce care intră într-un singur nod.
- În fiecare trupă (cale) trebuie să existe un arc care intră în nod (închis).
- În expresia potențialului, nu există tupluri care să conțină cicluri (contururi).
- Numărul de tupluri din expresia potențialului este determinat de formula bine cunoscută a lui Cayley și crește rapid cu nodurile crescânde ale graficului. Pentru 4 noduri avem 4 ^ 2 = 16 termeni, pentru cinci - 5 ^ 3 = 125, etc.
- Într-un grafic simetric, potențialul tuturor nodurilor este egal ca urmare a faptului că structura expresiei pentru potențialele tuturor nodurilor este aceeași (diferența este numai în direcție).
Structura grafică a potențialului grafic din 4 noduri
Pentru a determina fluxul printr-un nod, este suficient să multiplicăm potențialul nodului după gradul său:
Am obținut ceea ce ne-am dorit.
Pentru a calcula greutatea vocii participantului (potențial), ștergeți rândul și coloana corespunzătoare și luați în considerare determinantul. Avem 3 potențiale:
Aceasta este greutatea fiecărui participant. Acum, luați în considerare fluxurile și determinați cine a înscris câte voturi:
Alena a câștigat cele mai multe voturi.
Cum se calculează potențialele grafice mari
Dacă graficul este mare (multe noduri), atunci este inconvenient (costisitor) să se calculeze vectorul de potențial-potențial prin calculul determinanților minori Laplacian. În astfel de situații, este mai bine să utilizați inversarea matricei. Algoritmul este după cum urmează:
- În matricea Laplacian, înlocuim primul rând cu vectorul (1, 0, 0, ...).
- Considerăm matricea inversă a matricei obținute și găsim determinantul acesteia.
- Împărțim valorile primei coloane a matricei inverse obținute cu determinantul acesteia. Acesta este vectorul necesar al potențialelor. Prima linie conține potențialul primului nod, a doua linie prezintă al doilea nod și așa mai departe.
- Dacă valoarea absolută a potențialului nu este importantă, atunci nu este necesar să se ia în considerare și să se împartă cu determinantul.
Clasificarea obiectelor bazate pe potențiale și fluxuri
Ce ar trebui să servească drept bază pentru clasificare - potențiale sau fluxuri - necesită o analiză separată în fiecare sarcină, deoarece este determinată de un aspect aplicat.
Rezultatele turneului
Abordarea modernă și corectă este aceea de a lua puncte ponderate, adică de a utiliza calculul potențialelor și fluxurilor. Un alt plus - cu acest sistem este aproape exclusă divizarea locurilor - nu trebuie să ne gândim ce să facem cu egalitatea de puncte.
Doar la Moscova s-a încheiat turneul candidaților (îi felicităm pe Serghei Karyakin pentru victorie!). În urma rezultatelor, un număr mare de participanți au împărțit locurile (2-3, 4-7). Folosind metoda potențialului, să încercăm să ne dăm seama cine a luat locul.
Rezultatele turneului sunt matricea adjacency a graficului. În ceea ce privește plăcile, pierderea participantului este aceea de a stabili laika câștigătorului (deși pare puțin neobișnuit). De la învins la câștigător există un flux de puncte cântărite.
Și care este potențialul jucătorilor?
Potențialul este puterea jocului prezentată de participant (în acest turneu). Cu cât este mai mare potențialul participantului, cu atât mai valoroase sunt punctele primite de la el.
Este posibil ca un jucător mai puțin puternic să înscrie mai multe puncte decât cel mai puternic? Da, acest lucru este posibil, deși nu se întâmplă atât de des. De exemplu, la turneul de mai sus al solicitanților, puterea și punctele punctate ale participantului coincid - clasarea pe potențiale și fluxuri sa dovedit a fi echivalentă.
Pentru cei interesați de detalii
Am normalizat potențialele și fluxurile, astfel încât suma lor să fie egală cu 100.
Caruana este încă al doilea, iar Giri este al patrulea.
Potențialii unui bețiv
Ultimul exemplu pe care îl vom lua în considerare în acest articol este calculul valorii cărților din jocul popular "Drunkard".
Vă mulțumim pentru acest exemplu astgtciv. Fără articolul lui. poate că nici nu ar fi acesta.
Detalii despre afirmația problemei figurează în articolul menționat; - cărțile se bateau reciproc în conformitate cu regulile vechimii, însă șase dintre ei au bătut asul.
Această problemă este bună deoarece valorile potențialelor (hm și ce înseamnă acest lucru?) Pot fi exprimate în formă explicită - simple formule.
Vederea generală a matricei de adjudecare corespunde rezultatelor comparațiilor cărților - cine lovește cine.
Cardurile de numerotare de la un ason condițional la un condițional șase, obținem următoarea formă a matricii de adjudecție:
Caracteristica cheie - în colțul din dreapta jos - "cele șase bate un as."
Apoi matricea Kirchhoff va avea forma:
Acum, puteți vedea clar de ce potențialul "șase" este (n-2)! Deoarece am șters coloana și coloana celor șase, obținem o matrice triunghiulară, a cărei determinant este considerată o multiplicare simplă a elementelor diagonalei principale.
Același lucru este valabil și pentru un as, singura diferență fiind faptul că are un element (n-2) de două ori în compoziția factorilor. Prin urmare, este imediat evident că potențialul ace este întotdeauna (n-2) ori mai mare decât potențialul celor șase.
Expresii pentru potențialele de la Ace la Șase:
Este interesant faptul că suma potențialelor tuturor cărților (cu excepția celor șase și ase) este egală cu potențialul unui as:
concluzie
Câți ar fi putut încerca și au ascultat fetele din povestile regelui Saltan despre posibilitatea Laplacianului, dar totuși au dormit bine.
Ei au visat de oameni buni cu mare potențial, gestionând fluxuri mari.
A venit și este timpul pentru noi să rotunjim. Utilizați potențialul!
Trimiteți-le prietenilor: