Кіріспе
Бағытталмаған графиктің іргелес кіші жиынтығы. Графтар теориясының математикалық саласында клика ('/k//l//iː//k/ немесе '/k//l//ɪ//k/') — бағытталмаған графиктің төбелерінің кіші жиынтығы, онда кликадағы кез келген екі әртүрлі төбе іргелес болады. Яғни, графтың кликасы — оның толық индукцияланған кіші графы. Кликалар — графтар теориясының негізгі ұғымдарының бірі және көптеген басқа математикалық мәселелерде және графтардағы құрылымдарда қолданылады. Кликалар компьютерлік ғылымда да зерттелді: графта белгілі бір мөлшердегі кликаның бар-жоғын анықтау (клика мәселесі) NP-толық, бірақ осы қиындыққа қарамастан, кликаларды табуға арналған көптеген алгоритмдер зерттелді. Толық кіші графтарды зерттеу кем дегенде Рамзи теориясының графтық теориялық тұжырымдамасына дейін жетеді. Ал бұл терминді , әлеуметтік желілерде адамдардың кликаларын модельдеу үшін толық кіші графтарды қолданған , яғни, бір-бірін танитын адамдардың тобынан шыққан. Кликалар ғылымда, әсіресе биоинформатикада көптеген басқа да қолданыстарға ие.
In the mathematical area of graph theory, a clique ('/k//l//iː//k/ or '/k//l//ɪ//k/) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP complete, but despite this hardness result, many algorithms for finding cliques have been studied. Although the study of complete subgraphs goes back at least to the graph theoretic reformulation of Ramsey theory by , the term clique comes from , who used complete subgraphs in social networks to model cliques of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinformatics.
Анықтамалар
Бағытталмаған граф 1=G = (V, E)-дегі C - кликасы, C – V жиынының ішкі жиыны, сондықтан кез келген екі түрлі төбе іргелес болады. Бұл G графигінің C арқылы туындаған ішкі графигі толық граф болатын шартқа тең. Кейбір жағдайларда "клика" термині тікелей ішкі графты білдіруі мүмкін. Максималды клика – бұл тағы бір іргелес төбе қосылу арқылы кеңейтілмейтін клика, яғни үлкен кликаның төбелер жиынында ғана кездеспейтін клика. Кейбір авторлар кликаны максималды болуын міндетті түрде талап етеді және максималды емес толық ішкі графтар үшін басқа терминология қолданады. Графтың G ең үлкен кликасы – бұл одан көп төбесі бар клика жоқ клика. Сонымен қатар, G графигінің клика саны ω(G) – G-дегі ең үлкен кликадағы төбелер саны. G графигінің қиылысу саны – G графигінің барлық қабырғаларын бірге жабатын кликалардың ең кіші саны. G графигінің клика жабу саны – G графигінің төбелер жиыны V-ті жабатын кликалардың ең кіші саны. Графтың ең үлкен клика кесімі – бұл графтың әрбір ең үлкен кликасының кемінде бір төбесін қамтитын төбелердің ішкі жиыны. Кликаның қарама-қарсысы – тәуелсіз жиын, себебі әр клика комплемент графтың тәуелсіз жиынына сәйкес келеді. Кликаны жабу мәселесі – графтың барлық төбелерін қамтитын мүмкіндігінше аз кликаны табуға қатысты. Бұған ұқсас түсінік – биклика, толық екі бөлікті ішкі граф. Графтың екі бөлікті өлшемі – графтың барлық қабырғаларын жабу үшін қажетті бикликалардың ең аз саны.
The intersection number of G is the smallest number of cliques that together cover all edges of G.
The clique cover number of a graph G is the smallest number of cliques of G whose union covers the set of vertices V of the graph. A maximum clique transversal of a graph is a subset of vertices with the property that each maximum clique of the graph contains at least one vertex in the subset. The opposite of a clique is an independent set, in the sense that every clique corresponds to an independent set in the complement graph. The clique cover problem concerns finding as few cliques as possible that include every vertex in the graph. A related concept is a biclique, a complete bipartite subgraph. The bipartite dimension of a graph is the minimum number of bicliques needed to cover all the edges of the graph.
Компьютерлік ғылым
Компьютерлік ғылымда клика мәселесі – берілген графтың ең ірі кликасын немесе барлық кликаларын табудың есептеулік мәселесі. Бұл NP-толық, Карптың 21 NP-толық мәселесінің бірі. Сонымен қатар, бұл мәселені шешу тұрақты параметрлерге тәуелді қиын, және жуықтап табу да қиын. Дегенмен, кликаларды есептеу үшін көптеген алгоритмдер әзірленді, олар экспоненциалды уақытта жұмыс істейді (мысалы, Брон-Кербош алгоритмі) немесе жазық графтар немесе толық графтар сияқты графтар отбасыларына арналған, онда мәселені полиномиалдық уақытта шешуге болады.
Қолданбалар
"Клика" сөзі, оның графтық теориялық қолданылуы, әлеуметтік желілерде кликаларды (бір-бірін танитын адамдар тобы) модельдеу үшін толық субграфтарды қолданған . Осы анықтаманы техникалық емес тілмен мақаласында қолданған. Екі жұмыста да матрицалар арқылы әлеуметтік желідегі кликаларды анықтау қарастырылады. Әлеуметтік кликаларды теориялық тұрғыдан графиктік модельдеуге қатысты жұмыстар үшін, мысалы, , , және қараңыз. Биоинформатика саласынан көптеген мәселелер кликалар арқылы модельденді. Мысалы, ген экспрессиясы деректерін кластерлеу мәселесі, деректерді сипаттайтын графикті кликалардың біріктірілген жиынтығы түріндегі графикке түрлендіру үшін қажетті ең аз өзгерістерді табу ретінде моделіңіз; экспрессиялық деректер үшін ұқсас екі кластерлеу мәселесін талқылаңыз, онда кластерлер кликалар болуы керек. азық тізбегіндегі экологиялық нишаларды модельдеу үшін кликаларды қолданады. Эволюциялық ағаштарды анықтау мәселесін, егер осы екі белгіні біріктіретін толық филогенез болса, онда екі төбесі шетке ие болатын, түрлердің қасиеттері бар графикте ең үлкен кликаны табу мәселесі ретінде сипаттайды. ақуыз құрылымын болжауды, ақуыздың бөліктерінің орналасқан жерлерін көрсететін графикте кликаларды табу мәселесі ретінде модельдейді. Ақуыз-ақуыз өзара әрекеттесу желісінде кликаларды іздеу арқылы бір-бірімен тығыз байланыста болған және кластерден тыс ақуыздармен азаяқ байланыста болған ақуыздардың топтарын тапты. Күш графигін талдау – бұл күрделі биологиялық желілерді осы желілердегі кликалар мен оған байланысты құрылымдарды анықтау арқылы жеңілдету әдісі. Электротехникада байланыс желілерін талдау үшін кликаларды қолданады, ал олар ішінара анықталған Буль функцияларын есептеу үшін тиімді схемаларды жобалау үшін пайдаланады. Кликалар автоматты сынақ үлгісін жасауда да қолданылды: ықтимал ақаулардың қақтығыс графигіндегі үлкен клика, сынақ жинағының мөлшері үшін төменгі шекараны анықтайды. Электрондық схеманы кішігірім бөлімдерге иерархиялық бөлуде кликаларды қолдануды сипаттайды. Химияда, мақсатты құрылыммен жоғары ұқсастығы бар химиялық дерекқордағы химиялық заттарды сипаттау үшін кликаларды қолданады. екі химиялық заттың бір-бірімен байланысатын орындарын модельдеу үшін кликаларды қолданады.
Many different problems from bioinformatics have been modeled using cliques. For instance, model the problem of clustering gene expression data as one of finding the minimum number of changes needed to transform a graph describing the data into a graph formed as the disjoint union of cliques; discuss a similar biclustering problem for expression data in which the clusters are required to be cliques. uses cliques to model ecological niches in food webs. describe the problem of inferring evolutionary trees as one of finding maximum cliques in a graph that has as its vertices characteristics of the species, where two vertices share an edge if there exists a perfect phylogeny combining those two characters. model protein structure prediction as a problem of finding cliques in a graph whose vertices represent positions of subunits of the protein. And by searching for cliques in a protein–protein interaction network, found clusters of proteins that interact closely with each other and have few interactions with proteins outside the cluster. Power graph analysis is a method for simplifying complex biological networks by finding cliques and related structures in these networks. In electrical engineering, uses cliques to analyze communications networks, and use them to design efficient circuits for computing partially specified Boolean functions. Cliques have also been used in automatic test pattern generation: a large clique in an incompatibility graph of possible faults provides a lower bound on the size of a test set. describe an application of cliques in finding a hierarchical partition of an electronic circuit into smaller subunits. In chemistry, use cliques to describe chemicals in a chemical database that have a high degree of similarity with a target structure. use cliques to model the positions in which two chemicals will bind to each other.