Mediangraf

I grafteorin är en mediangraf en oriktad graf där alla tre hörn a , b och c har en enda median  , vertex m ( a , b , c ), som tillhör de kortaste vägarna mellan varje par av hörn a , b och c .

Begreppet mediangrafer har studerats under lång tid, till exempel av Birkhoff och Kiss ( Birkhoff, Kiss 1947 ) eller (mer explicit) av Avann ( Avann 1961 ), men den första artikeln med namnet "Mediangrafer" kom 1971 ( Nebesk'y 1971 ). Som Chang Graham och Saks skriver, "mediangrafer uppstår naturligt i studiet av ordnade mängder och diskreta distributionsgitter och har en omfattande litteratur." [1] Inom fylogenetiken är Buneman-grafen som representerar alla evolutionära träd med maximal sannolikhet . [2]Mediangrafer förekommer också i social choice theory  — om en uppsättning möjligheter har strukturen som en mediangraf, kan man entydigt bestämma preferensen för majoriteten bland dem. [3]

En översikt över mediangrafer finns i Klavžar, Mulder, 1999 , Bandelt, Chepoi, 2008 och Knuth, 2008 .

Exempel

Vilket träd som helst är en mediangraf. [4] I ett träd är föreningen av tre kortaste banor mellan par av tre hörn a , b och c antingen en bana i sig eller ett underträd som bildas av tre banor från samma centrala vertex av grad tre. Om föreningen av tre banor i sig är en bana, är medianen m ( a , b , c ) lika med en av hörnen a , b eller c , beroende på vilken vertex som är mellan två andra på banan. Om trädet som bildas av föreningen av banor inte är en bana, kommer medianen att vara underträdets centrala nod.

Gitter är ett annat exempel på mediangrafer . I en gittergraf kan koordinaterna för medianen m ( a , b , c ) hittas som medianen för koordinaterna för hörnen a , b och c . Omvänt visar det sig att det är möjligt att arrangera hörnen på ett heltalsgitter på ett sådant sätt att medianerna kan beräknas som medianerna för koordinaterna . [5]

Ramgrafer [6] , plana grafer där alla invändiga ytor är fyrkantiga och alla inre hörn har fyra eller fler infallande kanter, är en annan underklass av mediangrafer. [7] Polyomino  är ett specialfall av ramgrafer, och bildar därför också en mediangraf.

Simplexgrafen κ( G ) för en godtycklig oriktad graf G har en vertex för varje klick (komplett subgraf) av G , och två hörn är sammankopplade med en kant om motsvarande klick skiljer sig med endast en vertex. Medianen för givna tre klick kan bildas med hjälp av majoritetsregeln , som låter dig bestämma vilka klickhörn som ska inkluderas. En simplexgraf är en mediangraf där denna regel bestämmer medianen för varje trippel av hörn.

Ingen cykel med annan längd än fyra kan vara en mediangraf, eftersom varje sådan cykel har tre hörn a , b och c , som är förbundna med tre kortaste banor som inte har några skärningspunkter.

Motsvarande definitioner

I en godtycklig graf, för vilka två hörn som helst a och b , kallas det minsta antalet kanter mellan dem avståndet , vilket betecknas som d ( x , y ). Intervallet av hörn som ligger på den kortaste vägen mellan a och b definieras som

I ( a , b ) = { v | d ( a , b ) = d(a, v) + d(v, b) }.

Mediangrafen definieras som en graf, för alla tre hörn a , b och c där dessa intervall skär varandra i en punkt:

För alla a , b och c | I ( a , b ) ∩ I ( a , c ) ∩ I ( b , c )| = 1.

På liknande sätt, för vilka tre hörn som helst a , b och c , kan man hitta en vertex m ( a , b , c ) så att de ovägda avstånden i grafen uppfyller likheterna

och m ( a , b , c ) är det enda hörnet för vilket detta är sant.

Man kan också definiera mediangrafer som lösningar på problem med 2-tillfredsställelse, som hyperkubreduktion, som grafer för finita medianalgebror, som Buneman-grafer för Halley-partitionssystem och som grafer för windex 2. Se avsnitten nedan.

Distribuerade gitter och medianalgebror

I gitterteorin har grafen för ett ändligt gitter en vertex för varje element i gittret och en kant för varje par av element i det täckande förhållandet gittret. Gitter representeras vanligtvis visuellt som Hasse-diagram , som är ritningar av grafer av gitter. Dessa grafer, speciellt för distributiva gitter , visar sig vara nära besläktade med mediangrafer.

I det distributiva Birkhoff -gittret, den självdubbla ternära operationen av medianen [8]

m ( a , b , c ) = ( a ∧ b ) ∨ ( a ∧ c ) ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c ) ∧ ( b ∨ c ),

