Clique (grafteori) - Clique (graph theory)

En graf med

• 23 × 1-vertex-klick (hörnen),
• 42 × 2-vertex-klickar (kanterna),
• 19 × 3-vertex-klickar (ljusa och mörkblå trianglar) och
• 2 × 4-vertex-klickar (mörkblå områden).

De 11 ljusblå trianglarna bildar maximala klickningar. De två mörkblå 4-klickarna är både maximala och maximala, och klickantalet i grafen är 4.

I matematisk yta på grafteori , en klick ( / k l Î k / eller / k l ɪ k / ) är en delmängd av hörn i en oriktad graf så att varje två distinkta hörn i klicken ligger intill varandra. Det vill säga en klick av en graf är en inducerad subgraf av det som är komplett . Cliques är ett av de grundläggande begreppen inom grafteori och används i många andra matematiska problem och konstruktioner på grafer. Cliques har också studerats inom datavetenskap : uppgiften att hitta om det finns en klick av en viss storlek i ett diagram ( klickproblemet ) är NP-komplett , men trots detta hårdhetsresultat har många algoritmer för att hitta klickor studerats. ${\ displaystyle G}$${\ displaystyle G}$

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

Definitioner

En klick , i en oriktad graf är en delmängd av de vertex , så att varje två distinkta hörn angränsar. Detta motsvarar villkoret att den inducerade subgrafen för inducerad av är en fullständig graf . I vissa fall kan termen klick också hänvisa till subgrafen direkt. ${\ displaystyle C}$ ${\ displaystyle G = (V, E)}$${\ displaystyle C \ subseteq V}$${\ displaystyle G}$${\ displaystyle C}$

En maximal klick är en klick som inte kan förlängas genom att inkludera ytterligare en intilliggande hörnpunkt, det vill säga en klick som inte existerar exklusivt inom hörnuppsättningen av en större klick. Vissa författare definierar klickningar 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 på en graf,, är en klick, så att det inte finns någon klick med fler hörn. Dessutom är klickantalet i en graf antalet hörn i en maximal klick in . ${\ displaystyle G}$ ${\ displaystyle \ omega (G)}$${\ displaystyle G}$${\ displaystyle G}$

Den skärnings nummer av är det minsta antalet gäng som tillsammans täcker alla kanter . ${\ displaystyle G}$${\ displaystyle G}$

Den klick täcka antal av ett diagram är det minsta antalet gäng av vars union täcker uppsättningen hörn av grafen. ${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle V}$

En maximal klick transversal av en graf är en delmängd av hörn med egenskapen att varje maximal klick i grafen innehåller minst en toppunkt 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 . De Clique täcka problem oro hitta så få gäng som möjligt som inkluderar varje hörn i grafen.

Ett relaterat koncept är en biclique , en komplett bipartit subgraf . Den tvådelade dimension av ett diagram är det minsta antalet bicliques som behövs för att täcka alla kanter i grafen.

Matematik

Matematiska resultat avseende klickor inkluderar följande.

• Turáns sats 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 måste varje graf med hörn och mer än kanter innehålla en klick med tre hörn.${\ displaystyle n}$${\ displaystyle \ scriptstyle \ lfloor {\ frac {n} {2}} \ rfloor \ cdot \ lceil {\ frac {n} {2}} \ rceil}$
• Ramseys sats säger att varje graf eller dess komplementgraf innehåller en klick med minst 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 klickningar. Graferna som möter denna gräns är Moon -Moser -graferna K _{3,3, ...} , ett specialfall av Turán -graferna som uppstår som extrema fall i Turáns sats.
• Hadwiger förmodan , fortfarande oprövad avser storleken på den största clique moll i en graf (dess Hadwiger nummer ) till dess kromatiska nummer .
• Den Erdős-Faber-Lovasz gissningar är en annan oprövad förklaring om graffärg till klick.

Flera viktiga klasser av grafer kan definieras eller kännetecknas av deras klickningar:

• Ett klusterdiagram är en graf vars anslutna komponenter är klickar.
• Ett blockdiagram är ett diagram vars sammankopplade komponenter är klickningar.
• En ackordgraf är en graf vars hörn kan ordnas till en perfekt elimineringsordning, en ordning så att grannarna till varje hörn v som kommer senare än v i ordningen bildar en klick.
• En cograph är en graf vars alla inducerade subgrafer har egenskapen att varje maximal klick skär varje maximal oberoende uppsättning i en enda toppunkt.
• Ett intervalldiagram är en graf vars maximala klick kan ordnas på ett sådant sätt att för varje hörn v , de klick som innehåller v är på varandra följande i ordningen.
• Ett linjediagram är ett diagram vars kanter kan täckas av kantdelade klickar på ett sådant sätt att varje hörn hör till exakt två av klickarna i omslaget.
• En perfekt graf är en graf där klickantalet är lika med det kromatiska talet i varje inducerad delgraf .
• Ett delat diagram är ett diagram där någon klick innehåller minst en slutpunkt för varje kant.
• En triangelfri graf är en graf som inte har några andra klick än dess hörn och kanter.

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

• Den klick komplex av en graf G är en abstrakt simplicial komplex X ( G ) med en simplex för varje klick i G
• Ett simplexdiagram är ett oriktat diagram κ ( G ) med en toppunkt för varje klick i en graf G och en kant som förbinder två klick som skiljer sig med en enda toppunkt. Det är ett exempel på mediangraf och är associerat med en medianalgebra på grafikens klick: medianen m ( A , B , C ) för tre klick A , B och C är den klick vars hörn hör till åtminstone två av klickarna A , B , och C .
• Den klick-summan är en metod för att kombinera två grafer genom att slå samman dem längs en delad klick.
• Clique-width är en föreställning om komplexiteten hos en graf när det gäller det minsta antalet distinkta hörnetiketter som behövs för att bygga upp grafen från sammanfogade fackföreningar, ommärkning och operationer som förbinder alla par hörnpar med givna etiketter. Graferna med klickbredd ett är exakt de olikartade fackföreningarna för klickningar.
• Den skärnings antal av ett diagram är det minsta antalet gäng som behövs för att täcka alla diagrammets kanter.
• Den klicken grafen av en graf är skärnings grafen av dess maximala klick.

Närbesläktade begrepp för att slutföra undergrafer är underavdelningar av kompletta grafer och kompletta grafer . I synnerhet karakteriserar Kuratowskis sats och Wagners sats plana grafer av förbjudna fullständiga och fullständiga tvåpartsindelningar respektive minderåriga.

Datavetenskap

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

Ansökningar

Ordet "klick", i sin grafteoretiska användning, härstammade från arbetet av Luce & Perry (1949) , som använde kompletta subgrafer för att modellera klickningar (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 klickningar 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 klickar. Exempelvis modellerar Ben-Dor, Shamir & Yakhini (1999) problemet med att klustera genuttrycksdata som ett av att hitta det minsta antal förändringar som behövs för att omvandla en graf som beskriver data till en graf som bildas som en oenig förening av klick; Tanay, Sharan & Shamir (2002) diskuterar ett liknande biklusteringsproblem för uttrycksdata där klustren måste vara klickar. Sugihara (1984) använder klickar för att modellera ekologiska nischer i livsmedelsbanor . Day & Sankoff (1986) beskriver problemet med att dra slutsatser om evolutionära träd som att hitta maximala klickningar i en graf som har dess hörnkarakteristik för arten, där två hörn delar en kant om det finns en perfekt fylogeni som kombinerar dessa två tecken. Samudrala & Moult (1998) modellerar proteinstrukturprognoser som ett problem med att hitta klickningar i en graf vars hörn representerar positioner för proteinets subenheter. Och genom att söka efter klickar i ett protein-protein-interaktionsnä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 klickningar och relaterade strukturer i dessa nätverk.

I elektroteknik , Prihar (1956) använder klick att analysera kommunikationsnät och Paull & Unger (1959) använda dem för att utforma effektiva kretsar för beräkning delvis angivna Boolean funktioner. Cliques har också använts vid automatisk testmönstergenerering : 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 klick för att hitta en hierarkisk uppdelning av en elektronisk krets i mindre underenheter.

Inom kemi har Rhodes et al. (2003) använder klick för att beskriva kemikalier i en kemisk databas 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

Referenser

externa länkar

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