Signerad graf - Signed graph

Image
Det finns åtta sätt att tecken kan tilldelas sidorna av en triangel. Ett udda antal negativa tecken gör en obalanserad triangel, enligt Fritz Heiders teori.

Inom området grafteori i matematik är en signerad graf en graf där varje kant har ett positivt eller negativt tecken.

En signerad graf balanseras om produkten av kantskyltar runt varje cykel är positiv. Tre grundläggande frågor om ett signerat diagram är: Är det balanserat? Vad är den största storleken på en balanserad kant i den? Vad är det minsta antalet hörn som måste raderas för att få det balanserat? Den första frågan är lätt att lösa snabbt; den andra och den tredje är beräkningsmässigt svåråtkomliga (tekniskt sett är de NP-hårda ).

Namnet "signerad graf" och begreppet balans uppträdde först i en matematisk uppsats av Frank Harary 1953. Dénes Kőnig hade redan studerat likvärdiga föreställningar 1936 under en annan terminologi men utan att erkänna teckengruppens relevans. Vid Centrum för Gruppdynamik vid University of Michigan , Dorwin Cartwright och Harary generaliserad Fritz Heider är psykologisk teori om balans i trianglar av känslor till en psykologisk teori om balans i signerad grafer.

Signerade grafer har återupptäckts många gånger eftersom de kommer upp naturligt i många orelaterade områden. Till exempel gör de det möjligt för en att beskriva och analysera geometrin för delmängder i de klassiska rotsystemen . De förekommer i topologisk grafteori och gruppteori . De är ett naturligt sammanhang för frågor om udda och jämna cykler i grafer. De förekommer i beräkningen av markenergin i den icke-ferromagnetiska Ising-modellen ; för detta måste man hitta en största balanserad kant i Σ. De har tillämpats på dataklassificering i korrelationskluster .

Exempel

  • Den fullständiga signerade grafen på n hörn med slingor, betecknade med ± K n o , har alla möjliga positiva och negativa kanter inklusive negativa slingor, men inga positiva slingor. Dess kanter motsvarar rötterna i rotsystemet C n ; kolumnen i en kant i incidensmatrisen (se nedan) är vektorn som representerar roten.
  • Den fullständiga signerade grafen med halvkanter, ± K n ', är ± K n med en halvkant vid varje hörn. Dess kanter motsvarar rötterna i rotsystemet B n , halvkanter motsvarande enhetsbaserade vektorer.
  • Den fullständiga signerade länkgrafen , ± K n , är densamma men utan slingor. Dess kanter motsvarar rötterna i rotsystemet D n .
  • En helt positiv signerad graf har bara positiva kanter. Om den underliggande grafen är G är all-positiva signering skriven + G .
  • Ett helt negativt signerat diagram har bara negativa kanter. Det är balanserat om och bara om det är tvåpartigt eftersom en cirkel är positiv om och bara om den har jämn längd. En helt negativ graf med underliggande graf G skrivs- G .
  • Ett signerat komplett diagram har som underliggande graf G det vanliga kompletta diagrammet K n . Det kan ha några tecken. Signerade fullständiga grafer motsvarar tvågrafer , som är av värde i ändlig gruppteori. En tvågraf kan definieras som klassen av toppunktsuppsättningar av negativa trianglar (med ett udda antal negativa kanter) i ett signerat komplett diagram.

Adjacency matris

Den grannmatris av ett undertecknat graf Σ på n vertex är en n × n matris A (Σ). Den har en rad och kolumn för varje toppunkt. Posten a vw i rad v och kolumn w är antalet positiva vw -kanter minus antalet negativa vw -kanter. På diagonal, a vv = 0 om det inte finns slingor eller halvkanter; rätt definition när sådana kanter finns beror på omständigheterna.

Orientering

En signerad graf orienteras när varje ände av varje kant ges en riktning, så att i en positiv kant är ändarna båda riktade från en ändpunkt till den andra, och i en negativ kant är båda ändarna riktade utåt, till sina egna hörn , eller båda är riktade inåt, bort från sina hörn. Således är en orienterad signerad graf densamma som en dubbelriktad graf . (Det skiljer sig mycket från en signerad digraph .)

