Grafic semnat - Signed graph

Image
Există opt moduri în care semnele pot fi atribuite laturilor unui triunghi. Un număr impar de semne negative face un triunghi dezechilibrat, conform teoriei lui Fritz Heider .

În zona teoriei graficelor în matematică , un grafic semnat este un grafic în care fiecare margine are un semn pozitiv sau negativ.

Un grafic semnat este echilibrat dacă produsul semnelor de margine din jurul fiecărui ciclu este pozitiv. Trei întrebări fundamentale despre un grafic semnat sunt: ​​Este echilibrat? Care este cea mai mare dimensiune a unei margini echilibrate setate în ea? Care este cel mai mic număr de vârfuri care trebuie șterse pentru a-l echilibra? Prima întrebare este ușor de rezolvat rapid; al doilea și al treilea sunt intratabil din punct de vedere al calculului (din punct de vedere tehnic, sunt NP-hard ).

Numele „grafic semnat” și noțiunea de echilibru au apărut pentru prima dată într-o lucrare matematică a lui Frank Harary în 1953. Dénes Kőnig studiase deja noțiuni echivalente în 1936 sub o altă terminologie, dar fără să recunoască relevanța grupului de semne. La Centrul pentru dinamica grupurilor de la Universitatea din Michigan , Dorwin Cartwright și Harary au generalizat teoria psihologică a echilibrului lui Fritz Heider în triunghiurile sentimentelor către o teorie psihologică a echilibrului în grafice semnate.

Graficele semnate au fost redescoperite de multe ori, deoarece apar în mod natural în multe domenii fără legătură. De exemplu, ele permit descrierea și analiza geometriei subseturilor sistemelor radiculare clasice . Ele apar în teoria topologică a graficelor și teoria grupurilor . Acestea sunt un context natural pentru întrebări despre ciclurile impare și pare din grafice. Ele apar în calculul stării de bază de energie în non-feromagnetic modelul Ising ; pentru aceasta trebuie să găsiți o margine echilibrată cea mai mare setată în Σ. Acestea au fost aplicate clasificării datelor în gruparea corelației .

Exemple

  • Complet Graficul semnat pe n noduri cu bucle, notate cu ± K n o , are toate pozitive posibile și marginea negativă , inclusiv bucle negativ, dar nu și bucle pozitive. Marginile sale corespund rădăcinilor sistemului radicular C n ; coloana unei margini din matricea de incidență (vezi mai jos) este vectorul care reprezintă rădăcina.
  • Complet Graficul semnat cu jumătate de margini, ± K n “, este de ± K n cu o jumatate de margine la fiecare nod. Marginile sale corespund rădăcinilor sistemului radicular B n , jumătăți de margini corespunzătoare vectorilor de bază unitară.
  • Complet link - ul Graficul semnat , ± K n , este aceeași , dar fără bucle. Marginile sale corespund rădăcinilor sistemului radicular D n .
  • Un grafic semnat pozitiv are numai margini pozitive. Dacă graficul de bază este G , semnarea toate pozitive este scris + G .
  • Un grafic cu semn negativ are numai margini negative. Este echilibrat dacă și numai dacă este bipartit, deoarece un cerc este pozitiv dacă și numai dacă are lungime egală. Un grafic all-negativ cu grafic care stau la baza G este scris - G .
  • Un grafic complet semnat are ca grafic subiacent G graficul complet obișnuit K n . Poate avea semne. Graficele complete semnate sunt echivalente cu două grafice , care au valoare în teoria grupurilor finite . Un grafic cu două poate fi definit ca clasa seturilor de vârfuri de triunghiuri negative (având un număr impar de muchii negative) într-un grafic complet semnat.

Matricea de adiacență

Matricea de adiacenta a unui grafic Σ semnat n noduri este n x n matricea A (Σ). Are un rând și o coloană pentru fiecare vârf. Intrarea a vw în rândul v și coloana w este numărul de margini vw pozitive minus numărul de margini vw negative . Pe diagonală, un vv = 0 dacă nu există bucle sau jumătăți de margini; definiția corectă atunci când există astfel de margini depinde de circumstanțe.

Orientare

