. "1175666"^^ . "Kograf (ang. cograph, P4-free graph) \u2013 graf, kt\u00F3ry mo\u017Cna zbudowa\u0107 z pojedynczych wierzcho\u0142k\u00F3w za pomoc\u0105 operacji oraz . Z\u0142\u0105czenie graf\u00F3w G i F to graf powsta\u0142y poprzez po\u0142\u0105czenie wszystkich wierzcho\u0142k\u00F3w grafu G z wszystkimi wierzcho\u0142kami grafu F, przy zachowaniu wewn\u0119trznej budowy graf\u00F3w G i F. Natomiast operacja sumy graf\u00F3w to zwyk\u0142e sumowanie zbior\u00F3w kraw\u0119dzi i wierzcho\u0142k\u00F3w. Kografy mo\u017Cna wygodnie reprezentowa\u0107 za pomoc\u0105 (ang. cotree), kt\u00F3rego li\u015B\u0107mi s\u0105 wierzcho\u0142ki graf\u00F3w, natomiast w\u0119z\u0142y wewn\u0119trzne drzewa reprezentuj\u0105 operacj\u0119 z\u0142\u0105czenia (1) i sumowania (0)."@pl . . . . . "Kograf (ang. cograph, P4-free graph) \u2013 graf, kt\u00F3ry mo\u017Cna zbudowa\u0107 z pojedynczych wierzcho\u0142k\u00F3w za pomoc\u0105 operacji oraz . Z\u0142\u0105czenie graf\u00F3w G i F to graf powsta\u0142y poprzez po\u0142\u0105czenie wszystkich wierzcho\u0142k\u00F3w grafu G z wszystkimi wierzcho\u0142kami grafu F, przy zachowaniu wewn\u0119trznej budowy graf\u00F3w G i F. Natomiast operacja sumy graf\u00F3w to zwyk\u0142e sumowanie zbior\u00F3w kraw\u0119dzi i wierzcho\u0142k\u00F3w. Kografy mo\u017Cna wygodnie reprezentowa\u0107 za pomoc\u0105 (ang. cotree), kt\u00F3rego li\u015B\u0107mi s\u0105 wierzcho\u0142ki graf\u00F3w, natomiast w\u0119z\u0142y wewn\u0119trzne drzewa reprezentuj\u0105 operacj\u0119 z\u0142\u0105czenia (1) i sumowania (0)."@pl . . "\u041A\u043E\u0433\u0440\u0430\u0444"@uk . . . . . . . . . . . . . . . . . . . "Cograph"@en . . . . "Cograph"@en . . . . . . . . . . "cs2"@en . . . . . . . "\u0412 \u0442\u0435\u043E\u0440\u0456\u0457 \u0433\u0440\u0430\u0444\u0456\u0432 \u043A\u043E\u0433\u0440\u0430\u0444, \u0430\u0431\u043E \u0434\u043E\u0434\u0430\u0442\u043A\u043E\u0432\u043E \u0437\u0432\u0456\u0434\u043D\u0438\u0439 \u0433\u0440\u0430\u0444, \u0447\u0438 \u0433\u0440\u0430\u0444, \u0432\u0456\u043B\u044C\u043D\u0438\u0439 \u0432\u0456\u0434 P4, \u2014 \u0446\u0435 \u0433\u0440\u0430\u0444, \u044F\u043A\u0438\u0439 \u043C\u043E\u0436\u043D\u0430 \u043E\u0442\u0440\u0438\u043C\u0430\u0442\u0438 \u0437 \u0433\u0440\u0430\u0444\u0430 \u0437 \u0454\u0434\u0438\u043D\u043E\u044E \u0432\u0435\u0440\u0448\u0438\u043D\u043E\u044E K1 \u043E\u043F\u0435\u0440\u0430\u0446\u0456\u044F\u043C\u0438 \u0434\u043E\u043F\u043E\u0432\u043D\u0435\u043D\u043D\u044F \u0442\u0430 \u043E\u0431'\u0454\u0434\u043D\u0430\u043D\u043D\u044F \u0433\u0440\u0430\u0444\u0456\u0432. \u0422\u0430\u043A\u0438\u043C \u0447\u0438\u043D\u043E\u043C, \u0441\u0456\u043C\u0435\u0439\u0441\u0442\u0432\u043E \u043A\u043E\u0433\u0440\u0430\u0444\u0456\u0432 \u2014 \u0446\u0435 \u043D\u0430\u0439\u043C\u0435\u043D\u0448\u0438\u0439 \u043A\u043B\u0430\u0441 \u0433\u0440\u0430\u0444\u0456\u0432, \u0449\u043E \u043C\u0456\u0441\u0442\u0438\u0442\u044C K1 \u0456 \u0437\u0430\u043C\u043A\u043D\u0443\u0442\u0438\u0439 \u0432\u0456\u0434\u043D\u043E\u0441\u043D\u043E \u0434\u043E\u043F\u043E\u0432\u043D\u0435\u043D\u043D\u044F \u0442\u0430 \u043E\u0431'\u0454\u0434\u043D\u0430\u043D\u043D\u044F. \u0412 \u043A\u043D\u0438\u0437\u0456 \u0411\u0440\u0430\u043D\u0434\u0448\u0442\u0435\u0434\u0442\u0430, \u041B\u0456 \u0456 \u0428\u043F\u0456\u043D\u0440\u0430\u0434\u0430 \u043A\u043E\u0433\u0440\u0430\u0444\u0438 \u0440\u043E\u0437\u0433\u043B\u044F\u043D\u0443\u0442\u043E \u0434\u0435\u0442\u0430\u043B\u044C\u043D\u0456\u0448\u0435, \u0432\u043A\u043B\u044E\u0447\u043D\u043E \u0437 \u0444\u0430\u043A\u0442\u0430\u043C\u0438, \u043D\u0430\u0432\u0435\u0434\u0435\u043D\u0438\u043C\u0438 \u0442\u0443\u0442."@uk . . "1110999582"^^ . "\u0412 \u0442\u0435\u043E\u0440\u0456\u0457 \u0433\u0440\u0430\u0444\u0456\u0432 \u043A\u043E\u0433\u0440\u0430\u0444, \u0430\u0431\u043E \u0434\u043E\u0434\u0430\u0442\u043A\u043E\u0432\u043E \u0437\u0432\u0456\u0434\u043D\u0438\u0439 \u0433\u0440\u0430\u0444, \u0447\u0438 \u0433\u0440\u0430\u0444, \u0432\u0456\u043B\u044C\u043D\u0438\u0439 \u0432\u0456\u0434 P4, \u2014 \u0446\u0435 \u0433\u0440\u0430\u0444, \u044F\u043A\u0438\u0439 \u043C\u043E\u0436\u043D\u0430 \u043E\u0442\u0440\u0438\u043C\u0430\u0442\u0438 \u0437 \u0433\u0440\u0430\u0444\u0430 \u0437 \u0454\u0434\u0438\u043D\u043E\u044E \u0432\u0435\u0440\u0448\u0438\u043D\u043E\u044E K1 \u043E\u043F\u0435\u0440\u0430\u0446\u0456\u044F\u043C\u0438 \u0434\u043E\u043F\u043E\u0432\u043D\u0435\u043D\u043D\u044F \u0442\u0430 \u043E\u0431'\u0454\u0434\u043D\u0430\u043D\u043D\u044F \u0433\u0440\u0430\u0444\u0456\u0432. \u0422\u0430\u043A\u0438\u043C \u0447\u0438\u043D\u043E\u043C, \u0441\u0456\u043C\u0435\u0439\u0441\u0442\u0432\u043E \u043A\u043E\u0433\u0440\u0430\u0444\u0456\u0432 \u2014 \u0446\u0435 \u043D\u0430\u0439\u043C\u0435\u043D\u0448\u0438\u0439 \u043A\u043B\u0430\u0441 \u0433\u0440\u0430\u0444\u0456\u0432, \u0449\u043E \u043C\u0456\u0441\u0442\u0438\u0442\u044C K1 \u0456 \u0437\u0430\u043C\u043A\u043D\u0443\u0442\u0438\u0439 \u0432\u0456\u0434\u043D\u043E\u0441\u043D\u043E \u0434\u043E\u043F\u043E\u0432\u043D\u0435\u043D\u043D\u044F \u0442\u0430 \u043E\u0431'\u0454\u0434\u043D\u0430\u043D\u043D\u044F. \u041A\u043E\u0433\u0440\u0430\u0444\u0438 \u0432\u0456\u0434\u043A\u0440\u0438\u0432\u0430\u043B\u0438 \u043D\u0435\u0437\u0430\u043B\u0435\u0436\u043D\u043E \u043A\u0456\u043B\u044C\u043A\u0430 \u0430\u0432\u0442\u043E\u0440\u0456\u0432, \u043F\u043E\u0447\u0438\u043D\u0430\u044E\u0447\u0438 \u0432\u0456\u0434 1970-\u0445 \u0440\u043E\u043A\u0456\u0432. \u041D\u0430\u0439\u0440\u0430\u043D\u0456\u0448\u0456 \u0437\u0433\u0430\u0434\u043A\u0438 \u043C\u043E\u0436\u043D\u0430 \u0437\u043D\u0430\u0439\u0442\u0438 \u0443 \u042F\u043D\u0433\u0430, \u041B\u0435\u0440\u0447\u0441\u0430, \u0417\u0430\u0439\u043D\u0448\u0435 \u0456 . \u0426\u0456 \u0433\u0440\u0430\u0444\u0438 \u043D\u0430\u0437\u0438\u0432\u0430\u043B\u0438 D*-\u0433\u0440\u0430\u0444\u0430\u043C\u0438, \u0441\u043F\u0430\u0434\u043A\u043E\u0432\u0438\u043C\u0438 \u0433\u0440\u0430\u0444\u0430\u043C\u0438 \u0414\u0435\u0439\u0441\u0456 (\u043F\u0456\u0441\u043B\u044F \u0440\u043E\u0431\u043E\u0442\u0438 \u0414\u0436\u0435\u0439\u043C\u0441\u0430 \u0414\u0435\u0439\u0441\u0456 (James C. Dacey, Jr.) \u043F\u0440\u043E . \u0414\u0438\u0432. \u0440\u043E\u0431\u043E\u0442\u0443 \u0421\u0430\u043C\u043D\u0435\u0440\u0430) \u0442\u0430 \u0433\u0440\u0430\u0444\u0438 \u0437 \u0434\u0432\u043E\u043C\u0430 \u043D\u0430\u0449\u0430\u0434\u043A\u0430\u043C\u0438 \u0411\u0430\u0440\u043B\u0435\u0442\u0430 \u0456 \u0423\u0440\u0456. \u0412 \u043A\u043D\u0438\u0437\u0456 \u0411\u0440\u0430\u043D\u0434\u0448\u0442\u0435\u0434\u0442\u0430, \u041B\u0456 \u0456 \u0428\u043F\u0456\u043D\u0440\u0430\u0434\u0430 \u043A\u043E\u0433\u0440\u0430\u0444\u0438 \u0440\u043E\u0437\u0433\u043B\u044F\u043D\u0443\u0442\u043E \u0434\u0435\u0442\u0430\u043B\u044C\u043D\u0456\u0448\u0435, \u0432\u043A\u043B\u044E\u0447\u043D\u043E \u0437 \u0444\u0430\u043A\u0442\u0430\u043C\u0438, \u043D\u0430\u0432\u0435\u0434\u0435\u043D\u0438\u043C\u0438 \u0442\u0443\u0442."@uk . . . "In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union. Cographs have been discovered independently by several authors since the 1970s; early references include , , , and . They have also been called D*-graphs, hereditary Dacey graphs (after the related work of James C. Dacey Jr. on orthomodular lattices), and 2-parity graphs.They have a simple structural decomposition involving disjoint union and complement graph operations that can be represented concisely by a labeled tree, and used algorithmically to efficiently solve many problems such as finding the maximum clique that are hard on more general graph classes. Special cases of the cographs include the complete graphs, complete bipartite graphs, cluster graphs, and threshold graphs. The cographs are, in turn, special cases of the distance-hereditary graphs, permutation graphs, comparability graphs, and perfect graphs."@en . . . . "Co-Graph"@de . . . . . "In der Informatik ist ein Co-Graph ein ungerichteter Graph , welcher sich mit bestimmten elementaren Operationen konstruieren l\u00E4sst. Auf Co-Graphen lassen sich viele schwere Probleme wie z. B. CLIQUE und das damit eng verwandte UNABH\u00C4NGIGE MENGE sowie KNOTEN\u00DCBERDECKUNG in Linearzeit l\u00F6sen."@de . . "In der Informatik ist ein Co-Graph ein ungerichteter Graph , welcher sich mit bestimmten elementaren Operationen konstruieren l\u00E4sst. Auf Co-Graphen lassen sich viele schwere Probleme wie z. B. CLIQUE und das damit eng verwandte UNABH\u00C4NGIGE MENGE sowie KNOTEN\u00DCBERDECKUNG in Linearzeit l\u00F6sen."@de . . . . . . . "\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0433\u0440\u0430\u0444\u043E\u0432 \u043A\u043E\u0433\u0440\u0430\u0444, \u0438\u043B\u0438 \u0434\u043E\u043F\u043E\u043B\u043D\u0438\u0442\u0435\u043B\u044C\u043D\u043E \u0441\u0432\u043E\u0434\u0438\u043C\u044B\u0439 \u0433\u0440\u0430\u0444, \u0438\u043B\u0438 \u0433\u0440\u0430\u0444, \u0441\u0432\u043E\u0431\u043E\u0434\u043D\u044B\u0439 \u043E\u0442 P4, \u2014 \u044D\u0442\u043E \u0433\u0440\u0430\u0444, \u043A\u043E\u0442\u043E\u0440\u044B\u0439 \u043C\u043E\u0436\u043D\u043E \u043F\u043E\u043B\u0443\u0447\u0438\u0442\u044C \u0438\u0437 \u0433\u0440\u0430\u0444\u0430 \u0441 \u0435\u0434\u0438\u043D\u0441\u0442\u0432\u0435\u043D\u043D\u043E\u0439 \u0432\u0435\u0440\u0448\u0438\u043D\u043E\u0439 K1 \u043F\u0443\u0442\u0451\u043C \u043E\u043F\u0435\u0440\u0430\u0446\u0438\u0439 \u0434\u043E\u043F\u043E\u043B\u043D\u0435\u043D\u0438\u044F \u0438 \u043E\u0431\u044A\u0435\u0434\u0438\u043D\u0435\u043D\u0438\u044F \u0433\u0440\u0430\u0444\u043E\u0432. \u0422\u0430\u043A\u0438\u043C \u043E\u0431\u0440\u0430\u0437\u043E\u043C, \u0441\u0435\u043C\u0435\u0439\u0441\u0442\u0432\u043E \u043A\u043E\u0433\u0440\u0430\u0444\u043E\u0432 \u2014 \u044D\u0442\u043E \u043D\u0430\u0438\u043C\u0435\u043D\u044C\u0448\u0438\u0439 \u043A\u043B\u0430\u0441\u0441 \u0433\u0440\u0430\u0444\u043E\u0432, \u0441\u043E\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 K1 \u0438 \u0437\u0430\u043C\u043A\u043D\u0443\u0442\u044B\u0439 \u043E\u0442\u043D\u043E\u0441\u0438\u0442\u0435\u043B\u044C\u043D\u043E \u0434\u043E\u043F\u043E\u043B\u043D\u0435\u043D\u0438\u044F \u0438 \u043E\u0431\u044A\u0435\u0434\u0438\u043D\u0435\u043D\u0438\u044F. \u041A\u043E\u0433\u0440\u0430\u0444\u044B \u043E\u0442\u043A\u0440\u044B\u0432\u0430\u043B\u0438\u0441\u044C \u043D\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043C\u043E \u043D\u0435\u0441\u043A\u043E\u043B\u044C\u043A\u0438\u043C\u0438 \u0430\u0432\u0442\u043E\u0440\u0430\u043C\u0438, \u043D\u0430\u0447\u0438\u043D\u0430\u044F \u0441 1970-\u0445 \u0433\u043E\u0434\u043E\u0432. \u0421\u0430\u043C\u044B\u0435 \u0440\u0430\u043D\u043D\u0438\u0435 \u0443\u043F\u043E\u043C\u0438\u043D\u0430\u043D\u0438\u044F \u043C\u043E\u0436\u043D\u043E \u043D\u0430\u0439\u0442\u0438 \u0443 \u042F\u043D\u0433\u0430, \u041B\u0435\u0440\u0447\u0441\u0430, \u0417\u0430\u0439\u043D\u0448\u0435 \u0438 \u0421\u0430\u043C\u043D\u0435\u0440\u0430. \u042D\u0442\u0438 \u0433\u0440\u0430\u0444\u044B \u043D\u0430\u0437\u044B\u0432\u0430\u043B\u0438\u0441\u044C D*-\u0433\u0440\u0430\u0444\u0430\u043C\u0438, \u043D\u0430\u0441\u043B\u0435\u0434\u0441\u0442\u0432\u0435\u043D\u043D\u044B\u043C\u0438 \u0433\u0440\u0430\u0444\u0430\u043C\u0438 \u0414\u0435\u0439\u0441\u0438 (\u043F\u043E\u0441\u043B\u0435 \u0440\u0430\u0431\u043E\u0442\u044B \u0414\u0436\u0435\u0439\u043C\u0441\u0430 \u0414\u0435\u0439\u0441\u0438 [James C. Dacey, Jr.] \u043E\u0431 . \u0421\u043C\u043E\u0442\u0440\u0438\u0442\u0435 \u0440\u0430\u0431\u043E\u0442\u0443 \u0421\u0430\u043C\u043D\u0435\u0440\u0430) \u0438 \u0433\u0440\u0430\u0444\u044B \u0441 \u0434\u0432\u0443\u043C\u044F \u043F\u043E\u0442\u043E\u043C\u043A\u0430\u043C\u0438 \u0411\u0430\u0440\u043B\u0435\u0442\u0430 \u0438 \u0423\u0440\u0438. \u0421\u043C\u043E\u0442\u0440\u0438\u0442\u0435 \u043A\u043D\u0438\u0433\u0443 \u0411\u0440\u0430\u043D\u0434\u0448\u0442\u0435\u0434\u0442\u0430, \u041B\u0438 \u0438 \u0428\u043F\u0438\u043D\u0440\u0430\u0434\u0430, \u0433\u0434\u0435 \u043A\u043E\u0433\u0440\u0430\u0444\u044B \u0440\u0430\u0441\u0441\u043C\u043E\u0442\u0440\u0435\u043D\u044B \u0431\u043E\u043B\u0435\u0435 \u0434\u0435\u0442\u0430\u043B\u044C\u043D\u043E, \u0432\u043A\u043B\u044E\u0447\u0430\u044F \u0444\u0430\u043A\u0442\u044B, \u043F\u0440\u0438\u0432\u0435\u0434\u0451\u043D\u043D\u044B\u0435 \u0437\u0434\u0435\u0441\u044C."@ru . . . . "Kograf"@pl . . . "Cographe"@fr . . "\u041A\u043E\u0433\u0440\u0430\u0444"@ru . "Un cographe est, en th\u00E9orie des graphes, un graphe qui peut \u00EAtre g\u00E9n\u00E9r\u00E9 par compl\u00E9mentation et union disjointe \u00E0 partir du graphe \u00E0 un n\u0153ud. La plupart des probl\u00E8mes algorithmiques peuvent \u00EAtre r\u00E9solus sur cette classe en temps polynomial, et m\u00EAme linaire, du fait de ses propri\u00E9t\u00E9s structurelles."@fr . . . . . . . . . . . . . . . . . . . . . . . . "Un cographe est, en th\u00E9orie des graphes, un graphe qui peut \u00EAtre g\u00E9n\u00E9r\u00E9 par compl\u00E9mentation et union disjointe \u00E0 partir du graphe \u00E0 un n\u0153ud. La plupart des probl\u00E8mes algorithmiques peuvent \u00EAtre r\u00E9solus sur cette classe en temps polynomial, et m\u00EAme linaire, du fait de ses propri\u00E9t\u00E9s structurelles."@fr . "In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union. Special cases of the cographs include the complete graphs, complete bipartite graphs, cluster graphs, and threshold graphs. The cographs are, in turn, special cases of the distance-hereditary graphs, permutation graphs, comparability graphs, and perfect graphs."@en . . . . . . . . . "21893"^^ . . . . . . . . . "Cograph"@en . . . . . . . . "\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0433\u0440\u0430\u0444\u043E\u0432 \u043A\u043E\u0433\u0440\u0430\u0444, \u0438\u043B\u0438 \u0434\u043E\u043F\u043E\u043B\u043D\u0438\u0442\u0435\u043B\u044C\u043D\u043E \u0441\u0432\u043E\u0434\u0438\u043C\u044B\u0439 \u0433\u0440\u0430\u0444, \u0438\u043B\u0438 \u0433\u0440\u0430\u0444, \u0441\u0432\u043E\u0431\u043E\u0434\u043D\u044B\u0439 \u043E\u0442 P4, \u2014 \u044D\u0442\u043E \u0433\u0440\u0430\u0444, \u043A\u043E\u0442\u043E\u0440\u044B\u0439 \u043C\u043E\u0436\u043D\u043E \u043F\u043E\u043B\u0443\u0447\u0438\u0442\u044C \u0438\u0437 \u0433\u0440\u0430\u0444\u0430 \u0441 \u0435\u0434\u0438\u043D\u0441\u0442\u0432\u0435\u043D\u043D\u043E\u0439 \u0432\u0435\u0440\u0448\u0438\u043D\u043E\u0439 K1 \u043F\u0443\u0442\u0451\u043C \u043E\u043F\u0435\u0440\u0430\u0446\u0438\u0439 \u0434\u043E\u043F\u043E\u043B\u043D\u0435\u043D\u0438\u044F \u0438 \u043E\u0431\u044A\u0435\u0434\u0438\u043D\u0435\u043D\u0438\u044F \u0433\u0440\u0430\u0444\u043E\u0432. \u0422\u0430\u043A\u0438\u043C \u043E\u0431\u0440\u0430\u0437\u043E\u043C, \u0441\u0435\u043C\u0435\u0439\u0441\u0442\u0432\u043E \u043A\u043E\u0433\u0440\u0430\u0444\u043E\u0432 \u2014 \u044D\u0442\u043E \u043D\u0430\u0438\u043C\u0435\u043D\u044C\u0448\u0438\u0439 \u043A\u043B\u0430\u0441\u0441 \u0433\u0440\u0430\u0444\u043E\u0432, \u0441\u043E\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 K1 \u0438 \u0437\u0430\u043C\u043A\u043D\u0443\u0442\u044B\u0439 \u043E\u0442\u043D\u043E\u0441\u0438\u0442\u0435\u043B\u044C\u043D\u043E \u0434\u043E\u043F\u043E\u043B\u043D\u0435\u043D\u0438\u044F \u0438 \u043E\u0431\u044A\u0435\u0434\u0438\u043D\u0435\u043D\u0438\u044F. \u0421\u043C\u043E\u0442\u0440\u0438\u0442\u0435 \u043A\u043D\u0438\u0433\u0443 \u0411\u0440\u0430\u043D\u0434\u0448\u0442\u0435\u0434\u0442\u0430, \u041B\u0438 \u0438 \u0428\u043F\u0438\u043D\u0440\u0430\u0434\u0430, \u0433\u0434\u0435 \u043A\u043E\u0433\u0440\u0430\u0444\u044B \u0440\u0430\u0441\u0441\u043C\u043E\u0442\u0440\u0435\u043D\u044B \u0431\u043E\u043B\u0435\u0435 \u0434\u0435\u0442\u0430\u043B\u044C\u043D\u043E, \u0432\u043A\u043B\u044E\u0447\u0430\u044F \u0444\u0430\u043A\u0442\u044B, \u043F\u0440\u0438\u0432\u0435\u0434\u0451\u043D\u043D\u044B\u0435 \u0437\u0434\u0435\u0441\u044C."@ru . . .