. . . . "Neil Robertson"@en . . . . . . . . . . . . . . . . . . . . . "Umberto"@en . "3987086"^^ . . . . . . . . "\u0414\u0440\u0435\u0432\u0435\u0441\u043D\u0430\u044F \u0448\u0438\u0440\u0438\u043D\u0430 (\u0442\u0435\u043E\u0440\u0438\u044F \u0433\u0440\u0430\u0444\u043E\u0432)"@ru . . . . . . . . . . . . "\u0414\u0435\u0440\u0435\u0432\u043D\u0430 \u0448\u0438\u0440\u0438\u043D\u0430 (\u0442\u0435\u043E\u0440\u0456\u044F \u0433\u0440\u0430\u0444\u0456\u0432)"@uk . . . "Bertel\u00E8"@en . . "Brioschi"@en . "\u0412 \u0442\u0435\u043E\u0440\u0456\u0457 \u0433\u0440\u0430\u0444\u0456\u0432 \u0434\u0435\u0440\u0435\u0432\u043D\u0430 \u0448\u0438\u0440\u0438\u043D\u0430 \u043D\u0435\u043E\u0440\u0456\u0454\u043D\u0442\u043E\u0432\u0430\u043D\u043E\u0433\u043E \u0433\u0440\u0430\u0444\u0443 \u2014 \u0446\u0435 \u0447\u0438\u0441\u043B\u043E, \u0430\u0441\u043E\u0446\u0456\u0439\u043E\u0432\u0430\u043D\u0435 \u0437 \u0433\u0440\u0430\u0444\u043E\u043C. \u0414\u0435\u0440\u0435\u0432\u043D\u0443 \u0448\u0438\u0440\u0438\u043D\u0443 \u043C\u043E\u0436\u043D\u0430 \u0432\u0438\u0437\u043D\u0430\u0447\u0438\u0442\u0438 \u0434\u0435\u043A\u0456\u043B\u044C\u043A\u043E\u043C\u0430 \u0435\u043A\u0432\u0456\u0432\u0430\u043B\u0435\u043D\u0442\u043D\u0438\u043C\u0438 \u0441\u043F\u043E\u0441\u043E\u0431\u0430\u043C\u0438: \u044F\u043A \u0440\u043E\u0437\u043C\u0456\u0440 \u043D\u0430\u0439\u0431\u0456\u043B\u044C\u0448\u043E\u0457 \u043C\u043D\u043E\u0436\u0438\u043D\u0438 \u0432\u0435\u0440\u0448\u0438\u043D \u0443 \u0434\u0435\u0440\u0435\u0432\u043D\u043E\u043C\u0443 \u0440\u043E\u0437\u043A\u043B\u0430\u0434\u0456, \u044F\u043A \u0440\u043E\u0437\u043C\u0456\u0440 \u043D\u0430\u0439\u0431\u0456\u043B\u044C\u0448\u043E\u0457 \u043A\u043B\u0456\u043A\u0438 \u0432 \u0445\u043E\u0440\u0434\u0430\u043B\u044C\u043D\u043E\u043C\u0443 \u0434\u043E\u043F\u043E\u0432\u043D\u0435\u043D\u043D\u0456 \u0433\u0440\u0430\u0444\u0443, \u044F\u043A \u043D\u0430\u0439\u0431\u0456\u043B\u044C\u0448\u0438\u0439 \u043F\u043E\u0440\u044F\u0434\u043E\u043A \u0443\u043A\u0440\u0438\u0442\u0442\u044F \u043F\u0456\u0434 \u0447\u0430\u0441 \u043E\u043F\u0438\u0441\u0443 \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0456\u0457 \u0433\u0440\u0438 \u043F\u0435\u0440\u0435\u0441\u043B\u0456\u0434\u0443\u0432\u0430\u043D\u043D\u044F \u043D\u0430 \u0433\u0440\u0430\u0444\u0456 \u0430\u0431\u043E \u044F\u043A \u043D\u0430\u0439\u0431\u0456\u043B\u044C\u0448\u0438\u0439 \u043F\u043E\u0440\u044F\u0434\u043E\u043A \u043E\u0436\u0438\u043D\u0438, \u043D\u0430\u0431\u043E\u0440\u0443 \u0437\u0432'\u044F\u0437\u043D\u0438\u0445 \u043F\u0456\u0434\u0433\u0440\u0430\u0444\u0456\u0432, \u044F\u043A\u0456 \u0434\u043E\u0442\u0438\u043A\u0430\u044E\u0442\u044C\u0441\u044F \u043E\u0434\u0438\u043D \u0437 \u043E\u0434\u043D\u0438\u043C. \u0414\u0435\u0440\u0435\u0432\u043D\u0430 \u0448\u0438\u0440\u0438\u043D\u0430 \u0447\u0430\u0441\u0442\u043E \u0432\u0438\u043A\u043E\u0440\u0438\u0441\u0442\u043E\u0432\u0443\u0454\u0442\u044C\u0441\u044F \u044F\u043A \u043F\u0430\u0440\u0430\u043C\u0435\u0442\u0440 \u0432 \u0430\u043D\u0430\u043B\u0456\u0437\u0456 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0456\u0432 \u043D\u0430 \u0433\u0440\u0430\u0444\u0430\u0445. \u0413\u0440\u0430\u0444\u0438 \u0437 \u0448\u0438\u0440\u0438\u043D\u043E\u044E \u0434\u0435\u0440\u0435\u0432\u0430, \u0449\u043E \u043D\u0435 \u043F\u0435\u0440\u0435\u0432\u0438\u0449\u0443\u0454 k, \u043D\u0430\u0437\u0438\u0432\u0430\u044E\u0442\u044C\u0441\u044F \u0447\u0430\u0441\u0442\u043A\u043E\u0432\u0438\u043C\u0438 k-\u0434\u0435\u0440\u0435\u0432\u0430\u043C\u0438. \u0411\u0430\u0433\u0430\u0442\u043E \u0456\u043D\u0448\u0438\u0445 \u0434\u043E\u0431\u0440\u0435 \u0432\u0438\u0432\u0447\u0435\u043D\u0438\u0445 \u0441\u0456\u043C\u0435\u0439\u0441\u0442\u0432 \u0433\u0440\u0430\u0444\u0456\u0432 \u0442\u0430\u043A\u043E\u0436 \u043C\u0430\u044E\u0442\u044C \u043E\u0431\u043C\u0435\u0436\u0435\u043D\u0443 \u0448\u0438\u0440\u0438\u043D\u0443 \u0434\u0435\u0440\u0435\u0432\u0430."@uk . . . . . . . . . . . . . . . . . . "En th\u00E9orie des graphes et en informatique th\u00E9orique, la largeur arborescente ou largeur d'arbre d'un graphe (treewidth en anglais) est un nombre qui, intuitivement, mesure s'il est proche d'un arbre. Elle peut \u00EAtre d\u00E9finie de plusieurs mani\u00E8res[Lesquelles ?], notamment en utilisant la d\u00E9composition arborescente."@fr . "42012"^^ . . . . . . . . . . . "\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0433\u0440\u0430\u0444\u043E\u0432 \u0434\u0440\u0435\u0432\u0435\u0441\u043D\u0430\u044F \u0448\u0438\u0440\u0438\u043D\u0430 \u043D\u0435\u043E\u0440\u0438\u0435\u043D\u0442\u0438\u0440\u043E\u0432\u0430\u043D\u043D\u043E\u0433\u043E \u0433\u0440\u0430\u0444\u0430 \u2014 \u044D\u0442\u043E \u0447\u0438\u0441\u043B\u043E, \u0430\u0441\u0441\u043E\u0446\u0438\u0438\u0440\u043E\u0432\u0430\u043D\u043D\u043E\u0435 \u0441 \u0433\u0440\u0430\u0444\u043E\u043C. \u0414\u0440\u0435\u0432\u0435\u0441\u043D\u0443\u044E \u0448\u0438\u0440\u0438\u043D\u0443 \u043C\u043E\u0436\u043D\u043E \u043E\u043F\u0440\u0435\u0434\u0435\u043B\u0438\u0442\u044C \u043D\u0435\u0441\u043A\u043E\u043B\u044C\u043A\u0438\u043C\u0438 \u044D\u043A\u0432\u0438\u0432\u0430\u043B\u0435\u043D\u0442\u043D\u044B\u043C\u0438 \u043F\u0443\u0442\u044F\u043C\u0438: \u043A\u0430\u043A \u0440\u0430\u0437\u043C\u0435\u0440 \u043D\u0430\u0438\u0431\u043E\u043B\u044C\u0448\u0435\u0433\u043E \u043C\u043D\u043E\u0436\u0435\u0441\u0442\u0432\u0430 \u0432\u0435\u0440\u0448\u0438\u043D \u0432 \u0434\u0440\u0435\u0432\u0435\u0441\u043D\u043E\u043C \u0440\u0430\u0437\u043B\u043E\u0436\u0435\u043D\u0438\u0438, \u043A\u0430\u043A \u0440\u0430\u0437\u043C\u0435\u0440 \u043D\u0430\u0438\u0431\u043E\u043B\u044C\u0448\u0435\u0439 \u043A\u043B\u0438\u043A\u0438 \u0432 \u0445\u043E\u0440\u0434\u0430\u043B\u044C\u043D\u043E\u043C \u0434\u043E\u043F\u043E\u043B\u043D\u0435\u043D\u0438\u0438 \u0433\u0440\u0430\u0444\u0430, \u043A\u0430\u043A \u043C\u0430\u043A\u0441\u0438\u043C\u0430\u043B\u044C\u043D\u044B\u0439 \u043F\u043E\u0440\u044F\u0434\u043E\u043A \u0443\u0431\u0435\u0436\u0438\u0449\u0430 \u043F\u0440\u0438 \u043E\u043F\u0438\u0441\u0430\u043D\u0438\u0438 \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0438 \u0438\u0433\u0440\u044B \u043F\u0440\u0435\u0441\u043B\u0435\u0434\u043E\u0432\u0430\u043D\u0438\u044F \u043D\u0430 \u0433\u0440\u0430\u0444\u0435 \u0438\u043B\u0438 \u043A\u0430\u043A \u043C\u0430\u043A\u0441\u0438\u043C\u0430\u043B\u044C\u043D\u044B\u0439 \u043F\u043E\u0440\u044F\u0434\u043E\u043A \u0435\u0436\u0435\u0432\u0438\u043A\u0438, \u043D\u0430\u0431\u043E\u0440\u0430 \u0441\u0432\u044F\u0437\u043D\u044B\u0445 \u043F\u043E\u0434\u0433\u0440\u0430\u0444\u043E\u0432, \u043A\u043E\u0442\u043E\u0440\u044B\u0435 \u043A\u0430\u0441\u0430\u044E\u0442\u0441\u044F \u0434\u0440\u0443\u0433 \u0434\u0440\u0443\u0433\u0430.\u0414\u0440\u0435\u0432\u0435\u0441\u043D\u0430\u044F \u0448\u0438\u0440\u0438\u043D\u0430 \u0447\u0430\u0441\u0442\u043E \u0438\u0441\u043F\u043E\u043B\u044C\u0437\u0443\u0435\u0442\u0441\u044F \u0432 \u043A\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043F\u0430\u0440\u0430\u043C\u0435\u0442\u0440\u0430 \u0432 \u0430\u043D\u0430\u043B\u0438\u0437\u0435 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u0432 \u043D\u0430 \u0433\u0440\u0430\u0444\u0430\u0445. \u0413\u0440\u0430\u0444\u044B \u0441 \u0448\u0438\u0440\u0438\u043D\u043E\u0439 \u0434\u0435\u0440\u0435\u0432\u0430, \u043D\u0435 \u043F\u0440\u0435\u0432\u043E\u0441\u0445\u043E\u0434\u044F\u0449\u0435\u0439 k, \u043D\u0430\u0437\u044B\u0432\u0430\u044E\u0442\u0441\u044F \u0447\u0430\u0441\u0442\u0438\u0447\u043D\u044B\u043C\u0438 k-\u0434\u0435\u0440\u0435\u0432\u044C\u044F\u043C\u0438. \u041C\u043D\u043E\u0433\u0438\u0435 \u0434\u0440\u0443\u0433\u0438\u0435 \u0445\u043E\u0440\u043E\u0448\u043E \u0438\u0437\u0443\u0447\u0435\u043D\u043D\u044B\u0435 \u0441\u0435\u043C\u0435\u0439\u0441\u0442\u0432\u0430 \u0433\u0440\u0430\u0444\u043E\u0432 \u0442\u0430\u043A\u0436\u0435 \u0438\u043C\u0435\u044E\u0442 \u043E\u0433\u0440\u0430\u043D\u0438\u0447\u0435\u043D\u043D\u0443\u044E \u0448\u0438\u0440\u0438\u043D\u0443 \u0434\u0435\u0440\u0435\u0432\u0430."@ru . "1124268108"^^ . . . . . . . . . "Francesco"@en . "Die Baumweite ist ein Begriff aus der Graphentheorie. Sie sagt aus, wie \"baum-\u00E4hnlich\" ein Graph ist. Da viele Algorithmen auf B\u00E4umen (oder Baumzerlegungen) effizient laufen, die dies auf allgemeinenGraphen nicht tun, ist es interessant, die Baumweite zu kennen. Ein verwandter Begriff ist die Pfadweite. Der Begriff wurde 1972 von Umberto Bertel\u00E8 und Francesco Brioschi eingef\u00FChrt, unabh\u00E4ngig von Rudolf Halin 1976 und erneut unabh\u00E4ngig von Neil Robertson und Paul Seymour 1984."@de . "Halin"@en . . . . "Baumweite"@de . "Seymour"@en . . "Robertson"@en . . . "\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0433\u0440\u0430\u0444\u043E\u0432 \u0434\u0440\u0435\u0432\u0435\u0441\u043D\u0430\u044F \u0448\u0438\u0440\u0438\u043D\u0430 \u043D\u0435\u043E\u0440\u0438\u0435\u043D\u0442\u0438\u0440\u043E\u0432\u0430\u043D\u043D\u043E\u0433\u043E \u0433\u0440\u0430\u0444\u0430 \u2014 \u044D\u0442\u043E \u0447\u0438\u0441\u043B\u043E, \u0430\u0441\u0441\u043E\u0446\u0438\u0438\u0440\u043E\u0432\u0430\u043D\u043D\u043E\u0435 \u0441 \u0433\u0440\u0430\u0444\u043E\u043C. \u0414\u0440\u0435\u0432\u0435\u0441\u043D\u0443\u044E \u0448\u0438\u0440\u0438\u043D\u0443 \u043C\u043E\u0436\u043D\u043E \u043E\u043F\u0440\u0435\u0434\u0435\u043B\u0438\u0442\u044C \u043D\u0435\u0441\u043A\u043E\u043B\u044C\u043A\u0438\u043C\u0438 \u044D\u043A\u0432\u0438\u0432\u0430\u043B\u0435\u043D\u0442\u043D\u044B\u043C\u0438 \u043F\u0443\u0442\u044F\u043C\u0438: \u043A\u0430\u043A \u0440\u0430\u0437\u043C\u0435\u0440 \u043D\u0430\u0438\u0431\u043E\u043B\u044C\u0448\u0435\u0433\u043E \u043C\u043D\u043E\u0436\u0435\u0441\u0442\u0432\u0430 \u0432\u0435\u0440\u0448\u0438\u043D \u0432 \u0434\u0440\u0435\u0432\u0435\u0441\u043D\u043E\u043C \u0440\u0430\u0437\u043B\u043E\u0436\u0435\u043D\u0438\u0438, \u043A\u0430\u043A \u0440\u0430\u0437\u043C\u0435\u0440 \u043D\u0430\u0438\u0431\u043E\u043B\u044C\u0448\u0435\u0439 \u043A\u043B\u0438\u043A\u0438 \u0432 \u0445\u043E\u0440\u0434\u0430\u043B\u044C\u043D\u043E\u043C \u0434\u043E\u043F\u043E\u043B\u043D\u0435\u043D\u0438\u0438 \u0433\u0440\u0430\u0444\u0430, \u043A\u0430\u043A \u043C\u0430\u043A\u0441\u0438\u043C\u0430\u043B\u044C\u043D\u044B\u0439 \u043F\u043E\u0440\u044F\u0434\u043E\u043A \u0443\u0431\u0435\u0436\u0438\u0449\u0430 \u043F\u0440\u0438 \u043E\u043F\u0438\u0441\u0430\u043D\u0438\u0438 \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0438 \u0438\u0433\u0440\u044B \u043F\u0440\u0435\u0441\u043B\u0435\u0434\u043E\u0432\u0430\u043D\u0438\u044F \u043D\u0430 \u0433\u0440\u0430\u0444\u0435 \u0438\u043B\u0438 \u043A\u0430\u043A \u043C\u0430\u043A\u0441\u0438\u043C\u0430\u043B\u044C\u043D\u044B\u0439 \u043F\u043E\u0440\u044F\u0434\u043E\u043A \u0435\u0436\u0435\u0432\u0438\u043A\u0438, \u043D\u0430\u0431\u043E\u0440\u0430 \u0441\u0432\u044F\u0437\u043D\u044B\u0445 \u043F\u043E\u0434\u0433\u0440\u0430\u0444\u043E\u0432, \u043A\u043E\u0442\u043E\u0440\u044B\u0435 \u043A\u0430\u0441\u0430\u044E\u0442\u0441\u044F \u0434\u0440\u0443\u0433 \u0434\u0440\u0443\u0433\u0430.\u0414\u0440\u0435\u0432\u0435\u0441\u043D\u0430\u044F \u0448\u0438\u0440\u0438\u043D\u0430 \u0447\u0430\u0441\u0442\u043E \u0438\u0441\u043F\u043E\u043B\u044C\u0437\u0443\u0435\u0442\u0441\u044F \u0432 \u043A\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043F\u0430\u0440\u0430\u043C\u0435\u0442\u0440\u0430 \u0432 \u0430\u043D\u0430\u043B\u0438\u0437\u0435 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u0432 \u043D\u0430 \u0433\u0440\u0430\u0444\u0430\u0445. \u0413\u0440\u0430\u0444\u044B \u0441 \u0448\u0438\u0440\u0438\u043D\u043E\u0439 \u0434\u0435\u0440\u0435\u0432\u0430, \u043D\u0435 \u043F\u0440\u0435\u0432\u043E\u0441\u0445\u043E\u0434\u044F\u0449\u0435\u0439 k, \u043D\u0430\u0437\u044B\u0432\u0430\u044E\u0442\u0441\u044F \u0447\u0430\u0441\u0442\u0438\u0447\u043D\u044B\u043C\u0438 k-\u0434\u0435\u0440\u0435\u0432\u044C\u044F\u043C\u0438. \u041C\u043D\u043E\u0433\u0438\u0435 \u0434\u0440\u0443\u0433\u0438\u0435 \u0445\u043E\u0440\u043E\u0448\u043E \u0438\u0437\u0443\u0447\u0435\u043D\u043D\u044B\u0435 \u0441\u0435\u043C\u0435\u0439\u0441\u0442\u0432\u0430 \u0433\u0440\u0430\u0444\u043E\u0432 \u0442\u0430\u043A\u0436\u0435 \u0438\u043C\u0435\u044E\u0442 \u043E\u0433\u0440\u0430\u043D\u0438\u0447\u0435\u043D\u043D\u0443\u044E \u0448\u0438\u0440\u0438\u043D\u0443 \u0434\u0435\u0440\u0435\u0432\u0430. \u041F\u043E\u043D\u044F\u0442\u0438\u0435 \u0448\u0438\u0440\u0438\u043D\u044B \u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u0432\u0451\u043B \u0425\u0430\u043B\u0438\u043D \u043E\u0441\u043D\u043E\u0432\u044B\u0432\u0430\u044F\u0441\u044C \u043D\u0430 \u0434\u0440\u0443\u0433\u043E\u043C \u043F\u0430\u0440\u0430\u043C\u0435\u0442\u0440\u0435, \u0447\u0438\u0441\u043B\u0435 \u0425\u0430\u0434\u0432\u0438\u0433\u0435\u0440\u0430, \u0441 \u043A\u043E\u0442\u043E\u0440\u044B\u043C \u0434\u0440\u0435\u0432\u0435\u0441\u043D\u0430\u044F \u0448\u0438\u0440\u0438\u043D\u0430 \u0438\u043C\u0435\u0435\u0442 \u0440\u044F\u0434 \u043E\u0431\u0449\u0438\u0445 \u0441\u0432\u043E\u0439\u0441\u0442\u0432. \u041F\u043E\u0437\u0436\u0435 \u0434\u0440\u0435\u0432\u0435\u0441\u043D\u0443\u044E \u0448\u0438\u0440\u0438\u043D\u0443 \u043F\u0435\u0440\u0435\u043E\u0442\u043A\u0440\u044B\u043B\u0438 \u0420\u043E\u0431\u0435\u0440\u0442\u0441\u043E\u043D \u0438 \u0421\u0435\u0439\u043C\u0443\u0440, \u0438 \u0441 \u0442\u0435\u0445 \u043F\u043E\u0440 \u043E\u043D\u0430 \u0438\u0437\u0443\u0447\u0430\u043B\u0430\u0441\u044C \u043C\u043D\u043E\u0433\u0438\u043C\u0438 \u0430\u0432\u0442\u043E\u0440\u0430\u043C\u0438."@ru . . . . . . "Paul Seymour"@en . . . . . . . "In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series\u2013parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth."@en . "Die Baumweite ist ein Begriff aus der Graphentheorie. Sie sagt aus, wie \"baum-\u00E4hnlich\" ein Graph ist. Da viele Algorithmen auf B\u00E4umen (oder Baumzerlegungen) effizient laufen, die dies auf allgemeinenGraphen nicht tun, ist es interessant, die Baumweite zu kennen. Ein verwandter Begriff ist die Pfadweite. Der Begriff wurde 1972 von Umberto Bertel\u00E8 und Francesco Brioschi eingef\u00FChrt, unabh\u00E4ngig von Rudolf Halin 1976 und erneut unabh\u00E4ngig von Neil Robertson und Paul Seymour 1984."@de . . "1976"^^ . . . . . "1972"^^ . . . . . . . . "Paul"@en . . . "Neil"@en . . . . . . . . "\u0412 \u0442\u0435\u043E\u0440\u0456\u0457 \u0433\u0440\u0430\u0444\u0456\u0432 \u0434\u0435\u0440\u0435\u0432\u043D\u0430 \u0448\u0438\u0440\u0438\u043D\u0430 \u043D\u0435\u043E\u0440\u0456\u0454\u043D\u0442\u043E\u0432\u0430\u043D\u043E\u0433\u043E \u0433\u0440\u0430\u0444\u0443 \u2014 \u0446\u0435 \u0447\u0438\u0441\u043B\u043E, \u0430\u0441\u043E\u0446\u0456\u0439\u043E\u0432\u0430\u043D\u0435 \u0437 \u0433\u0440\u0430\u0444\u043E\u043C. \u0414\u0435\u0440\u0435\u0432\u043D\u0443 \u0448\u0438\u0440\u0438\u043D\u0443 \u043C\u043E\u0436\u043D\u0430 \u0432\u0438\u0437\u043D\u0430\u0447\u0438\u0442\u0438 \u0434\u0435\u043A\u0456\u043B\u044C\u043A\u043E\u043C\u0430 \u0435\u043A\u0432\u0456\u0432\u0430\u043B\u0435\u043D\u0442\u043D\u0438\u043C\u0438 \u0441\u043F\u043E\u0441\u043E\u0431\u0430\u043C\u0438: \u044F\u043A \u0440\u043E\u0437\u043C\u0456\u0440 \u043D\u0430\u0439\u0431\u0456\u043B\u044C\u0448\u043E\u0457 \u043C\u043D\u043E\u0436\u0438\u043D\u0438 \u0432\u0435\u0440\u0448\u0438\u043D \u0443 \u0434\u0435\u0440\u0435\u0432\u043D\u043E\u043C\u0443 \u0440\u043E\u0437\u043A\u043B\u0430\u0434\u0456, \u044F\u043A \u0440\u043E\u0437\u043C\u0456\u0440 \u043D\u0430\u0439\u0431\u0456\u043B\u044C\u0448\u043E\u0457 \u043A\u043B\u0456\u043A\u0438 \u0432 \u0445\u043E\u0440\u0434\u0430\u043B\u044C\u043D\u043E\u043C\u0443 \u0434\u043E\u043F\u043E\u0432\u043D\u0435\u043D\u043D\u0456 \u0433\u0440\u0430\u0444\u0443, \u044F\u043A \u043D\u0430\u0439\u0431\u0456\u043B\u044C\u0448\u0438\u0439 \u043F\u043E\u0440\u044F\u0434\u043E\u043A \u0443\u043A\u0440\u0438\u0442\u0442\u044F \u043F\u0456\u0434 \u0447\u0430\u0441 \u043E\u043F\u0438\u0441\u0443 \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0456\u0457 \u0433\u0440\u0438 \u043F\u0435\u0440\u0435\u0441\u043B\u0456\u0434\u0443\u0432\u0430\u043D\u043D\u044F \u043D\u0430 \u0433\u0440\u0430\u0444\u0456 \u0430\u0431\u043E \u044F\u043A \u043D\u0430\u0439\u0431\u0456\u043B\u044C\u0448\u0438\u0439 \u043F\u043E\u0440\u044F\u0434\u043E\u043A \u043E\u0436\u0438\u043D\u0438, \u043D\u0430\u0431\u043E\u0440\u0443 \u0437\u0432'\u044F\u0437\u043D\u0438\u0445 \u043F\u0456\u0434\u0433\u0440\u0430\u0444\u0456\u0432, \u044F\u043A\u0456 \u0434\u043E\u0442\u0438\u043A\u0430\u044E\u0442\u044C\u0441\u044F \u043E\u0434\u0438\u043D \u0437 \u043E\u0434\u043D\u0438\u043C. \u0414\u0435\u0440\u0435\u0432\u043D\u0430 \u0448\u0438\u0440\u0438\u043D\u0430 \u0447\u0430\u0441\u0442\u043E \u0432\u0438\u043A\u043E\u0440\u0438\u0441\u0442\u043E\u0432\u0443\u0454\u0442\u044C\u0441\u044F \u044F\u043A \u043F\u0430\u0440\u0430\u043C\u0435\u0442\u0440 \u0432 \u0430\u043D\u0430\u043B\u0456\u0437\u0456 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0456\u0432 \u043D\u0430 \u0433\u0440\u0430\u0444\u0430\u0445. \u0413\u0440\u0430\u0444\u0438 \u0437 \u0448\u0438\u0440\u0438\u043D\u043E\u044E \u0434\u0435\u0440\u0435\u0432\u0430, \u0449\u043E \u043D\u0435 \u043F\u0435\u0440\u0435\u0432\u0438\u0449\u0443\u0454 k, \u043D\u0430\u0437\u0438\u0432\u0430\u044E\u0442\u044C\u0441\u044F \u0447\u0430\u0441\u0442\u043A\u043E\u0432\u0438\u043C\u0438 k-\u0434\u0435\u0440\u0435\u0432\u0430\u043C\u0438. \u0411\u0430\u0433\u0430\u0442\u043E \u0456\u043D\u0448\u0438\u0445 \u0434\u043E\u0431\u0440\u0435 \u0432\u0438\u0432\u0447\u0435\u043D\u0438\u0445 \u0441\u0456\u043C\u0435\u0439\u0441\u0442\u0432 \u0433\u0440\u0430\u0444\u0456\u0432 \u0442\u0430\u043A\u043E\u0436 \u043C\u0430\u044E\u0442\u044C \u043E\u0431\u043C\u0435\u0436\u0435\u043D\u0443 \u0448\u0438\u0440\u0438\u043D\u0443 \u0434\u0435\u0440\u0435\u0432\u0430. \u041F\u043E\u043D\u044F\u0442\u0442\u044F \u0448\u0438\u0440\u0438\u043D\u0438 \u0434\u0435\u0440\u0435\u0432\u0430 \u0432\u0432\u0456\u0432 \u0425\u0430\u043B\u0456\u043D \u0491\u0440\u0443\u043D\u0442\u0443\u044E\u0447\u0438\u0441\u044C \u043D\u0430 \u0456\u043D\u0448\u043E\u043C\u0443 \u043F\u0430\u0440\u0430\u043C\u0435\u0442\u0440\u0456, , \u0437 \u044F\u043A\u0438\u043C \u0434\u0435\u0440\u0435\u0432\u043D\u0430 \u0448\u0438\u0440\u0438\u043D\u0430 \u043C\u0430\u0454 \u043D\u0438\u0437\u043A\u0443 \u0441\u043F\u0456\u043B\u044C\u043D\u0438\u0445 \u0432\u043B\u0430\u0441\u0442\u0438\u0432\u043E\u0441\u0442\u0435\u0439. \u041F\u0456\u0437\u043D\u0456\u0448\u0435 \u0434\u0435\u0440\u0435\u0432\u043D\u0443 \u0448\u0438\u0440\u0438\u043D\u0443 \u043F\u0435\u0440\u0435\u0432\u0456\u0434\u043A\u0440\u0438\u043B\u0438 \u0420\u043E\u0431\u0435\u0440\u0442\u0441\u043E\u043D \u0456 \u0421\u0435\u0439\u043C\u0443\u0440, \u0456 \u0432\u0456\u0434\u0442\u043E\u0434\u0456 \u0457\u0457 \u0432\u0438\u0432\u0447\u0430\u043B\u0438 \u0431\u0430\u0433\u0430\u0442\u043E \u0430\u0432\u0442\u043E\u0440\u0456\u0432."@uk . . . "Rudolf"@en . . . . . "1984"^^ . "Largeur arborescente"@fr . . . . . . . "En th\u00E9orie des graphes et en informatique th\u00E9orique, la largeur arborescente ou largeur d'arbre d'un graphe (treewidth en anglais) est un nombre qui, intuitivement, mesure s'il est proche d'un arbre. Elle peut \u00EAtre d\u00E9finie de plusieurs mani\u00E8res[Lesquelles ?], notamment en utilisant la d\u00E9composition arborescente. Souvent, un probl\u00E8me algorithmique facile sur les arbres est en fait facile pour les graphes qui ressemblent \u00E0 des arbres. Ainsi, ce param\u00E8tre est souvent utilis\u00E9 en algorithmique de graphes, notamment pour les sch\u00E9mas d'approximation polynomiaux et complexit\u00E9 param\u00E9tr\u00E9e. Dans beaucoup d'applications, les graphes ont des largeurs arborescentes petites[r\u00E9f. n\u00E9cessaire], comme par exemple les r\u00E9seaux sociaux."@fr . . . "Treewidth"@en . . "In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series\u2013parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth. Treewidth may be formally defined in several equivalent ways: in terms of the size of the largest vertex set in a tree decomposition of the graph, in terms of the size of the largest clique in a chordal completion of the graph, in terms of the maximum order of a haven describing a strategy for a pursuit\u2013evasion game on the graph, or in terms of the maximum order of a bramble, a collection of connected subgraphs that all touch each other. Treewidth is commonly used as a parameter in the parameterized complexity analysis of graph algorithms. Many algorithms that are NP-hard for general graphs, become easier when the treewidth is bounded by a constant. The concept of treewidth was originally introduced by Umberto Bertel\u00E8 and Francesco Brioschi under the name of dimension. It was later rediscovered by Rudolf Halin, based on properties that it shares with a different graph parameter, the Hadwiger number. Later it was again rediscovered by Neil Robertson and Paul Seymour and has since been studied by many other authors."@en . . . . "Rudolf Halin"@en . .