Avslutning av ackordal - Chordal completion
I grafteorin , en gren av matematik, en ackorduppfyllning av en given icke-riktad graf G är ett ackorddiagram , på samma toppunktuppsättning, som har G som subgraf. En minimal ackordavslutning är en ackordavslutning så att varje graf som bildas genom att ta bort en kant inte längre skulle vara en ackordavslutning. En minsta ackordavslutning är en ackordavslutning med så få kanter som möjligt.
En annan typ av ackord fullbordan, en som minimerar storleken på den maximala klick i den resulterande ackord graf kan användas för att definiera den treewidth av G . Chordal-kompletteringar kan också användas för att karakterisera flera andra grafklasser inklusive AT-fria grafer, klofria AT-fria grafer och grafer .
Den minsta ackorduppslutningen var ett av tolv beräkningsproblem vars komplexitet listades som öppen i 1979 års bok Computers and Intractability . Tillämpningar av ackordavslutning inkluderar modellering av problemet med att minimera fyllning vid Gaussisk eliminering på glesa symmetriska matriser och rekonstruktion av fylogenetiska träd .
Akkordiska kompletteringar av en graf kallas ibland trianguleringar, men denna term är tvetydig även i samband med grafteori, eftersom den också kan hänvisa till maximala plana grafer .
Relaterade diagramfamiljer
En graf G är en AT-fri graf om och bara om alla dess minimala ackorduppfyllningar är intervalldiagram . G är ett klofritt AT-fritt diagram om och bara om alla dess minimala ackorduppfyllningar är korrekta intervalldiagram. Och G är en graf om och bara om alla dess minimala ackorduppfyllelser är trivialt perfekta grafer .
En graf G har högst trebredd k om och endast om G har minst en ackordfördelning vars maximala klickstorlek är högst k + 1 . Den har högst vägbredd k om och endast om G har åtminstone en ackordavslutning som är ett intervalldiagram med högst klickstorlek som mest k + 1 . Den har bandbredd högst k om och bara om G har minst en ackordfördelning som är ett korrekt intervalldiagram med maximal klickstorlek högst k + 1 . Och den har trädjup k om och bara om den har åtminstone en ackordavslutning som är en trivialt perfekt graf med maximal klickstorlek högst k .
Applikationer
Den ursprungliga tillämpningen av ackordavslutning som beskrivs i Datorer och intrakterbarhet innebär Gaussisk eliminering för glesa matriser . Under processen med eliminering av Gauss vill man minimera fyllningskoefficienterna för matrisen som ursprungligen var noll men som senare blev noll, eftersom behovet av att beräkna värdena för dessa koefficienter saktar ner algoritmen. Mönstret för icke-nollor i en gles symmetrisk matris kan beskrivas med en icke-riktad graf (med matrisen som dess angränsningsmatris ); mönstret för icke-nollor i den ifyllda matrisen är alltid ett ackorddiagram, varje minimal ackorduppfyllelse motsvarar ett utfyllnadsmönster på detta sätt. Om en ackordavslutning av en graf ges kan en sekvens av steg för att utföra Gaussisk eliminering för att uppnå detta utfyllnadsmönster hittas genom att beräkna en eliminationsordning för den resulterande ackorddiagrammet. På detta sätt kan det minimala ifyllningsproblemet ses som motsvarande det minsta problemet med ackordavslutning. I denna ansökan kan plana grafer uppstå i lösningen av tvådimensionella system med ändliga element; det följer av den plana separatorsatsen att varje plan graf med n hörn har en ackordfördelning med högst O ( n log n ) kanter.
En annan applikation kommer från fylogeni , problemet med att rekonstruera evolutionära träd, till exempel träd av organismer som är föremål för genetiska mutationer eller träd av uppsättningar av forntida manuskript som kopieras från ett annat ämne till skriftfel. Om man antar att varje genetisk mutation eller skriftfel bara inträffar en gång, får man en perfekt fylogeni , ett träd där arten eller manuskripten med någon speciell egenskap alltid bildar ett anslutet underträd. Som Buneman (1974) beskriver, kan förekomsten av en perfekt fylogeni modelleras som ett ackordproblem. Man ritar ett "överlappningsdiagram" G där hörnpunkterna är attributvärden (specifika val för vissa egenskaper hos en art eller ett manuskript) och kanterna representerar par attributvärden som delas av minst en art. Hörnpunkterna i diagrammet kan färgas av identiteten för de egenskaper som varje attributvärde kommer från, så att det totala antalet färger är lika med antalet egenskaper som används för att härleda fylogenin. Då finns en perfekt fylogeni om och bara om G har en ackordal komplettering som respekterar färgningen.
Beräkningskomplexitet
Även om det listades som ett öppet problem i boken Computers and Intractability från 1979 , löstes snabbt den beräkningskomplexerade minimiprogrammet för ackorduppfyllning (även kallat minimiproblemet ): Yannakakis (1981) visade att det var NP-komplett . Om minimiackord fullbordan adderar k kanter till en graf G , så är det möjligt att hitta ett ackord fullbordan med användning högst 8 k 2 tillsatta kanter, i polynomisk tid. Problemet med att hitta den optimala uppsättningen k- kanter som kan läggas till kan också lösas med en algoritm med fast parameter , i tidspolynom i grafstorleken och subeksponentiell i k .
Den treewidth (minsta klick storleken på en ackord slutförande) och besläktade parametrar inklusive pathwidth och träd djup är också NP-komplett för att beräkna, och (såvida inte P = NP) inte kan approximeras i polynomisk tid till inom en konstant faktor av deras optimala värden ; emellertid är approximationsalgoritmer med logaritmiska approximationsförhållanden kända för dem.
Både minimifyllnings- och trebreddsproblemen kan lösas på exponentiell tid . Mer exakt, för ett n- vertikalt diagram är tiden O (1,9601 n ) .