Signert graf - Signed graph

Image
Det er åtte måter tegn kan tilordnes sidene av en trekant. Et ulikt antall negative tegn utgjør en ubalansert trekant, ifølge Fritz Heiders teori.

Innen grafteori i matematikk er en signert graf en graf der hver kant har et positivt eller negativt tegn.

En signert graf er balansert hvis produktet av kanttegn rundt hver syklus er positivt. Tre grunnleggende spørsmål om en signert graf er: Er den balansert? Hva er den største størrelsen på en balansert kant i den? Hva er det minste antallet hjørner som må slettes for å gjøre det balansert? Det første spørsmålet er enkelt å løse raskt; den andre og den tredje er beregningsmessig utilgjengelige (teknisk sett er de NP-harde ).

Navnet "signert graf" og begrepet balanse dukket først opp i en matematisk artikkel av Frank Harary i 1953. Dénes Kőnig hadde allerede studert likeverdige forestillinger i 1936 under en annen terminologi, men uten å erkjenne relevansen til skiltgruppen . Ved Senter for gruppedynamikk ved University of Michigan , Dorwin Cartwright og Harary generalisert Fritz Heider 's psykologisk teori om balanse i trekanter av følelser til en psykologisk teori om balanse i signerte grafer.

Signerte grafer har blitt gjenoppdaget mange ganger fordi de kommer naturlig opp i mange ikke -relaterte områder. For eksempel gjør de det mulig for en å beskrive og analysere geometrien til delsett i de klassiske rotsystemene . De vises i topologisk grafteori og gruppeteori . De er en naturlig kontekst for spørsmål om odde og jevne sykluser i grafer. De vises ved beregning av grunnstatsenergien i den ikke-ferromagnetiske Ising-modellen ; for dette må man finne et største balansert kantsett i Σ. De har blitt brukt på dataklassifisering i korrelasjonsklynger .

Eksempler

  • Den komplette signerte grafen på n hjørner med sløyfer, angitt med ± K n o , har alle mulige positive og negative sider inkludert negative sløyfer, men ingen positive sløyfer. Kantene tilsvarer røttene til rotsystemet C n ; kolonnen i en kant i forekomstmatrisen (se nedenfor) er vektoren som representerer roten.
  • Den komplette signerte grafen med halve kanter, ± K n ', er ± K n med en halvkant ved hvert toppunkt. Kantene tilsvarer røttene til rotsystemet B n , halvkantene tilsvarer enhetsbasisvektorene.
  • Den komplette signerte koblingsgrafen , ± K n , er den samme, men uten sløyfer. Kantene tilsvarer røttene til rotsystemet D n .
  • En hel-positiv signert graf har bare positive kanter. Hvis den underliggende grafen er G , er det all-positive signering skrevet + G .
  • En hel-negativ signert graf har bare negative kanter. Den er balansert hvis og bare hvis den er todelt fordi en sirkel er positiv hvis og bare hvis den har jevn lengde. En helt negativ graf med underliggende graf G er skrevet- G .
  • En signert komplett graf har som underliggende graf G den vanlige komplette grafen K n . Det kan ha noen tegn. Signerte komplette grafer tilsvarer to-grafer , som har verdi i endelig gruppeteori. En to-graf kan defineres som klassen av toppunktssett med negative trekanter (som har et oddetall negative kanter) i en signert fullstendig graf.

Tilstøtningsmatrise

Den naboskapsmatrisen av en signert graf Σ med n vertekser er en n x n matrise A (Σ). Den har en rad og kolonne for hvert toppunkt. Oppføringen a vw i rad v og kolonne w er antall positive vw -kanter minus antall negative vw -kanter. På diagonalen er a vv = 0 hvis det ikke er sløyfer eller halve kanter; riktig definisjon når slike kanter eksisterer, avhenger av omstendighetene.

Orientering

En signert graf er orientert når hver ende av hver kant får en retning, slik at endene i en positiv kant er rettet fra det ene endepunktet til det andre, og i en negativ kant er begge ender rettet utover, til sine egne hjørner , eller begge er rettet innover, vekk fra hjørnene. Dermed er en orientert signert graf det samme som en toveis graf . (Det er veldig annerledes enn en signert digraph .)