Incidensmatris

En förekomstmatris av en signerad graf med n hörn och m kanter är en n × m matris, med en rad för varje hörn och en kolumn för varje kant. Den erhålls genom att orientera den signerade grafen på något sätt. Därefter är dess inmatning η ij +1 om kant j är orienterad in i hörnet i , −1 om kant j är orienterad från hörn i , och 0 om hörn i och kant j inte är infallande . Denna regel gäller för en länk, vars kolumn kommer att ha två icke-nollposter med absolut värde 1, en halvkant, vars kolumn har en enkel post på noll +1 eller −1, och en lös kant, vars kolumn bara har nollor. Kolumnen i en slinga är emellertid helt noll om slingan är positiv, och om slingan är negativ har den post ± 2 i raden som motsvarar dess infallande hörn.

Alla två incidensmatriser är relaterade genom att negera någon delmängd av kolumnerna. Således för de flesta ändamål spelar det ingen roll vilken orientering vi använder för att definiera förekomsten matrisen och vi kan tala om det förekomsten matris av Σ utan att behöva oroa exakt vilken det är.

Att negera en rad av incidensmatrisen motsvarar att byta motsvarande toppunkt.

Växlande

Att byta in en hörn Σ innebär att negationen tecknar på alla kanter som infaller till den punkten. Att byta en uppsättning hörn innebär att man negerar alla kanter som har en ände i den uppsättningen och ena änden i den kompletterande uppsättningen. Att byta en serie hörn, en gång vardera, är samma sak som att byta hela uppsättningen på en gång.

Växling av signerade grafer ( signerad omkoppling ) generaliseras från Seidel (1976), där den applicerades på grafer ( grafväxling ), på ett sätt som motsvarar byte av signerade fullständiga grafer.

Växlingsekvivalens innebär att två grafer är relaterade genom att byta, och en ekvivalensklass av signerade grafer under växling kallas en växlingsklass . Ibland tillämpas dessa termer på likvärdighet mellan signerade grafer under kombinationen av växling och isomorfism , särskilt när graferna är omärkta; men för att skilja de två begreppen kan den kombinerade ekvivalensen kallas för att byta isomorfism och en ekvivalensklass under omkoppling av isomorfism kan kallas för en växling isomorfismklass .

Att byta en uppsättning hörn påverkar angränsningsmatrisen genom att negera raderna och kolumnerna i de växlade hörnen. Det påverkar incidensmatrisen genom att negera raderna med de växlade hörnen.

Grundläggande sats

Tecknet på en stig är produkten av tecknen på dess kanter. Således är en väg endast positiv om det finns ett jämnt antal negativa kanter i den (där noll är jämn). I den matematiska balansteori av Frank Harary är ett signerat graf balanserad när varje cykel är positivt. Han bevisar att en undertecknad graf är balanserad när (1) för varje par noder, alla vägar mellan dem har samma tecken, eller (2) diagrampartitionerna i ett par subgrafer, var och en bestående av positiva kanter, men anslutna med negativa kanter. Satsen publicerades av Harary 1953. Det generaliserar teoremet att en vanlig (osignerad) graf är tvåpartig om och bara om varje cykel har jämn längd.

Ett enkelt bevis använder växlingsmetoden. För att bevisa Hararys sats visar man genom induktion att Σ kan ändras till att vara allt positivt om och bara om det är balanserat.

En svagare sats, men med ett enklare bevis, är att om varje 3-cykel i ett signerat fullständigt diagram är positivt, så är grafen balanserad. För bevis, plocka en godtycklig nod n och placera den och alla de noder som är kopplade till n av en positiv kant i en grupp, som kallas A , och alla de som är kopplade till n av en negativ kant i den andra, som kallas B . Eftersom detta är en komplett graf måste varannan nod i A vara vänner och varannan nod i B måste vara vän, annars skulle det finnas en 3-cykel som var obalanserad. (Eftersom detta är ett komplett diagram, skulle en negativ kant orsaka en obalanserad 3-cykel.) På samma sätt måste alla negativa kanter gå mellan de två grupperna.