uppfyller några nyckelaxiom som är karakteristiska för vanliga medianvärden av tal i intervallet 0 till 1 och medianalgebror :

Den fördelande lagen kan ersättas med en associativ: [9]

Medianoperationen kan också användas för att definiera begreppet intervaller för distribuerade gitter:

I ( a , b ) = { x | m(a, x, b) = x } = { x | a ∧ b ≤ x ≤ a ∨ b }. [tio]

Grafen för ett ändligt fördelningsgitter har en kant mellan hörn a och b när I ( a , b ) = { a , b }. För alla två hörn a och b i denna graf består intervallet I ( a , b ) definierat i termer av gitterteori av hörnen på den kortaste vägen från a till b , och detta sammanfaller med intervallen från grafteorin som definierats tidigare. För alla tre gitterelement a , b och c , är m ( a , b , c ) den enda skärningspunkten mellan de tre intervallen I ( a , b ), I ( a , c ) och I ( b , c ). [11] Således är grafen för ett godtyckligt ändligt fördelat gitter en mediangraf. Omvänt, om mediangrafen G innehåller två hörn 0 och 1 så att alla andra hörn ligger på den kortaste vägen mellan dessa två (motsvarande m (0, a ,1) = a för alla a ), då kan vi definiera en fördelad ett gitter i vilket a ∧ b = m ( a ,0, b ) och a ∨ b = m ( a ,1, b ), och G kommer att vara grafen för detta gitter. [12]

Duffus och Rival ( Duffus, Rival 1983 ) beskriver distributiva gittergrafer som bevarande av reduktionsdiametern hos hyperkuber. I allmänhet genererar vilken mediangraf som helst en ternär operation m som uppfyller lagarna för idempotens, kommutativitet och distributivitet, men möjligen utan ett enda element i det distribuerade gittret. Varje ternär operation på en finit mängd som uppfyller dessa tre egenskaper (men som inte nödvändigtvis har element 0 och 1) genererar en mediangraf. [13]

Konvexa uppsättningar och Halley-familjer

I en mediangraf sägs en vertexmängd S vara konvex om hela intervallet I ( a , b ) är en delmängd av S för två hörn a och b som tillhör S . På motsvarande sätt, enligt de två definitionerna av intervall ovan, är S konvex om den innehåller någon kortaste väg mellan två hörn, eller om den innehåller medianen av tre punkter, varav två ligger i S . Observera att skärningspunkten mellan ett par konvexa uppsättningar i sig är konvex. [fjorton]

Konvexa mängder i en mediangraf har Halley-egenskapen : om F är en godtycklig familj av parvis skärande konvexa mängder, så har alla mängder F en gemensam punkt. [15] Så låt F bara ha tre konvexa mängder S , T och U . Låt a  vara skärningspunkterna mellan ett par S och T , b  skärningspunkterna mellan ett par T och U , och c  skärningspunkterna mellan ett par S och U . Då måste varje kortaste väg från a till b ligga inuti T på grund av konvexitet, och på samma sätt måste varje kortaste väg mellan två par av hörn ligga inom två andra mängder, men m ( a , b , c ) tillhör banorna mellan alla tre paren av hörn, så att den ligger innanför alla tre uppsättningarna. Om F innehåller mer än tre konvexa uppsättningar, erhålls resultatet genom induktion av antalet uppsättningar - man kan ersätta vilket par av uppsättningar som helst i F med deras skärningspunkt, vilket lämnar de resulterande uppsättningarna parvis skärande.

Uppsättningarna _ _

W uv = { w | d ( w , u ) < d ( w , v )},

som definieras för varje kant av uv- grafen. Enkelt uttryckt består W uv av hörn som är närmare u än v , eller motsvarande hörn w för vilka den kortaste vägen från v till w går genom u . För att visa att W uv är konvex, anta att w 1 w 2 … w k  är en godtyckligt kortaste väg som börjar och slutar inuti W uv . Då måste också w 2 ligga inuti W uv , annars blir två punkter m 1 = m ( u , w 1 , w k ) och m 2 = m ( m 1 , w 2 ... w k ) två olika medianer u , w 1 , och w k , vilket motsäger definitionen av en mediangraf, där medianen är unik per definition. Således ligger varje vertex på den kortaste vägen mellan två hörn W uv också i W uv , så W uv innehåller alla kortaste vägar mellan hörn, vilket är en av definitionerna av konvexitet.

