| dbo:abstract
|
- Le polynôme de Tutte, aussi appelé polynôme dichromatique ou polynôme de Tutte–Whitney, est un polynôme invariant de graphes dont les valeurs expriment des propriétés d'un graphe. C'est un polynôme en deux variables qui joue un rôle important en théorie des graphes et en combinatoire. Il est défini pour tout graphe non orienté et contient des informations liées à ses propriétés de connexité. L'importance de ce polynôme provient des informations qu'il contient sur le graphe . Étudié au départ dans le cadre de la théorie algébrique des graphes comme une généralisation des problèmes d'énumération liés à la coloration de graphes, il contient diverses spécialisations à d'autres disciplines, comme le polynôme de Jones en théorie des nœuds, les fonctions de partitions liées au (en) en physique statistique, le polynôme énumérateur des poids en théorie des codes, le polynôme de fiabilité en théorie des réseaux. Tous peuvent être exprimés comme des spécialisations du polynôme de Tutte. Il est aussi à la source de divers problèmes algorithmiques en informatique théorique. L'interprétation combinatoire des polynômes de Tutte est en étroite relation avec l’énumération d'objets combinatoires par des méthodes de langages formels et séries formelles non commutatives Les polynômes de Tutte ont plusieurs nom et définitions équivalents. Un polynôme de Tutte est équivalent au rang polynomial de Whitney, au polynôme dichromatique de Tutte et au random cluster model de Fortuin–Kasteleyn par des transformations simples. C'est essentiellement une série génératrice comptant les ensembles d'arêtes d'une taille de composantes connexes donnés, avec une généralisation naturelle aux matroïdes. C'est également l'invariant de graphes le plus général définissable par une récurrence de type suppression-contraction. Plusieurs livres de théorie des graphes ou de matroïdes consacrent des chapitres entiers aux polynômes de Tutte. (fr)
- The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph and contains information about how the graph is connected. It is denoted by . The importance of this polynomial stems from the information it contains about . Though originally studied in algebraic graph theory as a generalization of counting problems related to graph coloring and nowhere-zero flow, it contains several famous other specializations from other sciences such as the Jones polynomial from knot theory and the partition functions of the Potts model from statistical physics. It is also the source of several central computational problems in theoretical computer science. The Tutte polynomial has several equivalent definitions. It is equivalent to Whitney’s rank polynomial, Tutte’s own dichromatic polynomial and Fortuin–Kasteleyn’s random cluster model under simple transformations. It is essentially a generating function for the number of edge sets of a given size and connected components, with immediate generalizations to matroids. It is also the most general graph invariant that can be defined by a deletion–contraction recurrence. Several textbooks about graph theory and matroid theory devote entire chapters to it. (en)
- 그래프 이론과 매트로이드 이론에서 텃 다항식(Tutte多項式, 영어: Tutte polynomial)은 유한 그래프 및 유한 매트로이드에 대응되는 2변수 정수 계수 다항식이다. 그래프 및 매트로이드의 다양한 성질들을 텃 다항식의 특별한 값으로 얻을 수 있다. (ko)
- Многочлен Татта (многочлен Татта — Уитни) — многочлен от двух переменных, играющий большую роль в теории графов; определён для любого неориентированного графа и содержит информацию, насколько граф связен. Стандартное обозначение — . Первоначально изучался в алгебраической теории графов как конструкция для обобщения задач подсчёта, связанных с раскраской графов и нигде не нулевыми потоками, впоследствии обнаружена связь с многочленом Джонса из теории узлов и статистическими суммами из статистической физики. Многочлен является источником некоторых теоретической информатики. Многочлен имеет несколько эквивалентных определений: он эквивалентен многочлену ранга Уитни, дихроматическому многочлену Татта и модели случайных кластеров Фортюэна — Кастелейна (после небольшого преобразования). Многочлен, по существу, является производящей функцией для числа рёбер множеств заданного размера и связных компонент и имеет прямое обобщение в теории матроидов. Многочлен является также для графов инвариантом наиболее общего вида, который может быть определён рекурсией удаления — стягивания. Некоторые книги по теории графов и матроидам посвящают целые главы этому понятию. (ru)
- Многочле́н Та́тта (або многочлен Татта — Вітні) — многочлен від двох змінних, що відіграє значну роль у теорії графів; визначений для будь-якого неорієнтованого графа і містить інформацію, наскільки граф зв'язний. Стандартне позначення . Спочатку вивчався в алгебричній теорії графів як конструкція для узагальнення задач підрахунку, пов'язаних з розфарбовуванням графів і ніде не нульовими потоками, згодом виявлено зв'язок із многочленом Джонса з теорії вузлів та статистичними сумами статистичної фізики. Многочлен є джерелом деяких інформатики. Багаточлен має кілька еквівалентних визначень: він еквівалентний многочлену рангу Вітні, дихроматичному многочлену Татта та моделі випадкових кластерів Фортюена — Кастелейна (після незначного перетворення). Многочлен, по суті, є функцією для числа ребер множин заданого розміру і зв'язних компонент і має пряме узагальнення в теорії матроїдів. Многочлен є також для графів інваріантом найзагальнішого вигляду, який можна визначити рекурсією видалення стягування. Деякі книги з теорії графів і матроїдів присвячують цілі розділи цьому поняттю. (uk)
|
| rdfs:comment
|
- 그래프 이론과 매트로이드 이론에서 텃 다항식(Tutte多項式, 영어: Tutte polynomial)은 유한 그래프 및 유한 매트로이드에 대응되는 2변수 정수 계수 다항식이다. 그래프 및 매트로이드의 다양한 성질들을 텃 다항식의 특별한 값으로 얻을 수 있다. (ko)
- The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph and contains information about how the graph is connected. It is denoted by . (en)
- Le polynôme de Tutte, aussi appelé polynôme dichromatique ou polynôme de Tutte–Whitney, est un polynôme invariant de graphes dont les valeurs expriment des propriétés d'un graphe. C'est un polynôme en deux variables qui joue un rôle important en théorie des graphes et en combinatoire. Il est défini pour tout graphe non orienté et contient des informations liées à ses propriétés de connexité. (fr)
- Многочлен Татта (многочлен Татта — Уитни) — многочлен от двух переменных, играющий большую роль в теории графов; определён для любого неориентированного графа и содержит информацию, насколько граф связен. Стандартное обозначение — . Первоначально изучался в алгебраической теории графов как конструкция для обобщения задач подсчёта, связанных с раскраской графов и нигде не нулевыми потоками, впоследствии обнаружена связь с многочленом Джонса из теории узлов и статистическими суммами из статистической физики. Многочлен является источником некоторых теоретической информатики. (ru)
- Многочле́н Та́тта (або многочлен Татта — Вітні) — многочлен від двох змінних, що відіграє значну роль у теорії графів; визначений для будь-якого неорієнтованого графа і містить інформацію, наскільки граф зв'язний. Стандартне позначення . Спочатку вивчався в алгебричній теорії графів як конструкція для узагальнення задач підрахунку, пов'язаних з розфарбовуванням графів і ніде не нульовими потоками, згодом виявлено зв'язок із многочленом Джонса з теорії вузлів та статистичними сумами статистичної фізики. Многочлен є джерелом деяких інформатики. (uk)
|