Frustration

Ge varje hörn ett värde på +1 eller −1; vi kallar detta ett tillstånd av Σ. En kant kallas nöjd om den är positiv och båda slutpunkterna har samma värde, eller om det är negativt och slutpunkterna har motsatta värden. En kant som inte är nöjd kallas frustrerad . Det minsta antalet frustrerade kanter över alla stater kallas ation: s frustrationsindex (eller balansindex ). Att hitta frustrationsindexet är ett NP-svårt problem. Aref et al. föreslå binära programmeringsmodeller som kan beräkna frustrationsindex för grafer med upp till 10 5 kanter på en rimlig tid. Man kan se NP-hård komplexitet genom att observera att frustrationsindexet för en helt negativt signerad graf motsvarar det maximala skärproblemet i grafteori, vilket är NP-hårt. Anledningen till ekvivalensen är att frustrationsindex är lika med det minsta antalet kanter vars negation (eller, ekvivalent, radering; en sats av Harary) gör Σ balanserad. (Detta kan bevisas enkelt genom att byta.)

Frustrationsindexet är viktigt i en modell av spinnglasögon , den blandade Ising -modellen . I den här modellen är den signerade grafen fixad. Ett tillstånd består av att ge varje "topp" en antingen "upp" eller "ned". Vi tänker på snurr upp som +1 och snurra ner som −1. Varje tillstånd har således ett antal frustrerade kanter. Energin i ett tillstånd är större när det har mer frustrerade kanter, så ett marktillstånd är ett tillstånd med minst frustrerad energi. Således måste man hitta frustrationsindexet för att hitta markenergin för Σ.

Matroid teori

Det finns två matroider associerade med en signerad graf, kallad signerad-grafisk matroid (även kallad rammatroid eller ibland bias matroid ) och liftmatroid , som båda generaliserar cykelns matroid i en graf. De är speciella fall av samma matroider i ett partiskt diagram .

Den ram matroid (eller tecknat-grafisk matroid ) M ( G ) har till marken ställa in kanten som E . En kantuppsättning är oberoende om varje komponent innehåller antingen inga cirklar eller bara en cirkel, vilket är negativt. (I matroidteori fungerar en halvkant exakt som en negativ slinga.) En krets i matroid är antingen en positiv cirkel, eller ett par negativa cirklar tillsammans med en anslutande enkel väg, så att de två cirklarna antingen är osammanhängande (då anslutningsbanan har en ände gemensamt med varje cirkel och är i övrigt osammanhängande från båda) eller delar bara en enda gemensam hörn (i detta fall är anslutningsbanan den enda hörnpunkten). Rang av en kantuppsättning S är n - b , där n är antalet hörn för G och b är antalet balanserade komponenter i S , som räknar isolerade hörn som balanserade komponenter. Denna matroid är kolumnmatroiden för incidensmatrisen i den signerade grafen. Det är därför den beskriver de linjära beroenden för rötterna i ett klassiskt rotsystem.

Den förlängda lyftmatroid L 0 ( G ) har för sin mark satt uppsättningen E 0 föreningen av kantuppsättningen E med en extra punkt , som vi betecknar e 0 . Den lyft matroid L ( G ) är den utsträckta lyft matroid begränsad till E . Den extra punkten fungerar precis som en negativ slinga, så vi beskriver bara liftmatroiden. En kantuppsättning är oberoende om den innehåller antingen inga cirklar eller bara en cirkel, vilket är negativt. (Detta är samma regel som tillämpas separat för varje komponent i den signerade grafiska matroid.) En matroidkrets är antingen en positiv cirkel eller ett par negativa cirklar som antingen är sammanfogade eller bara har en gemensam toppunkt. Rang för en kantuppsättning S är n - c + ε, där c är antalet komponenter i S , som räknar isolerade hörn och ε är 0 om S är balanserad och 1 om det inte är det.