Un grafic semnat este orientat atunci când fiecărui capăt al fiecărei muchii i se dă o direcție, astfel încât într-o margine pozitivă capetele sunt ambele direcționate de la un punct final la celălalt, iar într-o margine negativă ambele capete sunt direcționate spre exterior, către propriile lor vârfuri. , sau ambele sunt îndreptate spre interior, departe de vârfurile lor. Astfel, un grafic orientat semnat este același cu un grafic bidirectat . (Este foarte diferit de un digraf semnat .)

Matricea de incidență

O matrice de incidență a unui grafic semnat cu n vârfuri și m margini este o matrice n × m , cu un rând pentru fiecare vârf și o coloană pentru fiecare margine. Se obține prin orientarea graficului semnat în orice mod. Atunci intrarea sa η ij este +1 dacă muchia j este orientată în vârful i , -1 dacă muchia j este orientată în afara vârfului i și 0 dacă vârful i și marginea j nu sunt incidente . Această regulă se aplică unui link, a cărui coloană va avea două intrări diferite de zero cu valoarea absolută 1, o jumătate de margine, a cărei coloană are o singură intrare diferită de zero +1 sau −1 și o margine liberă, a cărei coloană are doar zero. Coloana unei bucle este însă zero dacă bucla este pozitivă și dacă bucla este negativă are intrarea ± 2 în rândul corespunzător vârfului său incident.

Orice două matrice de incidență sunt corelate prin negarea unor subseturi de coloane. Astfel, pentru cele mai multe scopuri face nici o diferență pe care orientarea le folosim pentru a defini matricea de incidență, și putem vorbi de matricea de incidență Σ fără a avea grija exact care unul este.

Negarea unui rând al matricei de incidență corespunde schimbării vârfului corespunzător.

Comutare

Comutarea unui vârf în Σ înseamnă negarea semnelor tuturor marginilor incidente acelui vârf. Comutarea unui set de vârfuri înseamnă negarea tuturor muchiilor care au un capăt în acel set și un capăt în setul complementar. Comutarea unei serii de vârfuri, odată fiecare, este la fel ca schimbarea simultană a întregului set.

Comutarea graficelor semnate ( comutarea semnată ) este generalizată din Seidel (1976), unde a fost aplicată graficelor ( comutarea graficului ), într-un mod echivalent cu comutarea graficelor complete semnate.

Comutarea echivalenței înseamnă că două grafice sunt legate prin comutare, iar o clasă de echivalență a graficelor semnate sub comutare se numește clasă de comutare . Uneori acești termeni se aplică echivalenței graficelor semnate sub combinația de comutare și izomorfism , mai ales atunci când graficele sunt nemarcate; dar pentru a distinge cele două concepte, echivalența combinată poate fi numită izomorfism de comutare și o clasă de echivalență sub izomorfism de comutare poate fi numită clasă de izomorfism de comutare .

Comutarea unui set de vârfuri afectează matricea de adiacență prin negarea rândurilor și coloanelor vârfurilor comutate. Afectează matricea de incidență prin negarea rândurilor vârfurilor comutate.

Teorema fundamentală

Semnul unei căi este produsul semnelor marginilor sale. Astfel, o cale este pozitivă numai dacă există un număr par de muchii negative în ea (unde zero este par). În teoria echilibrului matematic al lui Frank Harary , un grafic semnat este echilibrat atunci când fiecare ciclu este pozitiv. El demonstrează că un grafic semnat este echilibrat atunci când (1) pentru fiecare pereche de noduri, toate căile dintre ele au același semn sau (2) partiția graficului într-o pereche de subgrafe, fiecare constând din margini pozitive, dar conectate prin negative margini. Teorema a fost publicată de Harary în 1953. Generalizează teorema că un grafic obișnuit (nesemnat) este bipartit dacă și numai dacă fiecare ciclu are lungime egală.

O dovadă simplă folosește metoda de comutare. Pentru a demonstra teorema lui Harary, se arată prin inducție că Σ poate fi schimbat pentru a fi tot pozitiv dacă și numai dacă este echilibrat.