Halley-egenskapen för uppsättningar W uv spelar en nyckelroll när det gäller att beskriva mediangrafer som ett problem med 2-tillfredsställelse.

2-tillfredsställelse

Mediangrafer är nära besläktade med lösningsuppsättningarna av 2-tillfredsställbarhetsproblem , som kan användas för att beskriva dessa grafer och som kan användas för att visa sambandet med den grannskapsbevarande hyperkubmappningen. [16]

En instans av 2-tillfredsställelse består av en uppsättning booleska variabler och en samling påståenden , restriktioner på vissa par av variabler för att undvika vissa kombinationer av värden. Vanligtvis uttrycks sådana problem i konjunktiv normal form , där varje påstående uttrycks med en disjunktion , och hela uppsättningen av begränsningar uttrycks av en konjunktion av påståenden, till exempel,

Lösningen på ett sådant fall är att tilldela sanna värden till för att tillfredsställa alla påståenden, eller, på motsvarande sätt, att de konjunktiva normalformspåståendena producerar sanna värden när man ersätter värdena. Familjen av alla lösningar har den naturliga strukturen av en medianalgebra, där medianen av tre lösningar bildas genom att välja majoritetsvärdet av de tre värdena. Det är lätt att direkt verifiera att denna median inte kan bryta mot påståendena. Således bildar dessa lösningar en mediangraf, där grannarna till varje lösning bildas genom att negera en uppsättning variabler, för vilka alla värden inom uppsättningarna antingen är lika eller inte lika.

Omvänt kan vilken mediangraf G som helst representeras som en uppsättning lösningar på en instans av 2-tillfredsställbarhetsproblemet. För att hitta en sådan representation skapar vi en instans av ett problem med 2-tillfredsställelse där varje variabel beskriver riktningen för en av grafens kanter (att tilldela en riktning till en kant resulterar i riktade grafer) och varje begränsning inkluderar två riktade bågar endast om det finns en vertex v för vilken båda bågarna ligger på den kortaste vägen från andra hörn till v . Varje vertex v i grafen G motsvarar en lösning på en instans av 2-satisfiability-problemet där alla bågar är riktade mot v . Varje instanslösning måste erhållas från någon vertex v på detta sätt, där v  är den gemensamma skärningspunkten av mängder W uw för bågar riktade från w till u . Denna gemensamma korsning existerar på grund av Halley-egenskapen för uppsättningarna W uw . Sålunda motsvarar lösningarna av en instans av detta 2-tillfredsställbarhetsproblem en till en till hörnen på grafen G .

Hyperkubreduktion

Reduktionen av en graf G  är en avbildning av en graf G till en av dess subgrafer med bevarad angränsning. [17] Mer exakt är det en homomorfism φ från G till sig själv, där φ( v ) = v för varje hörn v i subgrafen φ(G). Bilden av reduktionen kallas reduktionen av grafen G . Reduktioner är exempel på korta avbildningar : avståndet mellan φ( v ) och φ( w ) för alla v och w är högst avståndet mellan v och w , och dessa avstånd är lika om båda hörnen v och w tillhör φ( G ). Sålunda måste ruktionen vara en isometrisk subgraf av grafen G : avstånden i reduktionen är lika med motsvarande avstånd i G .

Om G är en mediangraf och a , b och c  är tre godtyckliga hörn av reduktionen φ( G ), så måste vertexet φ( m ( a , b , c )) vara medianen för a , b och c , och måste därför vara lika med m ( a , b , c ). Således innehåller φ( G ) medianerna för alla trippel av hörn och måste vara en mediangraf. Med andra ord är familjen av mediangrafer stängd under reduktionsoperationen. [arton]

En hyperkubgraf där hörnen motsvarar alla möjliga k -bitars vektorer och där två hörn är sammankopplade om motsvarande vektorer skiljer sig med en enda bit är ett specialfall av en k - dimensionell gittergraf, och därför en mediangraf. Medianen för trebitsvektorerna a , b och c kan beräknas genom att ta majoriteten av bitarna a , b och c . Eftersom mediangrafer stängs under reduktionsoperationen och inkluderar hyperkuber, är varje hyperkubreduktion en mediangraf.