Andra typer av "signerad graf"

Ibland tecknen är +1 och −1. Detta är bara en skillnad i notering, om tecknen fortfarande multipliceras runt en cirkel och produktens tecken är det viktiga. Det finns dock två andra sätt att behandla kantetiketterna som inte passar in i signerad grafteori.

Termen signerad graf tillämpas ibland på grafer där varje kant har en vikt, w ( e ) = +1 eller −1. Dessa är inte samma typ av signerad graf; de är viktade grafer med en begränsad viktuppsättning. Skillnaden är att vikter adderas, inte multipliceras. Problemen och metoderna är helt olika.

Namnet tillämpas också på grafer där tecknen fungerar som färger på kanterna. Färgens betydelse är att den bestämmer olika vikter som appliceras på kanten, och inte att dess tecken är inneboende signifikant. Detta är fallet i knutteori , där tecknenas enda betydelse är att de kan bytas ut med tvåelementgruppen, men det finns ingen inneboende skillnad mellan positivt och negativt. Matroid för en teckenfärgad graf är cykelmatroiden för den underliggande grafen; det är inte ramen eller lyftmatroiden för den signerade grafen. Skyltetiketterna, istället för att byta matroid, blir tecken på elementen i matroid.

I denna artikel diskuterar vi endast signerad grafteori i strikt bemärkelse. För teckenfärgade grafer, se färgade matroider .

Signerad digraph

En signerad digraph är en riktad graf med signerade bågar. Signerade digrafer är mycket mer komplicerade än signerade grafer, eftersom endast tecknen på riktade cykler är signifikanta. Till exempel finns det flera definitioner av balans, som var och en är svår att karaktärisera, i stark kontrast till situationen för signerade oriktade grafer.

Signerade digrafer bör inte förväxlas med orienterade signerade grafer . De senare är dubbelriktade grafer, inte riktade grafer (utom i triviala fall av alla positiva tecken).

Vertex tecken

En vertex-signerad graf , ibland kallad en markerad graf , är en graf vars hörn får tecken. En cirkel kallas konsekvent (men detta är inte relaterat till logisk konsistens) eller harmonisk om produkten av dess hörntecken är positiv och inkonsekvent eller inharmonisk om produkten är negativ. Det finns ingen enkel karakterisering av harmoniska vertex-signerade grafer som är analoga med Hararys balanssats; i stället har karaktäriseringen varit ett svårt problem, bäst löst (ännu mer allmänt) av Joglekar, Shah och Diwan (2012).

Det är ofta lätt att lägga till kanttecken i teorin om hörnetecken utan större förändring; många resultat för vertex-signerade grafer (eller "markerade signerade grafer") sträcker sig naturligt till topp-och-kant-signerade grafer. Detta gäller särskilt för karakterisering av harmoni av Joglekar, Shah och Diwan (2012).

Skillnaden mellan en markerad signerad graf och en signerad graf med en tillståndsfunktion (som i § Frustration ) är att toppunktstecknen i den förstnämnda är en del av den väsentliga strukturen, medan en tillståndsfunktion är en variabel funktion på den signerade grafen.

Observera att termen "markerad graf" ofta används i Petri -nät i en helt annan mening; se artikeln om markerade grafer .

Färg

Som med osignerade grafer finns det en uppfattning om signerad graffärgning . När en färgning av en graf är en kartläggning från toppunktsuppsättningen till de naturliga talen, är en färgning av en signerad graf en kartläggning från toppunktsuppsättningen till heltal. Begränsningarna för korrekt färgning kommer från kanterna på det signerade diagrammet. De heltal som tilldelas två hörn måste vara distinkta om de är anslutna med en positiv kant. Etiketterna på intilliggande hörn får inte vara additiva inverser om hörnen är anslutna med en negativ kant. Det kan inte finnas någon korrekt färgning av en signerad graf med en positiv slinga.