Forekomstmatrise

En forekomstmatrise av en signert graf med n hjørner og m kanter er en n × m matrise, med en rad for hvert toppunkt og en kolonne for hver kant. Den oppnås ved å orientere den signerte grafen på noen måte. Deretter er oppføringen η ij +1 hvis kant j er orientert i toppunkt i , -1 hvis kant j er orientert ut av toppunkt i , og 0 hvis toppunkt i og kant j ikke er innfallende . Denne regelen gjelder for en lenke, hvis kolonne vil ha to nulloppføringer med absolutt verdi 1, en halvkant, hvis kolonne har en enkel nulloppføring +1 eller −1, og en løs kant, hvis kolonne bare har nuller. Kolonnen i en sløyfe er imidlertid helt null hvis sløyfen er positiv, og hvis sløyfen er negativ har den oppføring ± 2 i raden som tilsvarer dens innfallende toppunkt.

Eventuelle to forekomstmatriser er relatert ved å negere noen delmengder av kolonnene. Således for de fleste formål er det ikke spiller noen rolle hvilken orientering vi bruker å definere forekomsten matrise, og vi kan snakke om den forekomsten matrise av Σ uten å bekymre seg nøyaktig hvilken det er.

Negere en rad av forekomstmatrisen tilsvarer å bytte det tilsvarende toppunktet.

Veksling

Å bytte inn et toppunkt Σ betyr å negere tegnene på alle kantene som kommer til det toppunktet. Å bytte et sett med hjørner betyr å negere alle kantene som har en ende i det settet og en ende i det komplementære settet. Å bytte en rekke hjørner, en gang hver, er det samme som å bytte hele settet på en gang.

Bytte av signerte grafer ( signert bytte ) er generalisert fra Seidel (1976), der den ble brukt på grafer ( grafbytte ), på en måte som tilsvarer bytte av signerte komplette grafer.

Bytteekvivalens betyr at to grafer er relatert til bytte, og en ekvivalensklasse med signerte grafer under bytte kalles en bytteklasse . Noen ganger brukes disse begrepene på ekvivalens av signerte grafer under kombinasjonen av bytte og isomorfisme , spesielt når grafene er umerkede; men for å skille de to begrepene kan den kombinerte ekvivalensen kalles bytte isomorfisme og en ekvivalensklasse under bytte isomorfisme kan kalles en bytte isomorfisme klasse .

Å bytte et sett med hjørner påvirker adjasensmatrisen ved å negere radene og kolonnene til de skiftede hjørnene. Det påvirker forekomstmatrisen ved å negere radene til de bytte hjørnene.

Grunnleggende teorem

Tegnet på en bane er produktet av tegnene på kantene. Således er en bane bare positiv hvis det er et jevnt antall negative kanter i den (hvor null er partall). I den matematiske balanse teorien til Frank Harary balanseres en signert graf når hver syklus er positiv. Han beviser at en signert graf er balansert når (1) for hvert par noder, alle veier mellom dem har det samme tegnet, eller (2) grafen skiller seg inn i et par undergrafer, som hver består av positive kanter, men forbundet med negative kanter. Teoremet ble utgitt av Harary i 1953. Det generaliserer teoremet om at en vanlig (usignert) graf er todelt hvis og bare hvis hver syklus har jevn lengde.

Et enkelt bevis bruker metoden for å bytte. For å bevise Hararys teorem viser man ved induksjon at Σ kan byttes til å være alt positivt hvis og bare hvis det er balansert.

En svakere teorem, men med et enklere bevis, er at hvis hver 3-syklus i en signert fullstendig graf er positiv, så er grafen balansert. For bevis, velge en vilkårlig node n og sted den og alle de noder som er knyttet til n av en positiv flanke i en gruppe, kalt A , og alle de som er knyttet til n av en negativ kant på den andre, kalt B . Siden dette er en komplett graf, må alle to noder i A være venner og hver to node i B må være venner, ellers ville det være en 3-syklus som var ubalansert. (Siden dette er en komplett graf, vil en hvilken som helst negativ kant forårsake en ubalansert 3-syklus.) På samme måte må alle negative kanter gå mellom de to gruppene.