Omvänt måste varje mediangraf vara en hyperkubreduktion. [19] Detta kan ses från ovanstående koppling mellan mediangrafer och 2-satisfiability-problemet. Låt G representera lösningar på en instans av 2-tillfredsställbarhetsproblemet. Utan förlust av generalitet kan denna instans formuleras så att inga två variabler alltid är lika eller inte lika i alla lösningar. Då bildar utrymmet för alla tilldelningar av värden till variabler en hyperkub. För varje påstående som bildas av disjunktionen av två variabler eller deras negationer, i en instans av 2-tillfredsställbarhetsproblemet, kan man bilda en hyperkubreduktion där tilldelningen av variabler som bryter mot detta påstående mappas till tilldelningen av variabler där båda variabler uppfyller påståendet, men ändrar inte andra variabler. Sammansättningen av reduktionerna konstruerade på detta sätt för varje påstående ger en reduktion av hyperkuben till lösningsutrymmet för instansen av problemet, och ger därför en representation av grafen G som en reduktion av hyperkuben. I synnerhet är mediangrafer isometriska till hyperkubundergrafer och är därför en partiell kub . Men inte alla partiella kuber är mediangrafer. Till exempel är en cykel med sex hörn en partiell kub, men inte en mediangraf.

Imrich och Klavžar ( Imrich, Klavžar 1998 ) skriver att en isometrisk inbäddning av en mediangraf i en hyperkub kan konstrueras i O( m log n ) tid, där n och m  är antalet grafens hörn och kanter. [tjugo]

Grafer utan trianglar och igenkänningsalgoritmer

Problemen med att kontrollera om en graf är median och om en graf innehåller trianglar är båda väl studerade, och som Imrich, Klavžar och Mulder (1999 ) noterar är de beräkningsmässigt ekvivalenta i någon mening. [21] Således kan den mest kända tiden för att kontrollera om en graf har trianglar, som är O( m 1,41 ), [22] användas som en uppskattning av tiden för att kontrollera om en graf är median, och eventuella framsteg i problem med att känna igen mediangrafer kommer att leda till framsteg i algoritmer för att bestämma trianglar i grafer.

För att bevisa ekvivalens i en riktning, anta att vi får en graf G och vi vill kontrollera om den innehåller trianglar. Låt oss skapa en annan graf H från G , som har en uppsättning av noll, en eller två angränsande hörn av grafen G som hörn . Två sådana uppsättningar ligger intill varandra i H om de skiljer sig åt med endast en vertex. Som en alternativ beskrivning kan H bildas genom att dela upp varje kant av G i två och lägga till en ny vertex kopplad till alla hörn i den ursprungliga grafen G. Denna graf H är en partiell kub till sin konstruktion, men den kommer att vara median endast när G inte innehåller trianglar - om a , b och c bildar en triangel i G , då { a , b }, { a , c } och { b , c } har inte medianer i H , eftersom en sådan median skulle behöva motsvara mängden { a , b , c }, men mängder av tre eller fler hörn av G bildar inte hörn i H . G innehåller alltså inte trianglar om och endast om H är en mediangraf. I fallet när G inte innehåller trianglar är H dess simplexgraf . En algoritm för att effektivt kontrollera om H är en mediangraf, genom denna konstruktion, kan användas för att kontrollera frånvaron av trianglar i en graf G . En sådan transformation bevarar problemets beräkningskomplexitet, eftersom storleken på H är proportionell mot storleken på G .

Reduktion i den andra riktningen, från att leta efter trianglar till att kontrollera om en graf är median, är mer komplex och beror på den beskrivna mediangrafigenkänningsalgoritmen ( Hagauer, Imrich, Klavžar 1999 ) som testar några nödvändiga villkor för en mediangraf i nästan linjärt tid. Det nya nyckelsteget använder bredd-först-sökning för att dekomponera grafen i nivåer enligt deras avstånd från en godtyckligt vald rot, och bildar därigenom en graf där två hörn ligger intill om de har en gemensam granne i den föregående nivån, och sökningen efter trianglar förekommer i dessa grafer. Medianen för en sådan triangel måste vara en gemensam granne till triangelns tre hörn. Om en sådan granne inte finns är grafen inte median. Om alla trianglar hittas och de alla har median, och den tidigare algoritmen bestämmer att grafen uppfyller resten av villkoren för mediangrafer, så måste den vara median. Observera att denna algoritm inte bara kräver att man kontrollerar frånvaron av trianglar, utan även att trianglarna räknas upp i nivågrafen. I en godtycklig graf kräver uppräkning av trianglar ibland tiden Ω( m 3/2 ), eftersom vissa grafer har så många trianglar. Hagauer (Hagauer et al.) visade dock att antalet trianglar som förekommer i nivågrafer är nästan linjärt, vilket gjorde att Alon (Alon et al.) kunde använda tekniken med snabb matrismultiplikation för att hitta trianglar.

