Klick (grafteori)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 11 april 2022; kontroller kräver 4 redigeringar .

En klick av en oriktad graf är en delmängd av dess hörn, varav två är förbundna med en kant. Klickor är ett av kärnbegreppen inom grafteorin och används i många andra matematiska problem och grafkonstruktioner. Klickar studeras också inom datavetenskap  - problemet med att avgöra om det finns en klick av en given storlek i en graf ( Clique problem ) är NP-komplett . Trots denna svårighet studeras många algoritmer för att hitta klick.

Även om studiet av kompletta subgrafer började med formuleringen av Ramseys teorem i termer av grafteori av Erdős och Székeres [1] [2] . Termen "klick" kommer från arbetet av Luc och Peri [3] , som använde fullständiga subgrafer när de studerade sociala nätverk för att modellera klicker av människor , det vill säga grupper av människor som känner varandra [4] . Clicks har många andra tillämpningar inom vetenskap, och bioinformatik i synnerhet .

Definitioner

En klick i en oriktad graf är en delmängd av hörn så att det för vilka två hörn som helst finns en kant som förbinder dem. Detta motsvarar att säga att subgrafen som genereras av är komplett .

En maximal klick  , eller klickmaximum genom inkludering , är en klick som inte kan utökas genom att lägga till hörn till den. Den här grafen innehåller med andra ord inte en större klick som den tillhör.

Den största klicken  , eller klicken som är maximal i storlek , är klicken för den maximala storleken för den givna grafen.

Klicknumret för en graf  är antalet hörn i den största klicken i grafen . Skärningsnumret för en graf  är det minsta antalet klick som tillsammans täcker alla kanter på grafen .

Motsatsen till en klick är en oberoende uppsättning i den meningen att varje klick motsvarar en oberoende uppsättning i den komplementära grafen . Problemet med klicktäckning är att hitta det minsta möjliga antalet klick som innehåller alla hörn i grafen.

En relaterad term  är biclique, en komplett tvådelad subgraf . Den tvådelade dimensionen av en graf är det minsta antal bicliques som behövs för att täcka alla kanter på grafen.

Matematik

Matematiska resultat angående klick inkluderar följande.

Några viktiga grafklasser kan definieras av deras klicker:

Dessutom involverar många andra matematiska konstruktioner grafklickar. Bland dem:

Ett nära koncept för kompletta subgrafer är uppdelningen av grafer i kompletta subgrafer och kompletta grafer . I synnerhet Kuratowskis sats och Wagners sats karakteriserar plana grafer genom att förbjuda fullständiga och fullständiga tvådelade subgrafer respektive moll.

Datavetenskap

Inom datavetenskap är klickproblemet  beräkningsproblemet att hitta den maximala klicken eller klicken i en given graf. Problemet är NP-komplett , ett av Karps 21 NP-kompletta problem [9] . Det är också svårt för parametrisk approximation och svårt att approximera . Men många klickalgoritmer har utvecklats som antingen körs i exponentiell tid (som Bron-Kerbosch-algoritmen ) eller som är specialiserade på familjer av grafer, såsom plana grafer eller perfekta grafer , för vilka problemet kan lösas i polynomtid .

Gratis programvara för att hitta den maximala klicken

Nedan finns en lista med gratis programvara för att hitta den maximala klicken.

namn Licens API-språk kort beskrivning
NetworkX BSD Pytonorm ungefärlig lösning, se procedur max_clique  (nedlänk)
maxClique CRAPL Java exakta algoritmer, DIMACS- implementeringar Arkiverad 23 september 2015 på Wayback Machine
öppna opt BSD Pytonorm exakta och ungefärliga lösningar, möjlighet att specificera kanter som ska inkluderas ( MCP )

Applikation

