Klick (grafteori)

En graf med

23 × 1-vertex klicker (hörn),
42 × 2-vertex klicker (kanterna),
19 × 3-vertex klicker (ljus och mörkblå trianglar), och
2 × 4-vertex klicker (mörkblå områden).

De 11 ljusblå trianglarna bildar maximala klicker. De två mörkblå 4-klickarna är både maximala och maximala, och grafens klicknummer är 4.

I det matematiska området av grafteorin / ) ˈk l ɪk är / en klick ( / ˈk l iːk så att varannan distinkta hörn / eller en delmängd av hörn av en oriktad graf i klicken ligger intill varandra . Det vill säga, en klick av en graf $G$ är en inducerad subgraf av $G$ som är komplett . Klickor är ett av grafteorins grundläggande begrepp och används i många andra matematiska problem och konstruktioner på grafer. Klick har också studerats inom datavetenskap : uppgiften att ta reda på om det finns en klick av en given storlek i en graf (klickproblemet ) är NP-komplett , men trots detta hårdhetsresultat har många algoritmer för att hitta klick studerats.

Även om studiet av kompletta subgrafer går tillbaka åtminstone till den grafteoretiska omformuleringen av Ramsey-teorin av Erdős & Szekeres (1935), kommer termen klick från Luce & Perry (1949), som använde kompletta subgrafer i sociala nätverk för att modellera klicker av människor; det vill säga grupper av människor som alla känner varandra. Klickor har många andra tillämpningar inom vetenskapen och särskilt inom bioinformatik .

Definitioner

En klick , $C$ , i en oriktad graf $G = (V, E)$ är en delmängd av hörnen , $C \subseteq V$ , så att varannan distinkta hörn ligger intill varandra. Detta motsvarar villkoret att den inducerade subgrafen av $G$ inducerad av $C$ är en komplett graf . I vissa fall kan termen klick också referera till subgrafen direkt.

En maximal klick är en klick som inte kan utökas genom att inkludera ytterligare en intilliggande vertex, det vill säga en klick som inte existerar exklusivt inom vertexuppsättningen av en större klick. Vissa författare definierar klickar på ett sätt som kräver att de är maximala, och använder annan terminologi för kompletta subgrafer som inte är maximala.

En maximal klick av en graf, $G$ , är en klick, så att det inte finns någon klick med fler hörn. Dessutom klicktalet $ω (G)$ i en graf $G$ antalet hörn i en maximal klick i $G$ .

Skärningsnumret för $G$ är det minsta antalet klick som tillsammans täcker alla kanter av $G$ .

Klicktäckningsnumret för en graf $G$ är det minsta antalet klicker av $G$ vars förening täcker uppsättningen av hörn V $i$ grafen.

En maximal klicktransversal av en graf är en delmängd av hörn med egenskapen att varje maximal klick i grafen innehåller minst en vertex i delmängden.

Motsatsen till en klick är en oberoende uppsättning , i den meningen att varje klick motsvarar en oberoende uppsättning i komplementgrafen . Klickskyddsproblemet handlar om att hitta så få klick som möjligt som inkluderar varje hörn i grafen .

Ett relaterat koncept är en 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 avseende klick inkluderar följande.

Turáns teorem ger en nedre gräns för storleken på en klick i täta grafer . Om en graf har tillräckligt många kanter måste den innehålla en stor klick. Till exempel, varje graf med $n$ hörn och mer än $\scriptstyle \left\lfloor {\frac {n}{2}}\right\rfloor \cdot \left\lceil {\frac {n}{2}}\right\rceil$ kanter måste innehålla en klick med tre vertex.
Ramseys teorem säger att varje graf eller dess komplementgraf innehåller en klick med åtminstone ett logaritmiskt antal hörn.
Enligt ett resultat av Moon & Moser (1965) kan en graf med 3 n hörn ha högst 3 ⁿ maximala klick. Graferna som möter denna gräns är Mån-Moser-graferna K _3,3,... , ett specialfall av Turán-graferna som uppstår som extremfallen i Turáns sats.
Hadwigers gissning , fortfarande obevisad, relaterar storleken på den största klickmoll i en graf (dess Hadwiger-nummer) till dess kromatiska nummer .
Erdős –Faber–Lovász gissningar är ett annat obevisat uttalande som relaterar graffärgning till klicker.

Flera viktiga klasser av grafer kan definieras eller karakteriseras av sina klickar:

En klustergraf är en graf vars anslutna komponenter är klickar.
En blockgraf är en graf vars dubbelkopplade komponenter är klickar.
En ackordsgraf är en graf vars hörn kan ordnas i en perfekt elimineringsordning, en ordning sådan att grannarna till varje vertex v som kommer senare än v i ordningen bildar en klick.
En kograf är en graf vars alla inducerade subgrafer har egenskapen att vilken maximal klick som helst skär en maximal oberoende uppsättning i en enda vertex.
En intervallgraf är en graf vars maximala klick kan ordnas på ett sådant sätt att, för varje vertex v , de klickar som innehåller v är konsekutiva i ordningen.
En linjegraf är en graf vars kanter kan täckas av kant-disjunkta klicker på ett sådant sätt att varje vertex tillhör exakt två av klicken i omslaget.
En perfekt graf är en graf där klicknumret är lika med det kromatiska talet i varje inducerad subgraf .
En delad graf är en graf där någon klick innehåller minst en ändpunkt av varje kant.
En triangelfri graf är en graf som inte har några andra klick än sina hörn och kanter.

Dessutom involverar många andra matematiska konstruktioner klickar i grafer. Bland dem,

Klickkomplexet i en graf G är ett abstrakt förenklat komplex X ( G ) med ett simplex för varje klick i G
En simplexgraf är en oriktad graf κ( G ) med en vertex för varje klick i en graf G och en kant som förbinder två klicker som skiljer sig åt med en enda vertex. Det är ett exempel på mediangraf , och är associerad med en medianalgebra på klickarna i en graf: medianen m ( A , B , C ) för tre klick A , B och C är klicken vars hörn tillhör åtminstone två av klicken A , B och C.
Klicksumman är en metod för att kombinera två grafer genom att slå samman dem längs en delad klick .
Klickbredd är en uppfattning om komplexiteten hos en graf i termer av det minsta antalet distinkta hörnetiketter som behövs för att bygga upp grafen från disjunkta kopplingar, ommärkningsoperationer och operationer som förbinder alla par av hörn med givna etiketter. Graferna med en klickbredd är exakt de osammanhängande föreningarna av klick.
Skärningsnumret för en graf är det minsta antal klick som behövs för att täcka alla grafens kanter.
Klickdiagrammet för en graf är skärningsdiagrammet för dess maximala klick .

Närbesläktade begrepp till kompletta subgrafer är underavdelningar av kompletta grafer och kompletta grafer . I synnerhet Kuratowskis sats och Wagners sats karaktäriserar plana grafer genom förbjudna fullständiga och fullständiga tvådelade underavdelningar respektive moll.

Datavetenskap

Inom datavetenskap är klickproblemet beräkningsproblemet att hitta en maximal klick, eller alla klick, i en given graf . Det är NP-komplett , ett av Karps 21 NP-komplett problem . Den är också svårbehandlad med fasta parametrar och svår att uppskatta . Ändå har många algoritmer för beräkning av klick utvecklats, antingen körs i exponentiell tid (som Bron–Kerbosch-algoritmen ) eller specialiserade för att grafa familjer som plana grafer eller perfekta grafer för vilka problemet kan lösas i polynomtid .

Ansökningar

Ordet "klick", i dess grafteoretiska användning, uppstod från arbetet av Luce & Perry (1949), som använde kompletta subgrafer för att modellera klicker (grupper av människor som alla känner varandra) i sociala nätverk . Samma definition användes av Festinger (1949) i en artikel med mindre tekniska termer. Båda verken handlar om att avslöja klickar i ett socialt nätverk med hjälp av matriser. För fortsatta ansträngningar att modellera sociala klicker grafteoretiskt, se t.ex. Alba (1973) , Peay (1974) och Doreian & Woodard (1994) .

Många olika problem från bioinformatik har modellerats med hjälp av klick. Till exempel Ben-Dor, Shamir & Yakhini (1999) problemet med att gruppera genuttrycksdata som ett av att hitta det minsta antalet förändringar som behövs för att transformera en graf som beskriver data till en graf bildad som den osammanhängande föreningen av klicker; Tanay, Sharan & Shamir (2002) diskuterar ett liknande biklustringsproblem för uttrycksdata där klustren måste vara klicker. Sugihara (1984) använder klicker för att modellera ekologiska nischer i näringsvävar . Day & Sankoff (1986) beskriver problemet med att sluta sig till evolutionära träd som ett av att hitta maximala klick i en graf som har som sina hörn egenskaper hos arten, där två hörn delar en kant om det finns en perfekt fylogeni som kombinerar dessa två karaktärer. Samudrala & Moult (1998) modellerar förutsägelse av proteinstruktur som ett problem med att hitta klicker i en graf vars hörn representerar positioner för underenheter av proteinet. Och genom att söka efter klicker i ett protein-proteininteraktionsnätverk hittade Spirin & Mirny (2003) kluster av proteiner som interagerar nära med varandra och har få interaktioner med proteiner utanför klustret. Effektgrafanalys är en metod för att förenkla komplexa biologiska nätverk genom att hitta klickar och relaterade strukturer i dessa nätverk.

Inom elektroteknik använder Prihar (1956) klicker för att analysera kommunikationsnätverk, och Paull & Unger (1959) använder dem för att designa effektiva kretsar för att beräkna delvis specificerade booleska funktioner. Klickor har också använts vid automatisk generering av testmönster : en stor klick i en inkompatibilitetsgraf över möjliga fel ger en nedre gräns för storleken på en testuppsättning. Cong & Smith (1993) beskriver en tillämpning av klickar för att hitta en hierarkisk uppdelning av en elektronisk krets i mindre underenheter.

Inom kemi , Rhodes et al. (2003) använder klick för att beskriva kemikalier i en kemikaliedatabas som har en hög grad av likhet med en målstruktur. Kuhl, Crippen & Friesen (1983) använder klick för att modellera positionerna där två kemikalier kommer att binda till varandra.

Se även

Klickspel

Anteckningar

Alba, Richard D. (1973), "A graph-theoretic definition of a sociometric clique" (PDF) , Journal of Mathematical Sociology , 3 (1): 113–126, doi : 10.1080/0022250X.1973.9989826 ( , PDF) archived (, från originalet 2011-05-03 , hämtat 2009-12-14 .
Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "On the use of ordered sets in problems of comparison and consensus of classifications", Journal of Classification , 3 (2): 187–224, doi : 10.1007/BF01894188 , S2CID 6092438 .
Ben-Dor, Amir; Shamir, Ron; Yakhini, Zohar (1999), "Clustering gene expression patterns.", Journal of Computational Biology , 6 ( 3–4): 281–297, CiteSeerX 10.1.1.34.5341 , doi : 10.1089/10665279903182761 , 5PM2761 .
Chang, Maw-Shang; Kloks, Ton; Lee, Chuan-Min (2001), "Maximum clique transversals", Grafteoretiska begrepp inom datavetenskap (Boltenhagen, 2001) , Lecture Notes in Comput. Sci., vol. 2204, Springer, Berlin, s. 32–43, doi : 10.1007/3-540-45477-2_5 , ISBN 978-3-540-42707-0 , MR 1905299 .
Cong, J.; Smith, M. (1993), "En parallell bottom-up-klustringsalgoritm med tillämpningar för kretspartitionering i VLSI-design", Proc. 30th International Design Automation Conference , s. 755–760, CiteSeerX 10.1.1.32.735 , doi : 10.1145/157485.165119 , ISBN 978-0897915779 , S525ID 52 .
Day, William HE; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility", Systematic Zoology , 35 (2): 224–229, doi : 10.2307/2413432 , JSTOR 2413432 .
Doreian, Patrick; Woodard, Katherine L. (1994), "Defining and locating cores and boundaries of social networks", Social Networks , 16 (4): 267–293, doi : 10.1016/0378-8733(94)90013-2 .
Erdős, Paul ; Szekeres, George (1935), "A combinatorial problem in geometry" (PDF) , Compositio Mathematica , 2 : 463–470, arkiverad (PDF) från originalet 2020-05-22 , hämtad 2009-12-19 .
Festinger, Leon (1949), "The analysis of sociograms using matrix algebra", Human Relations , 2 (2): 153–158, doi : 10.1177/001872674900200205 , S2CID 143609308 .
Graham, R .; Rothschild, B.; Spencer, JH (1990), Ramsey Theory , New York: John Wiley and Sons, ISBN 978-0-471-50046-9 .
Hamzaoglu, I.; Patel, JH (1998), "Testuppsättningskomprimeringsalgoritmer för kombinationskretsar", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design , s. 283–289, doi : 10.1145/288548.288615 , ISBN 978-1581130089 , S2CID 12258606 .
Karp, Richard M. (1972), "Reducibility among combinatorial problems", i Miller, RE; Thatcher, JW (red.), Complexity of Computer Computations (PDF) , New York: Plenum, s. 85–103, arkiverad från originalet (PDF) 2011-06-29 , hämtad 2009-12-13 .
Kuhl, FS; Crippen, GM; Friesen, DK (1983), "A combinatorial algorithm for calculating ligand binding", Journal of Computational Chemistry , 5 (1): 24–34, doi : 10.1002/jcc.540050105 , S2CID 122923018 .
Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en Topologie" (PDF) , Fundamenta Mathematicae (på franska), 15 : 271–283, doi : 10.4064/fm-15-1-271-283 ( , 283 ) PDF) från originalet 2018-07-23 , hämtat 2009-12-19 .
Luce, R. Duncan ; Perry, Albert D. (1949), " A method of matrix analysis of group structure", Psychometrika , 14 ( 2): 95–116, doi : 10.1007 /BF02289146 , hdl : 10.1007 / BF02289146 , 812ID .
Moon, JW; Moser, L. (1965), "On cliques in graphs", Israel Journal of Mathematics , 3 : 23–28, doi : 10.1007/BF02760024 , MR 0182577 .
Paull, MC; Unger, SH (1959), "Minimering av antalet tillstånd i ofullständigt specificerade sekventiella omkopplingsfunktioner", IRE Transactions on Electronic Computers , EC-8 (3): 356–367, doi : 10.1109/TEC.1959.5222697 .
Peay, Edmund R. (1974), "Hierarchical clique structures", Sociometri , 37 (1): 54–65, doi : 10.2307/2786466 , JSTOR 2786466 .
Prihar, Z. (1956), "Topologiska egenskaper hos telekommunikationsnätverk", Proceedings of the IRE , 44 (7): 927–933, doi : 10.1109/JRPROC.1956.275149 , S2CID 51654879 .
Rhodos, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: likhetssökning av 3D-databaser med hjälp av klickdetektion", Journal of Chemical Information and Computer Sciences , 43 ( 2): 443–448, doi : 10.1021/ci025605o , PMID 12653507 .
Samudrala, Ram; Moult, John (1998), "A graph-theoretic algorithm for comparative modeling of protein structure", Journal of Molecular Biology , 279 (1): 287–302, CiteSeerX 10.1.1.64.8918 , doi : 10.1006/jmbi . PMID 9636717 .
Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks", Proceedings of the National Academy of Sciences , 100 ( 21): 12123–12128, doi : 10.1073 /pnas.2032324100 , PMC 5 , 7232 5 .
Sugihara, George (1984), "Graph theory, homology and food webs", i Levin, Simon A. (red.), Population Biology , Proc. Symp. Appl. Math., vol. 30, s. 83–101 .
Tanay, Amos; Sharan, Roded; Shamir, Ron (2002), "Discovering statisticly significant biclusters in gene expression data", Bioinformatics , 18 (Suppl. 1): S136–S144, doi : 10.1093/bioinformatics/18.suppl_1.S136 , PM5ID 4116 .
Turán, Paul (1941), "Om ett extremt problem i grafteorin", Matematikai és Fizikai Lapok (på ungerska), 48 : 436–452

externa länkar

Weisstein, Eric W. , "Clique" , MathWorld
Weisstein, Eric W. , "Clique Number" , MathWorld