Likgiltig graf

En indifferent graf är en oriktad graf som är konstruerad genom att tilldela ett reellt tal till varje vertex och koppla två hörn med en kant när deras nummer skiljer sig inte mer än en [1] . Indifferenta grafer är också grafer över skärningspunkter av uppsättningar av enhetssegment eller intervall med en viss inbäddningsegenskap (inget intervall innehåller någon annan). Baserat på dessa två typer av intervallrepresentationer kallas dessa grafer också för enhetssegmentgrafer eller korrekta intervallgrafer . Indifferenta grafer bildar en underklass av intervallgrafer .

Motsvarande beskrivningar

Finita likgiltiga grafer kan på motsvarande sätt beskrivas som

För oändliga grafer kan vissa av dessa definitioner ges av olika grafer.

Egenskaper

Eftersom likgiltiga grafer är ett specialfall av intervallgrafer , har likgiltiga grafer alla egenskaper hos intervallgrafer. I synnerhet är de ett specialfall av ackordsgrafer och perfekta grafer . Dessa grafer är också ett specialfall av cirkeldiagram , vilket inte är sant för allmänna intervallgrafer.

I Erdős-Rényi-modellen av slumpmässiga grafer kommer en graf från en vertex vars antal kanter är betydligt mindre att vara en indifferent graf med hög sannolikhet, medan grafer med ett antal kanter som är väsentligt större än inte kommer att vara en indifferent graf med en hög sannolikhet [9] .

Bredden på bandet av en godtycklig grafär en mindre än storleken på den största klicken i den likgiltiga grafen som innehållersom en subgraf och är vald för att minimera storleken på den största klicken [10] . Den här egenskapen bildar paralleller, liknande kopplingen mellan kurvbredds- och intervallgrafer , och mellan trädbredds- och kordaldiagram . En svagare föreställning om bredd, klickbredd , kan vara godtyckligt stor på likgiltiga grafer [11] . Men varje korrekt underklass av likgiltiga grafer som inte är stängda med avseende på genererade subgrafer har en begränsad klickbredd [12] .

Varje ansluten indifferent graf innehåller en Hamiltonsk väg [13] . En indifferent graf har en Hamiltonsk graf om och bara om den är dubbelkopplad [14] .

Indifferenta grafer tillfredsställer rekonstruktionsförmodan — de definieras unikt av deras vertexborttagna subgrafer [15] .

Algoritmer

Liksom med flerdimensionella enhetsskivor är det möjligt att transformera en uppsättning punkter till deras likgiltiga graf eller en uppsättning enhetssegment till deras enhetssegmentgraf i linjär tid , mätt i termer av storleken på utdatagrafen. Algoritmen avrundar punkter (eller intervallcentrum) till närmaste mindre heltal, använder en hashtabell för att hitta alla par av punkter vars avrundade värden skiljer sig åt med högst ett ( fixerad radie närmaste granne problem ), och väljer par i den resulterande listan, vars oavrundade värden inte är mer än ett från varandra [16] .

Man kan testa om en given graf är indifferent i linjär tid med hjälp av PQ-träd för att konstruera intervallrepresentationer av grafen och sedan testa om vertexordningen härledd från denna representation uppfyller egenskaperna hos en indifferent graf [4] . Man kan också basera igenkänningsalgoritmen för likgiltiga grafer på igenkänningsalgoritmer för ackordsgrafen [14] . Vissa alternativa linjära tidsigenkänningsalgoritmer är baserade på bredd-först-sökning eller lexikografisk bredd-först-sökning , snarare än på förhållandet mellan likgiltiga grafer och intervallgrafer [17] [18] [19] [20] .

När hörnen är sorterade efter deras numeriska värden som beskriver en likgiltig graf (eller efter en sekvens av enhetssegment i en intervallrepresentation), kan samma ordning användas för att hitta den optimala färgningen av dessa grafer för att lösa problemet med den kortaste vägen , bygga Hamiltonbanor och största matchningar i linjär tid [4] . En Hamiltonsk cykel kan hittas från en riktig intervallrepresentationsgraf i tid [13] , men om grafen är en input till ett problem kan samma problem lösas i linjär tid, vilket kan generaliseras till intervallgrafer [21] [ 22] .

Den föreskrivna färgningen förblir NP-komplett även när den är begränsad till likgiltiga grafer [23] . Den är dock fast-parametriskt lösbar om den parametreras av det totala antalet ingångsfärger [12] .

Applikationer

Inom matematisk psykologi uppstår likgiltiga grafer från nyttofunktioner genom att skala funktionen så att en enhet representerar en skillnad i nytta som är tillräckligt liten för att enheten kan anses obetydlig för individen. I den här applikationen kan par av element vars verktyg är tillräckligt stora partiellt ordnas efter relativ nyttoordning, vilket resulterar i halvordningen [1] [24] .

Inom bioinformatik kan uppgiften att lägga till en färgad graf till en korrekt färgad graf av enhetssegment användas för att modellera upptäckten av falskt negativa DNA- genomsamlingar från fragment [25] .

Se även

Anteckningar

  1. ↑ 1 2 3 4 5 6 Roberts, 1969 , sid. 139–146.
  2. ↑ 1 2 Bogart, West, 1999 , sid. 21–23.
  3. ↑ Wegner, 1967 .
  4. ↑ 1 2 3 Looges, Olariu, 1993 , sid. 15–25.
  5. ↑ Jackowski, 1992 , sid. 103–109.
  6. ↑ 1 2 Gutierrez, Oubina, 1996 , sid. 199–205.
  7. ↑ Mertzios, 2008 , sid. 332–337.
  8. ↑ 1 2 Brandstädt, Hundt, Mancini, Wagner, 2010 , sid. 897–910.
  9. ↑ Cohen, 1982 , sid. 21–24.
  10. ↑ Kaplan, Shamir, 1996 , sid. 540–561.
  11. ↑ Golumbic, Rotics, 1999 , sid. 5–17.
  12. ↑ 1 2 Lozin, 2008 , sid. 871–882.
  13. ↑ 1 2 Bertossi, 1983 , sid. 97–101.
  14. ↑ 1 2 Panda, Das, 2003 , sid. 153–161.
  15. ↑ von Rimscha, 1983 , sid. 283–291.
  16. ↑ Bentley, Stanat, Williams, 1977 , sid. 209–212.
  17. ↑ Corneil, Kim, Natarajan, Olariu, Sprague, 1995 , sid. 99–104.
  18. ↑ Herrera de Figueiredo, Meidanis, Picinin de Mello, 1995 , sid. 179–184.
  19. ↑ Corneil, 2004 , sid. 371–379.
  20. ↑ Hell, Huang, 2004 , sid. 554–570.
  21. ↑ Keil, 1985 , sid. 201–206.
  22. ↑ Ibarra, 2009 , sid. 1105–1108.
  23. ↑ Marx, 2006 , sid. 995–1002.
  24. ↑ Roberts, 1970 , sid. 243–258.
  25. ↑ Goldberg, Golumbic, Kaplan, Shamir, 2009 .

Litteratur

Länkar