Många olika bioinformatiska problem modelleras med klicker. Till exempel modellerade Ben-Dor, Shamir och Yahini [10] problemet med genuttrycksgruppering som problemet med att hitta det minsta antalet förändringar som behövs för att omvandla en datagraf till en graf som bildas av frånkopplade uppsättningar av klickar. Tanay, Sharan och Shamir [11] diskuterar ett liknande problem med biklustring av genuttrycksdata, där klustren måste vara klicker. Sugihara [12] använde klicker för att modellera ekologiska nischer i livsmedelskedjor . Day och Sankow [13] beskriver problemet med att beskriva evolutionära träd som problemet med att hitta de maximala klicken i en graf där hörn representerar egenskaper och två hörn är förbundna med en kant om det finns en idealisk utvecklingshistoria som kombinerar dessa två egenskaper. Samudrala och Molt [14] modellerade proteinstrukturförutsägelse som ett problem med att hitta klicker i en graf vars hörn representerar positionerna för proteindelar, och genom att leta efter klicker i protein-proteininteraktionsschemat . Spirit och Mirni [15] hittade kluster av proteiner som interagerar nära med varandra och har liten interaktion utanför klustret. Grafkardinalitetsanalys  är en metod för att förenkla komplexa biologiska system genom att hitta klickar och relaterade strukturer i dessa system.

Inom elektroteknik använde Prihar [16] klick för att analysera kommunikationsnätverk, och Paul och Unger [17] använde dem för att utveckla effektiva kretsar för att beräkna delvis definierade booleska funktioner. Klick används också vid automatisk generering av testmönster  - en stor klick i inkompatibilitetsgrafen över möjliga defekter ger en nedre gräns för uppsättningen av tester [18] . Kong och Smith [19] beskriver användningen av klicker för att söka efter hierarkiska strukturer i elektriska kretsar.

Inom kemi använde Rhodes et al [20] klickar för att beskriva kemiska föreningar i en kemisk databas som har en hög grad av likhet. Kuhl, Kripen och Friesen [21] använde klick för att modellera positionerna där två kemiska föreningar binder till varandra.

Se även

Anteckningar

  1. ↑ Erdős, Szekeres, 1935 .
  2. ↑ Tidigare arbete av Kazimir Kuratowski Kuratowski, 1930 om karaktärisering av plana grafer genom att förbjuda fullständiga och fullständiga tvådelade subgrafer är formulerade i topologiska termer snarare än i termer av grafteori
  3. ↑ Luce, Perry, 1949 .
  4. ↑ För ytterligare arbete med att modellera sociala klick med grafteori, se Alba Alba, 1973 , Pius Peay, 1974 och Dorian och Woodard Doreian, Woodard, 1994
  5. ↑ Turán, 1941 .
  6. ↑ Graham, Rothschild, Spencer, 1990 .
  7. ↑ Moon, Moser, 1965 .
  8. ↑ J.-P. Barthelemy, B. Leclerc, B. Monjardet. Om användningen av ordnade uppsättningar i problem med jämförelse och konsensus av klassificeringar // Journal of Classification. - 1986. - T. 3 , nummer. 2 . - S. 200 . - doi : 10.1007/BF01894188 .
  9. ↑ Karp, 1972 .
  10. ↑ Ben-Dor, Shamir, Yakhini, 1999 .
  11. ↑ Tanay, Sharan, Shamir, 2002 .
  12. ↑ Sugihara, 1984 .
  13. ↑ Day, Sankoff, 1986 .
  14. ↑ Samudrala, Moult, 1998 .
  15. ↑ Spirin, Mirny, 2003 .
  16. ↑ Prihar, 1956 .
  17. ↑ Paull, Unger, 1959 .
  18. ↑ I. Hamzaoglu, JH Patel. Proc. 1998 IEEE/ACM internationella konferens om datorstödd design. - 1998. - S. 283-289 . doi : 10.1145 / 288548.288615 .
  19. ↑ Cong, Smith, 1993 .
  20. ↑ Rhodes, Willett, Calvet, Dunbar, Humblet, 2003 .
  21. ↑ Kuhl, Crippen, Friesen, 1983 .

Litteratur

Länkar