Evolutionsträd, Buneman-grafer och Halley-partitionssystem

Fylogenetik  är härledningen av fylogenetiska träd från de observerade egenskaperna hos en art . Sådana träd måste ha vyer vid olika hörn och kan innehålla ytterligare dolda hörn , men dolda hörn måste ha tre eller fler infallande kanter och måste märkas med egenskaper. Egenskaper är binära om de bara har två möjliga värden, och en uppsättning arter och deras egenskaper visar en perfekt evolutionär historia om det finns ett evolutionärt träd där hörn (arter och dolda hörn) märkta med någon speciell egenskap bildar en sammanhängande underträd. Om ett träd med en perfekt utvecklingshistoria inte är möjligt är det ofta önskvärt att hitta den maximala sannolikheten -trädet, eller motsvarande, för att minimera antalet fall där ändpunkterna på trädets kanter har olika egenskaper genom att summera över alla kanter och över alla egenskaper.

Buneman ( 1971 ) beskrev en metod för att härleda perfekta evolutionsträd för binära egenskaper om de existerar. Hans metod är generaliserad på ett naturligt sätt för att konstruera en mediangraf av vilken uppsättning arter och binära egenskaper som helst, och denna graf kallas mediannätverket eller Buneman-grafen [23] och det är ett fylogenetiskt nätverk . Varje evolutionärt träd med maximal sannolikhet kan bäddas in i en Buneman-graf, i den meningen att trädets kanter följer banor i grafen och antalet förändringar av karakteriseringsvärden på en kant av trädet är lika med antalet motsvarande vägar. Buneman-grafen är ett träd om och bara om det finns en perfekt utvecklingshistoria. Detta inträffar när det inte finns två inkompatibla egenskaper för vilka alla fyra kombinationer av värden observeras.

För att generera en Buneman-graf för en uppsättning arter och funktioner, tar vi först bort redundanta funktioner som inte går att skilja från vissa andra funktioner och från redundanta funktioner som alltid sammanfaller med vissa andra funktioner. Sedan bildar vi en dold vertex för valfri kombination av karakteristiska värden, så att två valfria värden finns i kända former. I exemplet som visas finns det små brunstjärtade möss, små silverstjärtade möss, små bruna svansmöss, stora bruna svansmöss och stora silversvansmöss. Buneman-grafmetoden kommer att skapa en dold vertex som motsvarar en okänd art av små silverstjärtade möss, eftersom alla parningskombinationer (små och silverfärgade, små och svansade och silverfärgade och svansade) förekommer hos vissa andra arter. Metoden förutsätter dock inte förekomsten av stora bruna anuraner, eftersom det inte finns några arter av stora och samtidigt anuraner. Efter att de dolda hörnen har definierats bildar vi kanter mellan varje vypar eller dolda hörn som skiljer sig åt i en egenskap.

Man kan på motsvarande sätt beskriva en uppsättning av binära egenskaper som ett system av partitioner , familjer av mängder med egenskapen att komplementet av vilken mängd som helst i familjen tillhör familjen. Detta partitioneringssystem representerar en uppsättning för varje funktionsvärde, bestående av de arter som har det värdet. Om dolda hörn ingår, har det resulterande partitioneringssystemet Halley-egenskapen  — eventuella parvisa skärningar av underfamiljer är inte tomma. På sätt och vis kan mediangrafer ses som derivator av Halley plattsättningssystem — paren ( W uv , W vu ) definierade för varje kant uv av mediangrafen bildar ett Halley plattsättningssystem, så att om konstruktionen av Buneman-grafen tillämpas på detta system, behövs inte de dolda hörnen, och resultatet blir den ursprungliga grafen. [24]

Bandelt , Forster, Sykes, Richards, 1995 och Bandelt, Macaulay, Richards, 2000 beskriver en teknik för att förenkla manuell beräkning av Buneman-grafer och visar användningen av denna konstruktion för att visuellt representera människors genetiska relationer.

Ytterligare egenskaper