O teoremă mai slabă, dar cu o dovadă mai simplă, este că dacă fiecare 3-ciclu dintr-un grafic complet semnat este pozitiv, atunci graficul este echilibrat. Pentru dovada, alege un nod arbitrar n și așezați - l și toate acele noduri care sunt legate de n printr - o margine pozitivă într - un grup, numit A , și toate cele legate de n printr - o margine în cealaltă negativă, numită B . Deoarece acesta este un grafic complet, fiecare două noduri din A trebuie să fie prieteni și fiecare două noduri din B trebuie să fie prieteni, altfel ar exista un ciclu 3 care era dezechilibrat. (Deoarece acesta este un grafic complet, orice margine negativă ar provoca un ciclu neechilibrat cu 3 cicluri.) La fel, toate marginile negative trebuie să se deplaseze între cele două grupuri.

Frustrare

Acordați fiecărui vârf o valoare de +1 sau −1; numim asta o stare de Σ. O margine se numește satisfăcută dacă este pozitivă și ambele puncte finale au aceeași valoare, sau este negativă, iar punctele finale au valori opuse. O margine care nu este satisfăcută se numește frustrată . Cel mai mic număr de margini frustrate din toate stările se numește indicele frustrării (sau indicele liniei de echilibru ) al lui Σ. Găsirea indicelui frustrării este o problemă dificilă pentru NP . Aref și colab. sugerează modele de programare binare care sunt capabile să calculeze indicele de frustrare al graficelor cu până la 10 5 muchii într-un timp rezonabil. Se poate vedea complexitatea NP-hard observând că indicele de frustrare al unui grafic semnat negativ este echivalent cu problema de tăiere maximă în teoria graficelor, care este NP-hard. Motivul echivalenței este că indicele de frustrare este egal cu cel mai mic număr de muchii a căror negare (sau, în mod echivalent, ștergere; o teoremă a lui Harary) face Σ echilibrată. (Acest lucru poate fi dovedit cu ușurință prin comutare.)

Indicele de frustrare este important într - un model de ochelari de spin ACESTEA , modelul mixt Ising . În acest model, graficul semnat este fix. O stare constă în acordarea unei „rotiri”, fie „sus”, fie „jos”, fiecărui vârf. Ne gândim la rotirea în sus ca +1 și rotirea în jos ca −1. Astfel, fiecare stat are un număr de margini frustrate. Energia unei stări este mai mare atunci când are margini mai frustrate, deci o stare de bază este o stare cu cea mai puțină energie frustrată. Astfel, pentru a găsi energia de bază a lui Σ trebuie să găsiți indicele frustrării.

Teoria matroida

Există două matroide asociate cu un grafic semnat, numit matroid cu grafic semnat (denumit și matroid cadru sau uneori matroid de polarizare ) și matroidul lift , ambele generalizând ciclul matroid al unui grafic. Sunt cazuri speciale ale acelorași matroide ale unui grafic părtinitor .

Matroide cadru (sau semnat-grafic matroide ) M ( G ) are de la sol sa stabilit set margine E . Un set de margini este independent dacă fiecare componentă nu conține fie cercuri, fie doar un cerc, ceea ce este negativ. (În teoria matroidului o jumătate de margine acționează exact ca o buclă negativă.) Un circuit al matroidului este fie un cerc pozitiv, fie o pereche de cercuri negative împreună cu o cale simplă de legătură, astfel încât cele două cercuri sunt fie disjuncte (atunci calea de conectare are un capăt comun cu fiecare cerc și este altfel disjunctă de ambele) sau împarte doar un singur vârf comun (în acest caz calea de conectare este acel vârf unic). Rangul unui set de margini S este n - b , unde n este numărul de vârfuri ale lui G și b este numărul de componente echilibrate ale lui S , numărând vârfurile izolate ca componente echilibrate. Acest matroid este coloana matroidă a matricei de incidență a graficului semnat. De aceea descrie dependențele liniare ale rădăcinilor unui sistem radicular clasic.

Lift extins matroide L 0 ( G ) are de la sol sa stabilit setul E 0 unirea set margine E cu un punct în plus , pe care notam e 0 . Ridicare matroid L ( G ) este elevatorul extins matroide limitată la E . Punctul suplimentar acționează exact ca o buclă negativă, deci descriem doar matroidul de ridicare. Un set de margini este independent dacă nu conține nici cercuri, fie doar un cerc, ceea ce este negativ. (Aceasta este aceeași regulă care se aplică separat fiecărei componente din matroidul cu semn grafic.) Un circuit matroid este fie un cerc pozitiv, fie o pereche de cercuri negative care sunt fie disjuncte, fie au doar un vârf comun. Rangul unui set de margini S este n - c + ε, unde c este numărul de componente ale lui S , numărând vârfurile izolate, iar ε este 0 dacă S este echilibrat și 1 dacă nu este.