Frustrasjon

Gi hvert toppunkt en verdi på +1 eller −1; vi kaller dette en tilstand av Σ. En kant kalles tilfreds hvis den er positiv og begge endepunktene har samme verdi, eller den er negativ og endepunktene har motsatte verdier. En kant som ikke er fornøyd kalles frustrert . Det minste antallet frustrerte kanter over alle tilstander kalles frustrasjonsindeksen (eller linjeindeksen for balansen ) på Σ. Å finne frustrasjonsindeksen er et NP-vanskelig problem. Aref et al. foreslå binære programmeringsmodeller som er i stand til å beregne frustrasjonsindeksen til grafer med opptil 10 5 kanter på en rimelig tid. Man kan se NP-hard kompleksitet ved å observere at frustrasjonsindeksen til en helt negativ signert graf tilsvarer det maksimale kuttproblemet i grafteorien, som er NP-hard. Årsaken til ekvivalensen er at frustrasjonsindeksen tilsvarer det minste antallet kanter hvis negasjon (eller, ekvivalent, sletting; en teori av Harary) gjør Σ balansert. (Dette kan enkelt bevises ved å bytte.)

Frustrasjonsindeksen er viktig i en modell av spinnglass , den blandede Ising -modellen . I denne modellen er den signerte grafen fikset. En tilstand består av å gi et "spinn", enten "opp" eller "ned", til hvert toppunkt. Vi tenker på snurr opp som +1 og snur ned som −1. Dermed har hver stat et antall frustrerte kanter. Energien til en stat er større når den har mer frustrerte kanter, så en grunntilstand er en tilstand med færrest frustrert energi. For å finne grunnenergien til Σ må man derfor finne frustrasjonsindeksen.

Matroid teori

Det er to matroider assosiert med en signert graf, kalt den signerte-grafiske matroid (også kalt frame matroid eller noen ganger bias matroid ) og liftmatroid , som begge generaliserer syklusmatroid av en graf. De er spesielle tilfeller av de samme matroidene i en partisk graf .

Den ramme matroid (eller signert-grafisk matroid ) M ( G ) har for sin bakken angir kanten satt E . Et kantsett er uavhengig hvis hver komponent enten inneholder ingen sirkler eller bare en sirkel, som er negativ. (I matroidteori fungerer en halvkant nøyaktig som en negativ sløyfe.) En krets i matroid er enten en positiv sirkel, eller et par negative sirkler sammen med en sammenhengende enkel bane, slik at de to sirklene enten er usammenhengende (da forbindelsesbanen har en ende felles med hver sirkel og er ellers usammenhengende fra begge deler) eller deler bare et enkelt felles toppunkt (i dette tilfellet er forbindelsesbanen det ene toppunktet). Rangen til et kantsett S er n - b , hvor n er antall hjørner av G og b er antall balanserte komponenter i S , og teller isolerte hjørner som balanserte komponenter. Denne matroid er kolonnen matroid av forekomstmatrisen til den signerte grafen. Det er derfor den beskriver de lineære avhengighetene til røttene til et klassisk rotsystem.

Den utvidede løfte matroid L 0 ( G ) har for bakken satt settet E 0 foreningen av kantsett E med et ekstra punkt , som vi betegner e 0 . Den heis matroid L ( G ) er forlenget heisen matroid begrenset til E . Ekstrapunktet fungerer akkurat som en negativ sløyfe, så vi beskriver bare heismatroiden. Et kantsett er uavhengig hvis det enten inneholder ingen sirkler eller bare en sirkel, som er negativ. (Dette er den samme regelen som gjelder separat for hver komponent i den signerte grafiske matroid.) En matroidkrets er enten en positiv sirkel eller et par negative sirkler som enten er usammenhengende eller bare har et felles toppunkt. Rangen til et kantsett S er n - c + ε, hvor c er antall komponenter i S , som teller isolerte hjørner, og ε er 0 hvis S er balansert og 1 hvis det ikke er det.

