Median graf

I grafteori er en mediangraf en urettet graf , hvor alle tre hjørner a , b og c har en enkelt median  , toppunkt m ( a , b , c ), som hører til de korteste veje mellem hvert par af spidser a , b og c .

Begrebet mediangrafer er blevet undersøgt i lang tid, for eksempel af Birkhoff og Kiss ( Birkhoff, Kiss 1947 ) eller (mere eksplicit) af Avann ( Avann 1961 ), men det første papir med navnet "Mediangrafer" udkom i 1971 ( Nebesk'y 1971 ). Som Chang Graham og Saks skriver, "opstår mediangrafer naturligt i studiet af ordnede sæt og diskrete fordelingsgitter og har en omfattende litteratur." [1] I fylogenetik er Buneman-grafen, der repræsenterer al maksimal sandsynlighed evolutionære træer , mediangrafen. [2]Mediangrafer optræder også i social choice-teori  — hvis et sæt muligheder har strukturen som en mediangraf, kan man utvetydigt bestemme præferencen for flertallet blandt dem. [3]

En oversigt over mediangrafer kan findes i Klavžar, Mulder, 1999 , Bandelt, Chepoi, 2008 og Knuth, 2008 .

Eksempler

Ethvert træ er en mediangraf. [4] I et træ er foreningen af ​​tre korteste stier mellem par af tre toppunkter a , b og c enten en sti i sig selv eller et undertræ dannet af tre stier fra det samme centrale toppunkt i grad tre. Hvis foreningen af ​​tre baner i sig selv er en sti, er medianen m ( a , b , c ) lig med et af hjørnerne a , b eller c , afhængigt af hvilket toppunkt der er mellem to andre på stien. Hvis træet dannet af foreningen af ​​stier ikke er en sti, vil medianen være den centrale knude i undertræet.

Gitter er et andet eksempel på mediangrafer . I en gittergraf kan koordinaterne for medianen m ( a , b , c ) findes som medianen af ​​koordinaterne for hjørnerne a , b og c . Omvendt viser det sig, at det er muligt at arrangere toppunkterne på et heltalsgitter på en sådan måde, at medianerne kan beregnes som medianerne af koordinaterne . [5]

Rammegrafer [6] , plane grafer, hvor alle indvendige flader er firkanter, og alle indre hjørner har fire eller flere indfaldende kanter, er en anden underklasse af mediangrafer. [7] Polyomino  er et specialtilfælde af rammegrafer, og danner derfor også en mediangraf.

Simplexgrafen κ( G ) af en vilkårlig ikke-rettet graf G har et toppunkt for hver klike (komplet undergraf) af G , og to toppunkter er forbundet med en kant, hvis de tilsvarende kliker kun adskiller sig med ét toppunkt. Medianen af ​​givne tre kliker kan dannes ved hjælp af flertalsreglen , som giver dig mulighed for at bestemme, hvilke klikhjørner der skal inkluderes. En simpleksgraf er en mediangraf, hvor denne regel bestemmer medianen af ​​hver tredobbelt af hjørner.

Ingen anden cyklus af længde end fire kan være en mediangraf, da enhver sådan cyklus har tre hjørner a , b og c , som er forbundet med tre korteste stier, der ikke har nogen skæringspunkter.

Tilsvarende definitioner

I en vilkårlig graf kaldes det mindste antal kanter mellem dem for to vilkårlige spidser a og b for afstanden , som er angivet som d ( x , y ). Intervallet af toppunkter, der ligger på den korteste vej mellem a og b , er defineret som

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

Mediangrafen er defineret som en graf for alle tre hjørner a , b og c , hvor disse intervaller skærer hinanden i ét punkt:

For alle a , b og c | I ( a , b ) ∩ I ( a , c ) ∩ I ( b , c )| = 1.

Tilsvarende kan man for alle tre toppunkter a , b og c finde et toppunkt m ( a , b , c ), således at de uvægtede afstande i grafen opfylder lighederne

og m ( a , b , c ) er det eneste toppunkt, for hvilket dette er sandt.

Man kan også definere mediangrafer som løsninger på 2-tilfredshedsproblemer, som hyperkubereduktion, som grafer for endelige medianalgebraer, som Buneman-grafer for Halley-partitionssystemer og som windex 2-grafer.Se afsnittene nedenfor.

Fordelte gitter og median algebraer

I gitterteorien har grafen for et endeligt gitter et toppunkt for hvert element i gitteret og en kant for hvert par af elementer i det dækkende forhold gitteret. Gitter er normalt repræsenteret visuelt som Hasse-diagrammer , som er tegninger af grafer over gitter. Disse grafer, især for distributive gitter , viser sig at være tæt forbundet med mediangrafer.

I det distributive Birkhoff -gitter, den selv-duale ternære operation af medianen [8]

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

opfylder nogle nøgleaksiomer, der er karakteristiske for almindelige medianer af tal i intervallet fra 0 til 1 og medianalgebraer :

Den distributive lov kan erstattes af en associativ lov: [9]

Medianoperationen kan også bruges til at definere begrebet intervaller for distribuerede gitter:

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

Grafen for et endeligt fordelingsgitter har en kant mellem hjørnerne a og b , når I ( a , b ) = { a , b }. For to vilkårlige toppunkter a og b i denne graf består intervallet I ( a , b ) defineret i termer af gitterteori af hjørnerne af den korteste vej fra a til b , og dette falder sammen med intervallerne fra grafteori defineret tidligere. For alle tre gitterelementer a , b og c , er m ( a , b , c ) det eneste skæringspunkt mellem de tre intervaller I ( a , b ), I ( a , c ) og I ( b , c ). [11] Grafen for et vilkårligt endeligt distribueret gitter er således en mediangraf. Omvendt, hvis mediangrafen G indeholder to toppunkter 0 og 1, således at alle andre toppunkter ligger på den korteste vej mellem disse to (tilsvarende m (0, a ,1) = a for alle a ), så kan vi definere en fordelt et gitter, hvor a ∧ b = m ( a ,0, b ) og a ∨ b = m ( a ,1, b ), og G vil være grafen for dette gitter. [12]

Duffus og Rival ( Duffus, Rival 1983 ) beskriver distributive gittergrafer som bevarer reduktionsdiameteren af ​​hyperkuber. Generelt genererer enhver mediangraf en ternær operation m , der opfylder lovene om idempotens, kommutativitet og distributivitet, men muligvis uden et enkelt element i det distribuerede gitter. Enhver ternær operation på et endeligt sæt, der opfylder disse tre egenskaber (men ikke nødvendigvis har elementerne 0 og 1), genererer en mediangraf. [13]

Konvekse sæt og Halley-familier

I en mediangraf siges en toppunktsmængde S at være konveks , hvis hele intervallet I ( a , b ) er en delmængde af S for alle to hjørner a og b , der hører til S. Tilsvarende, ifølge de to definitioner af intervaller ovenfor, er S konveks, hvis den indeholder en hvilken som helst korteste vej mellem to hjørner, eller hvis den indeholder medianen af ​​tre punkter, hvoraf to ligger i S . Bemærk, at skæringspunktet mellem ethvert par konvekse sæt i sig selv er konveks. [fjorten]

Konvekse mængder i en mediangraf har Halley-egenskaben : hvis F er en vilkårlig familie af parvis skærende konvekse mængder, så har alle mængder F et fælles punkt. [15] Så lad F kun have tre konvekse sæt S , T og U . Lad a  være skæringspunkterne mellem et par S og T , b  skæringspunkterne mellem et par T og U , og c  skæringspunkterne mellem et par S og U . Så skal enhver korteste vej fra a til b ligge inde i T på grund af konveksitet, og på samme måde skal enhver korteste vej mellem to par af knudepunkter ligge inden for to andre sæt, men m ( a , b , c ) tilhører stierne mellem alle tre par knudepunkter, så den ligger inde i alle tre sæt. Hvis F indeholder mere end tre konvekse sæt, opnås resultatet ved induktion af antallet af sæt - man kan erstatte et hvilket som helst par af sæt i F med deres skæringspunkt, hvilket efterlader de resulterende mængder, der krydser parvis.

Sættene _ _

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

som er defineret for hver kant af uv- grafen. Enkelt sagt består W uv af toppunkter, der er tættere på u end på v , eller tilsvarende toppunkter w , for hvilke den korteste vej fra v til w går gennem u . For at vise, at W uv er konveks, antag, at w 1 w 2 … w k  er en vilkårlig korteste vej, der starter og slutter inde i W uv . Så skal w 2 også ligge inde i W uv , ellers vil to punkter m 1 = m ( u , w 1 , w k ) og m 2 = m ( m 1 , w 2 ... w k ) være to forskellige medianer u , w 1 , og w k , hvilket modsiger definitionen af ​​en mediangraf, hvor medianen per definition er unik. Således ligger ethvert toppunkt på den korteste vej mellem to toppunkter W uv også i W uv , så W uv indeholder alle korteste veje mellem toppunkter, hvilket er en af ​​definitionerne på konveksitet.

Halley-egenskaben for sæt W uv spiller en nøglerolle i at beskrive mediangrafer som et 2-tilfredshedsproblem.

2-tilfredsstillende

Mediangrafer er tæt knyttet til løsningssættene af 2-tilfredshedsproblemer , som kan bruges til at beskrive disse grafer, og som kan bruges til at vise sammenhængen med den adjacency-bevarende hyperkube-mapping. [16]

Et tilfælde af 2-tilfredsstillelse består af et sæt booleske variable og en samling af påstande , restriktioner på nogle par af variabler for at undgå nogle kombinationer af værdier. Typisk er sådanne problemer udtrykt i konjunktiv normal form , hvor hvert udsagn er udtrykt ved en disjunktion , og hele sættet af begrænsninger er udtrykt ved en konjunktion af udsagn, f.eks.

Løsningen på et sådant tilfælde er at tildele sande værdier til for at tilfredsstille alle påstande, eller tilsvarende, at de konjunktive normalformspåstande producerer sande værdier, når værdierne erstattes. Familien af ​​alle løsninger har den naturlige struktur som en median algebra, hvor medianen af ​​tre løsninger dannes ved at vælge majoritetsværdien af ​​de tre værdier. Det er let at verificere direkte, at denne median ikke kan overtræde påstandene. Disse løsninger danner således en mediangraf, hvor naboerne til hver løsning dannes ved at negere et sæt af variabler, for hvilke alle værdier inden for mængderne enten er ens eller ikke ens.

Omvendt kan enhver mediangraf G repræsenteres som et sæt af løsninger på en instans af 2-tilfredshedsproblemet. For at finde en sådan repræsentation opretter vi en instans af et 2-tilfredshedsproblem, hvor hver variabel beskriver retningen af ​​en af ​​grafens kanter (tildeling af en retning til en kant resulterer i rettede grafer), og hver begrænsning inkluderer kun to rettede buer, hvis der eksisterer et toppunkt v , hvor begge buer ligger på den korteste vej fra andre toppunkter til v . Hvert toppunkt v på grafen G svarer til en løsning på en instans af 2-tilfredshedsproblemet, hvor alle buer er rettet mod v . Hver instansløsning skal opnås fra et eller andet toppunkt v på denne måde, hvor v  er det fælles skæringspunkt mellem mængder W uw for buer rettet fra w til u . Dette fælles skæringspunkt eksisterer på grund af Halley-egenskaben for sættene W uw . Således svarer løsningerne af en instans af dette 2-tilfredshedsproblem en til en til toppunkterne på grafen G .

Hyperkubereduktion

Reduktionen af ​​en graf G  er en afbildning af en graf G til en af ​​dens undergrafer med bevaret naboskab. [17] Mere præcist er det en homomorfi φ fra G til sig selv, hvor φ( v ) = v for hvert toppunkt v i undergrafen φ(G). Billedet af reduktionen kaldes reduktionen af ​​grafen G . Reduktioner er eksempler på korte afbildninger : afstanden mellem φ( v ) og φ( w ) for enhver v og w er højst afstanden mellem v og w , og disse afstande er ens, hvis begge toppunkter v og w tilhører φ( G ). Ruktionen skal således være en isometrisk subgraf af grafen G : afstandene i reduktionen er lig med de tilsvarende afstande i G .

Hvis G er en mediangraf, og a , b og c  er tre vilkårlige hjørner af reduktionen φ( G ), så skal toppunktet φ( m ( a , b , c )) være medianen af ​​a , b og c , og skal derfor være lig med m ( a , b , c ). Således indeholder φ( G ) medianerne for alle tripler af hjørner og skal være en mediangraf. Med andre ord er familien af ​​mediangrafer lukket under reduktionsoperationen. [atten]

En hyperkubegraf, hvor toppunkterne svarer til alle mulige k -bit vektorer , og hvor to toppunkter er forbundet, hvis de tilsvarende vektorer adskiller sig med en enkelt bit, er et specialtilfælde af en k - dimensional gittergraf, og derfor en mediangraf. Medianen af ​​tre bitvektorer a , b og c kan beregnes ved at tage majoritetsværdien af ​​bit a , b og c . Da mediangrafer lukkes under reduktionsoperationen og inkluderer hyperkuber, er enhver hyperkubereduktion en mediangraf.

Omvendt skal enhver mediangraf være en hyperkubereduktion. [19] Dette kan ses af ovenstående sammenhæng mellem mediangrafer og 2-tilfredshedsproblemet. Lad G repræsentere løsninger på en instans af 2-tilfredshedsproblemet. Uden tab af generalitet kan denne instans formuleres sådan, at ingen to variable altid er ens eller ikke ens i alle løsninger. Derefter danner rummet for alle tildelinger af værdier til variable en hyperkube. For ethvert udsagn dannet af disjunktionen af ​​to variable eller deres negationer, i et tilfælde af 2-tilfredshedsproblemet, kan man danne en hyperkubereduktion, hvor tildelingen af ​​variabler, der overtræder denne udsagn, afbildes til tildelingen af ​​variabler, hvor begge variabler opfylder udsagnet, men ændrer ikke andre variabler. Sammensætningen af ​​reduktionerne konstrueret på denne måde for hvert udsagn giver en reduktion af hyperkuben til løsningsrummet for instansen af ​​problemet, og giver derfor en repræsentation af grafen G som en reduktion af hyperkuben. Især mediangrafer er isometriske til hyperkubeundergrafer og er derfor en delvis terning . Det er dog ikke alle partielle terninger, der er mediangrafer. For eksempel er en cyklus med seks hjørner en delvis terning, men ikke en mediangraf.

Imrich og Klavžar ( Imrich, Klavžar 1998 ) skriver, at en isometrisk indlejring af en mediangraf i en hyperkube kan konstrueres i O( m log n ) tid, hvor n og m  er antallet af grafens toppunkter og kanter. [tyve]

Grafer uden trekanter og genkendelsesalgoritmer

Problemerne med at kontrollere, om en graf er median, og om en graf indeholder trekanter , er begge velundersøgte, og som Imrich, Klavžar og Mulder (1999 ) bemærker, er de beregningsmæssigt ækvivalente i en vis forstand. [21] Således kan den bedst kendte tid til at kontrollere, om en graf har trekanter, som er O( m 1,41 ), [22] bruges som et estimat af tiden til at kontrollere, om en graf er median, og eventuelle fremskridt i problem med at genkende mediangrafer vil føre til fremskridt i algoritmer til bestemmelse af trekanter i grafer.

For at bevise ækvivalens i én retning, antag, at vi får en graf G , og vi vil kontrollere, om den indeholder trekanter. Lad os skabe en anden graf H ud fra G , der som toppunkter har et sæt af nul, et eller to tilstødende hjørner af grafen G . To sådanne sæt er tilstødende i H , hvis de kun adskiller sig med ét toppunkt. Som en alternativ beskrivelse kan H dannes ved at dele hver kant af G i to og tilføje et nyt toppunkt forbundet med alle hjørner af den oprindelige graf G. Denne graf H er en delvis terning efter konstruktion, men den vil kun være median, når G ikke indeholder trekanter - hvis a , b og c danner en trekant i G , så er { a , b }, { a , c } og { b , c } har ikke medianer i H , da en sådan median skulle svare til mængden { a , b , c }, men mængder af tre eller flere toppunkter af G danner ikke toppunkter i H . G indeholder således ikke trekanter, hvis og kun hvis H er en mediangraf. I det tilfælde, hvor G ikke indeholder trekanter, er H dens simpleksgraf . En algoritme til effektivt at kontrollere, om H er en mediangraf, ved denne konstruktion, kan bruges til at kontrollere fraværet af trekanter i en graf G . En sådan transformation bevarer den beregningsmæssige kompleksitet af problemet, da størrelsen af ​​H er proportional med størrelsen af ​​G .

Reduktion i den anden retning, fra at lede efter trekanter til at kontrollere, om en graf er median, er mere kompleks og afhænger af den beskrevne mediangrafgenkendelsesalgoritme ( Hagauer, Imrich, Klavžar 1999 ), som tester nogle nødvendige betingelser for en mediangraf næsten lineært tid. Det nye nøgletrin bruger bredde-først søgning til at dekomponere grafen i niveauer i henhold til deres afstand fra en vilkårligt valgt rod, hvorved der dannes en graf, hvor to hjørner er tilstødende, hvis de har en fælles nabo i det forrige niveau, og søgningen efter trekanter forekommer i disse grafer. Medianen af ​​enhver sådan trekant skal være en fælles nabo af trekantens tre hjørner. Hvis en sådan nabo ikke findes, er grafen ikke median. Hvis alle trekanter findes, og de alle har medianer, og den tidligere algoritme bestemmer, at grafen opfylder resten af ​​betingelserne for mediangrafer, så skal den være median. Bemærk, at denne algoritme ikke kun kræver kontrol for fravær af trekanter, men også opregning af trekanter i niveaugrafen. I en vilkårlig graf kræver opregning af trekanter nogle gange tid Ω( m 3/2 ), da nogle grafer har så mange trekanter. Hagauer (Hagauer et al.) viste dog, at antallet af trekanter, der forekommer i niveaugrafer, er næsten lineært, hvilket gjorde det muligt for Alon (Alon et al.) at bruge teknikken med hurtig matrixmultiplikation til at finde trekanter.

Evolutionstræer, Buneman-grafer og Halley-partitionssystemer

Fylogenetik  er udledningen af ​​fylogenetiske træer fra de observerede karakteristika for en art . Sådanne træer skal have udsigter ved forskellige toppunkter og kan indeholde yderligere skjulte toppunkter , men skjulte toppunkter skal have tre eller flere indfaldende kanter og skal mærkes med karakteristika. Karakteristika er binære , hvis de kun har to mulige værdier, og et sæt af arter og deres karakteristika viser en perfekt evolutionær historie hvis der er et evolutionært træ, hvor knudepunkter (arter og skjulte knudepunkter) mærket med en bestemt karakteristik danner en sammenhængende undertræ. Hvis et træ med en perfekt udviklingshistorie ikke er muligt, er det ofte ønskeligt at finde den maksimale sandsynlighed træ, eller tilsvarende, for at minimere antallet af tilfælde, hvor endepunkterne af træets kanter har forskellige karakteristika ved at summere over alle kanter og over alle egenskaber.

Buneman ( 1971 ) beskrev en metode til at udlede perfekte udviklingstræer for binære træk, hvis de eksisterer. Hans metode er generaliseret på en naturlig måde til at konstruere en mediangraf af ethvert sæt af arter og binære karakteristika, og denne graf kaldes mediannetværket eller Buneman-grafen [23] og det er et fylogenetisk netværk . Ethvert evolutionært træ med maksimal sandsynlighed kan indlejres i en Buneman-graf i den forstand, at træets kanter følger stier i grafen, og antallet af karakteriseringsværdiændringer på en kant af træet er lig med antallet af tilsvarende stier. Buneman-grafen er et træ, hvis og kun hvis der eksisterer en perfekt udviklingshistorie. Dette sker, når der ikke er to inkompatible egenskaber, for hvilke alle fire kombinationer af værdier er observeret.

For at generere en Buneman-graf for et sæt arter og funktioner, fjerner vi først overflødige funktioner, der ikke kan skelnes fra nogle andre funktioner og fra overflødige funktioner, der altid falder sammen med nogle andre funktioner. Derefter danner vi et skjult toppunkt for enhver kombination af karakteristiske værdier, således at alle to værdier eksisterer i kendte former. I det viste eksempel er der små brunhalemus, små sølvhalemus, små brunhalemus, store brunhalemus og store sølvhalemus. Buneman-grafmetoden vil skabe et skjult toppunkt svarende til en ukendt art af små sølvhalede mus, eftersom enhver parringskombination (små og sølvfarvede, små og halede og sølvfarvede og halede) forekommer hos nogle andre arter. Metoden forudsætter dog ikke eksistensen af ​​store brune anuraner, da der ikke er nogen arter af store og samtidig anuraner. Efter at de skjulte hjørner er defineret, danner vi kanter mellem hvert par af visninger eller skjulte hjørner, der adskiller sig i en karakteristik.

Man kan tilsvarende beskrive et sæt binære karakteristika som et system af partitioner , familier af sæt med den egenskab, at komplementet af ethvert sæt i familien tilhører familien. Dette partitioneringssystem repræsenterer et sæt for hver funktionsværdi, der består af de arter, der har denne værdi. Hvis skjulte hjørner er inkluderet, har det resulterende partitioneringssystem Halley-egenskaben  - eventuelle parvise skæringer af underfamilier er ikke tomme. I en vis forstand kan mediangrafer opfattes som afledte af Halley flisesystemer - parrene ( W uv , W vu ) defineret for hver kant uv af mediangrafen danner et Halley flisesystem, således at hvis konstruktionen af ​​Buneman grafen anvendes på dette system, er de skjulte hjørner ikke nødvendige, og resultatet bliver den originale graf. [24]

Bandelt , Forster, Sykes, Richards, 1995 og Bandelt, Macaulay, Richards, 2000 beskriver en teknik til at forenkle den manuelle beregning af Buneman-grafer og viser brugen af ​​denne konstruktion til visuelt at repræsentere menneskers genetiske forhold.

Yderligere egenskaber

Noter

  1. ↑ 1 2 3 Chung, Graham, Saks, 1987 .
  2. ↑ Buneman, 1971 , Kjole, Hendy, Huber, Moulton, 1997 , Kjole, Huber, Moulton, 1997 .
  3. ↑ Bandelt, Barthélémy, 1984 , Day, McMorris, 2003 .
  4. ↑ Imrich, Klavžar, 2000 , Statement 1.26, s. 24.
  5. ↑ Dette følger umiddelbart af hyperkubereduktionsegenskaben for mediangrafer, som beskrevet nedenfor.
  6. ↑ A. V. Karzanov. Udvidelser af finite metrics og problemet med udstyrsplacering // 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 tilskriver definitionen af ​​denne operation til artiklen af ​​G. Birkhoff. Gitterteori. - American Mathematical Society, 1940. - S. 74 . .
  9. ↑ Knuth, 2008 , s. 65, og øvelser 75, 76 på side 89-90. Knuth hævder, at der ikke er noget simpelt bevis for, at associativitet indebærer distributivitet.
  10. ↑ Ækvivalensen af ​​de to udtryk i denne lighed, det ene i form af medianoperationen og det andet i form af gitter- og ulighedsoperationerne, er sætning 1 i Birkhoff og Kiss ( Birkhoff, Kiss 1947 ).
  11. ↑ Birkhoff, Kiss, 1947 , sætning 2.
  12. ↑ Birkhoff, Kiss, 1947 , s. 751.
  13. ↑ Avann, 1961 .
  14. ↑ Knuth, 2008 kalder et sådant sæt ideal , men et konveks sæt i en distribueret gittergraf er ikke det samme som et gitterideal .
  15. ↑ Imrich, Klavžar, 2000 , sætning 2.40, s. 77.
  16. ↑ Bandelt, Chepoi, 2008 , udtalelse 2.5, s.8; Chung, Graham, Saks, 1989 ; Feder, 1995 ; Knuth, 2008 , Teorem S, s. 72.
  17. ↑ Helvede, 1976 .
  18. ↑ Imrich, Klavžar, 2000 , udtalelse 1.33, s. 27.
  19. ↑ Bandelt, 1984 ; Imrich, Klavžar, 2000 , sætning 2.39, s.76; Knuth, 2008 , s. 74.
  20. ↑ En teknik, der kulminerer i Lemma 7.10 på side 218 i artiklen, er at bruge Chiba og Nishizekis algoritme ( Chiba, Nishizeki 1985 ) til at få en liste over alle cyklusser med længde 4 i en graf G , og som skaber en graf, der har kanter som knudepunkter graf G og som kanter sine modsatte sider af en cyklus med 4 kanter. De forbundne komponenter i disse grafer bruges til at danne hyperkubens koordinater. En tilsvarende algoritme er Knuths ( Knuth 2008 ), Algorithm H, s. 69.
  21. ↑ For median grafgenkendelsesalgoritme, se Jha, Slutzki, 1992 , Imrich, Klavžar, 1998, og Hagauer, Imrich, Klavžar, 1999 . For den trekantfrie grafgenkendelsesalgoritme, se Itai, Rodeh, 1978 , Chiba, Nishizeki, 1985, og Alon, Yuster, Zwick, 1995 .
  22. ↑ Alon, Yuster, Zwick, 1995 . Algoritmen er baseret på hurtig matrixmultiplikation . Her er m  antallet af kanter i grafen, og et stort "O" skjuler en stor konstant faktor. Den bedste praktiske trekantsgenkendelsesalgoritme kræver O( m 3/2 ) tid. Til genkendelse af mediangrafer kan tidsbegrænsningen udtrykkes enten i m eller n (antallet af hjørner), såsom m = O( n log n ).
  23. ↑ Mulder, Schrijver, 1979 beskrev en version af denne metode til funktionssystemer, der ikke kræver skjulte hjørner, mens Barthélémy, 1989 gav den fulde version. Buneman-greverne er navngivet i Dress, Hendy, Huber, Moulton, 1997 og Dress, Huber, Moulton, 1997 .
  24. ↑ Mulder, Schrijver, 1979 .
  25. ↑ Škrekovski, 2001 .
  26. ↑ Mulder, 1980 .

Noter

Links