Alte tipuri de „grafic semnat”

Uneori semnele sunt considerate a fi +1 și -1. Aceasta este doar o diferență de notație, dacă semnele sunt încă multiplicate în jurul unui cerc și semnul produsului este important. Cu toate acestea, există alte două moduri de tratare a etichetelor de margine care nu se încadrează în teoria graficelor semnate.

Termenul de grafic semnat se aplică ocazional graficelor în care fiecare margine are o greutate, w ( e ) = +1 sau −1. Acestea nu sunt același tip de grafic semnat; sunt grafice ponderate cu un set de greutate restrâns. Diferența este că greutățile sunt adăugate, nu multiplicate. Problemele și metodele sunt complet diferite.

Numele se aplică și graficelor în care semnele funcționează ca culori pe margini. Semnificația culorii este că determină diferite greutăți aplicate marginii și nu că semnul său este intrinsec semnificativ. Acesta este cazul în teoria nodurilor , unde singura semnificație a semnelor este că acestea pot fi schimbate de grupul cu două elemente, dar nu există nicio diferență intrinsecă între pozitiv și negativ. Matroidul unui grafic colorat de semn este ciclul matroid al graficului subiacent; nu este cadrul sau rama matroidă a graficului semnat. Etichetele semnelor, în loc să schimbe matroidul, devin semne pe elementele matroidului.

În acest articol discutăm doar teoria graficelor semnate în sens strict. Pentru grafice colorate în semne, consultați matroidele colorate .

Digraf semnat

Un digraf semnat este un grafic direcționat cu arcuri semnate. Digrafele semnate sunt mult mai complicate decât graficele semnate, deoarece doar semnele ciclurilor direcționate sunt semnificative. De exemplu, există mai multe definiții ale echilibrului, fiecare dintre acestea fiind greu de caracterizat, în contrast puternic cu situația graficelor semnate nedirecționate.

Digrafele semnate nu trebuie confundate cu graficele semnate orientate . Acestea din urmă sunt grafice bidirecționate, nu grafice direcționate (cu excepția cazului banal al tuturor semnelor pozitive).

Semne de vârf

Un grafic semnat de vârf , uneori numit grafic marcat , este un grafic ale cărui vârfuri sunt date cu semne. Un cerc este numit consistent (dar acest lucru nu are legătură cu consistența logică) sau armonios dacă produsul semnelor sale de vârf este pozitiv și inconsecvent sau inarmonic dacă produsul este negativ. Nu există o caracterizare simplă a graficelor armonioase semnate pe vârf, analog teoremei echilibrului lui Harary; în schimb, caracterizarea a fost o problemă dificilă, cel mai bine rezolvată (și mai general) de Joglekar, Shah și Diwan (2012).

Este adesea ușor să adăugați semne de margine la teoria semnelor de vârf fără schimbări majore; astfel, multe rezultate pentru graficele semnate la vârf (sau „grafice semnate marcate”) se extind în mod natural la graficele semnate la vârf și la margine. Acest lucru este valabil mai ales pentru caracterizarea armoniei de către Joglekar, Shah și Diwan (2012).

Diferența dintre un grafic marcat semnat și un grafic semnat cu o funcție de stare (ca în § Frustrare ) este că semnele de vârf din prima fac parte din structura esențială, în timp ce o funcție de stare este o funcție variabilă pe graficul semnat.

Rețineți că termenul „grafic marcat” este utilizat pe scară largă în plasele Petri într-un sens complet diferit; vezi articolul despre graficele marcate .

Colorare

Ca și în cazul graficelor nesemnate , există o noțiune de colorare a graficelor semnate . În cazul în care o colorare a unui grafic este o mapare de la vârful setat la numerele naturale, o colorare a unui grafic semnat este o mapare de la vârful setat la numerele întregi. Constrângerile asupra coloranților corespunzători provin de la marginile graficului semnat. Numerele întregi atribuite la două vârfuri trebuie să fie distincte dacă sunt conectate printr-o margine pozitivă. Etichetele de pe vârfurile adiacente nu trebuie să fie inverse aditive dacă vârfurile sunt conectate printr-o margine negativă. Nu poate exista o colorare adecvată a unui grafic semnat cu o buclă pozitivă.