Andre typer "signert graf"

Noen ganger blir tegnene +1 og −1. Dette er bare en forskjell i notasjon, hvis tegnene fremdeles multipliseres rundt en sirkel og tegnet på produktet er det viktige. Det er imidlertid to andre måter å behandle kantetikettene som ikke passer inn i signert grafteori.

Begrepet signert graf brukes tidvis på grafer der hver kant har en vekt, w ( e ) = +1 eller −1. Dette er ikke den samme typen signert graf; de er vektede grafer med et begrenset vektsett. Forskjellen er at vekter legges til, ikke multipliseres. Problemene og metodene er helt forskjellige.

Navnet brukes også på grafer der skiltene fungerer som farger på kantene. Fargenes betydning er at den bestemmer forskjellige vekter på kanten, og ikke at dens tegn er iboende signifikant. Dette er tilfellet i knute-teorien , der tegnens eneste betydning er at de kan byttes ut av gruppen med to elementer, men det er ingen iboende forskjell mellom positivt og negativt. Matroid av en tegnfarget graf er syklusmatroid av den underliggende grafen; det er ikke rammen eller løftematroiden til den signerte grafen. Skiltetikettene, i stedet for å bytte matroid, blir tegn på elementene i matroid.

I denne artikkelen diskuterer vi bare signert grafteori i streng forstand. For tegnfargede grafer, se fargede matroider .

Signert digraph

En signert digraph er en rettet graf med signerte buer. Signerte grafer er langt mer kompliserte enn signerte grafer, fordi bare tegn på rettet syklus er signifikante. For eksempel er det flere definisjoner av balanse, som hver er vanskelig å karakterisere, i sterk kontrast til situasjonen for signerte, ikke -styrte grafer.

Signerte grafer bør ikke forveksles med orienterte signerte grafer . Sistnevnte er toveis grafer, ikke dirigerte grafer (unntatt i trivialt tilfelle av alle positive tegn).

Vertex tegn

En toppunktsignert graf , noen ganger kalt en markert graf , er en graf hvis hjørner får tegn. En sirkel kalles konsekvent (men dette er ikke relatert til logisk konsistens) eller harmonisk hvis produktet av dets toppunktstegn er positivt, og inkonsekvent eller inharmonisk hvis produktet er negativt. Det er ingen enkel karakterisering av harmoniske toppunktsignerte grafer som er analoge med Hararys balansesetning; i stedet har karakteriseringen vært et vanskelig problem, best løst (enda mer generelt) av Joglekar, Shah og Diwan (2012).

Det er ofte enkelt å legge kanttegn til teorien om toppunktstegn uten store endringer; mange resultater for vertex-signerte grafer (eller "merkede signerte grafer") strekker seg naturlig til topp-og-kant-signerte grafer. Dette gjelder særlig karakteriseringen av harmoni av Joglekar, Shah og Diwan (2012).

Forskjellen mellom en markert signert graf og en signert graf med en tilstandsfunksjon (som i § Frustrasjon ) er at toppunktstegnene i førstnevnte er en del av den vesentlige strukturen, mens en tilstandsfunksjon er en variabel funksjon på den signerte grafen.

Vær oppmerksom på at begrepet "markert graf" er mye brukt i Petri -garn i en helt annen betydning; se artikkelen om markerte grafer .

Fargelegging

Som med usignerte grafer , er det en forestilling om signert graffarging . Når en farging av en graf er en kartlegging fra toppunktet til de naturlige tallene, er en farging av en signert graf en kartlegging fra toppunktet til heltallene. Begrensningene for riktige fargestoffer kommer fra kantene på den signerte grafen. Heltallene som er tilordnet to hjørner, må være forskjellige hvis de er forbundet med en positiv kant. Etikettene på tilstøtende hjørner må ikke være additive inverser hvis toppunktene er forbundet med en negativ kant. Det kan ikke være riktig farging av en signert graf med en positiv sløyfe.