Anteckningar

  1. ↑ 1 2 3 Chung, Graham, Saks, 1987 .
  2. ↑ Buneman, 1971 , Klänning, Hendy, Huber, Moulton, 1997 , Klänning, Huber, Moulton, 1997 .
  3. ↑ Bandelt, Barthélémy, 1984 , Day, McMorris, 2003 .
  4. ↑ Imrich, Klavžar, 2000 , uttalande 1.26, s. 24.
  5. ↑ Detta följer omedelbart av hyperkubreduktionsegenskapen för mediangrafer, som beskrivs nedan.
  6. ↑ A. V. Karzanov. Utvidgningar av finita mått och problemet med utrustningsplacering // Proceedings of the ISA RAS. - 2007. - T. 29 . - S. 225-244 .
  7. ↑ Soltan, Zambitskii, Prisˇacaru, 1973 , Chepoi, Dragan, Vaxès, 2002 , Chepoi, Fanciullini, Vaxès, 2004 .
  8. ↑ Birkhoff, Kiss, 1947 tillskriver definitionen av denna operation till artikeln av G. Birkhoff. Gitterteori. - American Mathematical Society, 1940. - S. 74 . .
  9. ↑ Knuth, 2008 , s. 65, och övningar 75, 76 på sidorna 89-90. Knuth menar att det inte finns några enkla bevis för att associativitet innebär distributivitet.
  10. ↑ Ekvivalensen för de två uttrycken i denna likhet, det ena i termer av medianoperationen och det andra i termer av gitter- och olikhetsoperationerna, är sats 1 i Birkhoff och Kiss ( Birkhoff, Kiss 1947 ).
  11. ↑ Birkhoff, Kiss, 1947 , sats 2.
  12. ↑ Birkhoff, Kiss, 1947 , s. 751.
  13. ↑ Avann, 1961 .
  14. ↑ Knuth, 2008 kallar en sådan mängd ideal , men en konvex mängd i en distribuerad gittergraf är inte detsamma som ett gitterideal .
  15. ↑ Imrich, Klavžar, 2000 , sats 2.40, s. 77.
  16. ↑ Bandelt, Chepoi, 2008 , uttalande 2.5, s.8; Chung, Graham, Saks, 1989 ; Feder, 1995 ; Knuth, 2008 , Theorem S, s. 72.
  17. ↑ Helvete, 1976 .
  18. ↑ Imrich, Klavžar, 2000 , uttalande 1.33, s. 27.
  19. ↑ Bandelt, 1984 ; Imrich, Klavžar, 2000 , sats 2.39, s.76; Knuth, 2008 , s. 74.
  20. ↑ En teknik som kulminerar i Lemma 7.10 på sidan 218 i artikeln är att använda Chiba och Nishizekis algoritm ( Chiba, Nishizeki 1985 ) för att få en lista över alla cykler med längd 4 i en graf G , och som skapar en graf som har kanter som hörn graf G och som kanter dess motsatta sidor av en cykel med 4 kanter. De sammankopplade komponenterna i dessa grafer används för att bilda hyperkubens koordinater. En likvärdig algoritm är Knuths ( Knuth 2008 ), Algorithm H, s. 69.
  21. ↑ För mediangrafigenkänningsalgoritm, se Jha, Slutzki, 1992 , Imrich, Klavžar, 1998 och Hagauer, Imrich, Klavžar, 1999 . För den triangelfria grafigenkänningsalgoritmen, se Itai, Rodeh, 1978 , Chiba, Nishizeki, 1985 och Alon, Yuster, Zwick, 1995 .
  22. ↑ Alon, Yuster, Zwick, 1995 . Algoritmen är baserad på snabb matrismultiplikation . Här är m  antalet kanter i grafen, och ett stort "O" döljer en stor konstant faktor. Den bästa praktiska triangeligenkänningsalgoritmen kräver O( m 3/2 ) tid. För mediangrafigenkänning kan tidsbegränsningen uttryckas antingen i termer av m eller n (antalet hörn), såsom m = O( n log n ).
  23. ↑ Mulder, Schrijver, 1979 beskrev en version av denna metod för funktionssystem som inte kräver dolda hörn, medan Barthélémy, 1989 gav den fullständiga versionen. Buneman-grevarna är namngivna i Dress, Hendy, Huber, Moulton, 1997 och Dress, Huber, Moulton, 1997 .
  24. ↑ Mulder, Schrijver, 1979 .
  25. ↑ Škrekovski, 2001 .
  26. ↑ Mulder, 1980 .

Anteckningar

Länkar