Când se restricționează etichetele de vârf la setul de numere întregi cu magnitudine cel mult un număr natural k , setul de coloranți corespunzători ai unui grafic semnat este finit. Relația dintre numărul de astfel de coloranți corespunzători și k este un polinom în k . Acest lucru este analog cu polinomul cromatic al graficelor nesemnate.

Aplicații

Psihologie sociala

În psihologia socială , graficele semnate au fost folosite pentru a modela situații sociale, cu margini pozitive reprezentând prietenii și margini negative dușmanii dintre noduri, care reprezintă oameni. Apoi, de exemplu, un ciclu pozitiv de 3 este fie trei prieteni comuni, fie doi prieteni cu un inamic comun; în timp ce un ciclu negativ de 3 este fie trei dușmani comuni, fie doi dușmani care împărtășesc un prieten comun. Conform teoriei echilibrului , ciclurile pozitive sunt echilibrate și se presupune că sunt situații sociale stabile, în timp ce ciclurile negative sunt dezechilibrate și se presupune că sunt instabile. Potrivit teoriei, în cazul a trei inamici comuni, acest lucru se datorează faptului că împărtășirea unui dușman comun poate determina doi dintre inamici să devină prieteni . În cazul în care doi inamici împărtășesc un prieten, prietenul împărtășit este probabil să aleagă unul peste celălalt și să transforme una dintre prietenii sale în inamic.

Antal, Krapivsky și Reder consideră dinamica socială ca schimbarea semnului pe marginea unui grafic semnat. Relațiile sociale cu prietenii anteriori ai unui cuplu divorțat sunt folosite pentru a ilustra evoluția unui grafic semnat în societate. O altă ilustrație descrie schimbarea alianțelor internaționale dintre puterile europene din deceniile anterioare primului război mondial . Ei iau în considerare dinamica triadei locale și dinamica constrânsă a triadei, în care în ultimul caz o schimbare a relației se face numai atunci când numărul total de triade dezechilibrate este redus. Simularea a presupus un grafic complet cu relații aleatorii având o triază dezechilibrată aleatorie selectată pentru transformare. Evoluția graficului semnat cu N noduri în cadrul acestui proces este studiată și simulată pentru a descrie densitatea staționară a legăturilor prietenoase.

Teoria echilibrului a fost puternic contestată, în special în aplicarea sa la sisteme mari, pe baza teoriei că relațiile de prietenie leagă o societate împreună, în timp ce o societate împărțită în două tabere de dușmani ar fi extrem de instabilă. Studiile experimentale au furnizat, de asemenea, doar o confirmare slabă a previziunilor teoriei echilibrului structural.

Rotiți ochelarii

În fizică, graficele semnate sunt un context natural pentru modelul general, nonferromagnetic Ising , care se aplică studiului ochelarilor .

Sisteme complexe

Image
Un digraf cu trei variabile semnat reprezentând un sistem trofic simplu

Folosind o metodă analitică dezvoltată inițial în biologia populației și ecologie, dar utilizată acum în multe discipline științifice, digrafele semnate și-au găsit aplicația în raționamentul despre comportamentul sistemelor cauzale complexe. Astfel de analize răspund la întrebări despre feedback-ul la niveluri date ale sistemului și despre direcția răspunsurilor variabile date de o perturbare a unui sistem la unul sau mai multe puncte, corelații variabile date de astfel de perturbații, distribuția varianței în sistem și sensibilitatea sau insensibilitatea anumitor variabile la perturbațiile sistemului.

Clusterizarea datelor

Gruparea de corelație caută gruparea naturală a datelor prin similaritate. Punctele de date sunt reprezentate ca vârfurile unui grafic, cu o margine pozitivă care unește elemente similare și o margine negativă care unește elemente diferite.

Neuroștiințe

Creierul poate fi considerat ca un grafic semnat în care sincronia și antisincronia dintre tiparele de activitate din regiunile creierului determină muchii pozitive și negative. În acest sens, stabilitatea și energia rețelei cerebrale pot fi explorate.

Generalizări

Un grafic semnat este un tip special de grafic câștig , în care grupul câștig are ordinea 2. Perechea ( G , B ( Σ )) determinată de un grafic semnat Σ este un tip special de grafic părtinitor .

Note

Referințe