Når du begrenser toppunktetikettene til settet med heltall med en størrelse på høyst et naturlig tall k , er settet med riktige fargestoffer for en signert graf begrenset. Forholdet mellom antall slike riktige fargestoffer og k er et polynom i k . Dette er analogt med det kromatiske polynomet for usignerte grafer.

applikasjoner

Sosial psykologi

I sosialpsykologi har signerte grafer blitt brukt til å modellere sosiale situasjoner, med positive kanter som representerer vennskap og negative kanter fiendskap mellom noder, som representerer mennesker. Da er for eksempel en positiv 3-syklus enten tre felles venner, eller to venner med en felles fiende; mens en negativ 3-syklus enten er tre gjensidige fiender, eller to fiender som deler en felles venn. I følge balanseteori er positive sykluser balansert og skal være stabile sosiale situasjoner, mens negative sykluser er ubalanserte og skal være ustabile. Ifølge teorien, for tre gjensidige fiender, er dette fordi det å dele en felles fiende sannsynligvis vil føre til at to av fiendene blir venner . Hvis to fiender deler en venn, vil den delte vennen sannsynligvis velge den ene fremfor den andre og gjøre et av vennskapene til en fiende.

Antal, Krapivsky og Reder anser sosial dynamikk som endringen i tegnet på en kant av en signert graf. De sosiale forholdene til tidligere venner til et skilsmissepar brukes til å illustrere utviklingen av en signert graf i samfunnet. En annen illustrasjon beskriver de skiftende internasjonale alliansene mellom europeiske makter i tiårene før første verdenskrig . De vurderer lokal triaddynamikk og begrenset triadedynamikk, der i sistnevnte tilfelle en relasjonsendring bare gjøres når det totale antallet ubalanserte triader reduseres. Simuleringen antok en komplett graf med tilfeldige relasjoner med en tilfeldig ubalansert triade valgt for transformasjon. Utviklingen av den signerte grafen med N -noder under denne prosessen studeres og simuleres for å beskrive den stasjonære tettheten av vennlige koblinger.

Balanse teorien har blitt sterkt utfordret, spesielt i sin anvendelse på store systemer, på den teoretiske grunnen om at vennskapelige forbindelser knytter et samfunn sammen, mens et samfunn delt i to fienderleire ville være svært ustabilt. Eksperimentelle studier har også gitt bare en svak bekreftelse på spådommene om strukturell balanse teori.

Spinn briller

I fysikk er signerte grafer en naturlig kontekst for den generelle, nonferromagnetiske Ising -modellen , som brukes på studiet av spinnglass .

Komplekse systemer

Image
En tre-variabel signert digraph som representerer et enkelt trofisk system

Ved å bruke en analytisk metode som opprinnelig ble utviklet i populasjonsbiologi og økologi, men nå brukt i mange vitenskapelige disipliner, har signerte digrafer funnet anvendelse i resonnement om oppførselen til komplekse årsakssystemer. Slike analyser svarer på spørsmål om tilbakemelding på gitte nivåer av systemet, og om retningen til variable responser gitt en forstyrrelse til et system på ett eller flere punkter, variable korrelasjoner gitt slike forstyrrelser, fordelingen av varians over systemet, og sensitiviteten eller ufølsomhet for bestemte variabler for systemforstyrrelser.

Dataklynger

Korrelasjonsklynger ser etter naturlig klynging av data etter likhet. Datapunktene er representert som hjørnene i en graf, med en positiv kant som forbinder lignende elementer og en negativ kant som forbinder forskjellige elementer.

Nevrovitenskap

Hjernen kan betraktes som en signert graf der synkronisering og antisynkronisering mellom aktivitetsmønstre i hjernegrupper bestemmer positive og negative kanter. I denne forbindelse kan stabilitet og energi i hjernenettverket utforskes.

Generaliseringer

En signert graf er en spesiell type forsterkningsgraf , der gevinstgruppen har rekkefølge 2. Paret ( G , B ( Σ )) bestemt av en signert graf Σ er en spesiell type partisk graf .

Merknader

Referanser