När man begränsar hörnetiketterna till uppsättningen heltal med högst ett naturligt tal k , är uppsättningen korrekta färgämnen för en signerad graf begränsad. Förhållandet mellan antalet korrekta färgämnen och k är ett polynom i k . Detta är analogt med det kromatiska polynomet för osignerade grafer.

Ansökningar

Socialpsykologi

Inom socialpsykologi har signerade grafer använts för att modellera sociala situationer, med positiva kanter som representerar vänskap och negativa kanter fiendskap mellan noder, som representerar människor. Då är till exempel en positiv 3-cykel antingen tre gemensamma vänner eller två vänner med en gemensam fiende; medan en negativ 3-cykel antingen är tre gemensamma fiender, eller två fiender som delar en gemensam vän. Enligt balansteori är positiva cykler balanserade och ska vara stabila sociala situationer, medan negativa cykler är obalanserade och ska vara instabila. Enligt teorin, för tre ömsesidiga fiender, beror detta på att delning av en gemensam fiende sannolikt kommer att få två av fienderna att bli vänner . Om två fiender delar en vän, kommer den delade vännen troligtvis att välja den ena över den andra och göra en av hans eller hennes vänskap till en fiende.

Antal, Krapivsky och Reder betraktar social dynamik som förändringen i tecknet på en kant av ett signerat diagram. De sociala relationerna med tidigare vänner till ett skilsmässopar används för att illustrera utvecklingen av ett signerat diagram i samhället. En annan illustration beskriver de förändrade internationella allianserna mellan europeiska makter under decennierna före första världskriget . De överväger lokal triaddynamik och begränsad triaddynamik, där i det senare fallet en relationsändring görs endast när det totala antalet obalanserade triader reduceras. Simuleringen antog en komplett graf med slumpmässiga relationer med en slumpmässig obalanserad triad vald för transformation. Utvecklingen av den signerade grafen med N -noder under denna process studeras och simuleras för att beskriva den stationära densiteten hos vänliga länkar.

Balansläran har utmanats kraftigt, särskilt i sin tillämpning på stora system, på den teoretiska grunden att vänskapliga förbindelser knyter samman ett samhälle, medan ett samhälle uppdelat i två fienderläger skulle vara mycket instabilt. Experimentella studier har också gett endast en svag bekräftelse av förutsägelserna om strukturell balansteori.

Snurrglasögon

Inom fysiken är signerade grafer ett naturligt sammanhang för den allmänna, nonferromagnetic Ising -modellen , som tillämpas på studiet av spinnglasögon .

Komplexa system

Image
En tre-variabel signerad digraph som representerar ett enkelt trofiskt system

Med hjälp av en analytisk metod som ursprungligen utvecklades inom populationsbiologi och ekologi, men som nu används i många vetenskapliga discipliner, har signerade digrafer funnit tillämpning i resonemang om beteendet hos komplexa kausalsystem. Sådana analyser besvarar frågor om feedback på givna nivåer av systemet och om riktningen för variabla svar som ger en störning till ett system på en eller flera punkter, variabla korrelationer med sådana störningar, variansfördelningen över systemet och känsligheten eller okänslighet hos särskilda variabler för systemstörningar.

Datakluster

Korrelationskluster letar efter naturliga kluster av data efter likhet. Datapunkterna representeras som hörn i en graf, med en positiv kant som förenar liknande objekt och en negativ kant som sammanfogar olika objekt.

Neurovetenskap

Hjärnan kan betraktas som en signerad graf där synkronisering och antisynkronisering mellan aktivitetsmönster i hjärnregioner bestämmer positiva och negativa kanter. I detta avseende kan stabiliteten och energin i hjärnans nätverk utforskas.

Generaliseringar

En signerad graf är en speciell typ av förstärkningsgraf , där förstärkningsgruppen har ordning 2. Paret ( G , B ( Σ )) som bestäms av en signerad graf Σ är en speciell typ av förspänd graf .

Anteckningar

Referenser