Acyclic orientationIn graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation. The chromatic number of any graph equals one more than the length of the longest path in an acyclic orientation chosen to minimize this path length. Acyclic orientations are also related to colorings through the chromatic polynomial, which counts both acyclic orientations and colorings.
Homologie (mathématiques)En mathématiques, l'homologie est une manière générale d'associer une séquence d'objets algébriques tels que des groupes abéliens ou des modules à d'autres objets mathématiques tels que des espaces topologiques. Les groupes d'homologie ont été définis à l'origine dans la topologie algébrique. Des constructions similaires sont disponibles dans beaucoup d'autres contextes, tels que l'algèbre abstraite, les groupes, les algèbres de Lie, la théorie de Galois et la géométrie algébrique.
Homologie singulièreEn topologie algébrique, l'homologie singulière est une construction qui permet d'associer à un espace topologique X une suite homologique de groupes abéliens libres ou de modules. Cette association est un invariant topologique non complet, c'est-à-dire que si deux espaces sont homéomorphes alors ils ont mêmes groupes d'homologie singulière en chaque degré mais que la réciproque est fausse. Le théorème de Stokes appliqué à des formes fermées donne des intégrales nulles. Cependant, il se fonde sur une hypothèse cruciale de compacité.
HypergrapheLes hypergraphes sont des objets mathématiques généralisant la notion de graphe. Ils ont été nommés ainsi par Claude Berge dans les années 1960. Les hypergraphes généralisent la notion de graphe non orienté dans le sens où les arêtes ne relient plus un ou deux sommets, mais un nombre quelconque de sommets (compris entre un et le nombre de sommets de l’hypergraphe). Certains théorèmes de la théorie des graphes se généralisent naturellement aux hypergraphes, par exemple le théorème de Ramsey.
Espace classifiantEn mathématiques, un espace classifiant pour un groupe topologique G est la base d’un fibré principal particulier EG → BG appelé fibré universel, induisant tous les fibrés ayant ce groupe de structure sur n’importe quel CW-complexe X par (pullback). Dans le cas d’un groupe discret, la définition d’espace classifiant correspond à celle d’un espace d'Eilenberg-MacLane K(G, 1), c’est-à-dire un espace connexe par arcs dont tous les groupes d'homotopie sont triviaux en dehors du groupe fondamental (lequel est isomorphe à G).
Dégénérescence (théorie des graphes)En théorie des graphes, la dégénérescence est un paramètre associé à un graphe non orienté. Un graphe est k-dégénéré si tout sous-graphe contient un nœud de degré inférieur ou égal à k, et la dégénérescence d'un graphe est le plus petit k tel qu'il est k-dégénéré. On peut de façon équivalente définir le paramètre en utilisant un ordre sur les sommets (appelé ordre de dégénérescence) tel que, pour tout sommet, le nombre d'arêtes vers des sommets plus petits dans l'ordre est au plus k. On parle alors parfois de nombre de marquage.
Orientation (graph theory)In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. A directed graph is called an oriented graph if none of its pairs of vertices is linked by two symmetric edges. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of (x, y) and (y, x) may be arrows of the graph). A tournament is an orientation of a complete graph. A polytree is an orientation of an undirected tree.
Homologie de FloerL'homologie de Floer est une adaptation de l'homologie de Morse en dimension infinie. L'homologie de Floer symplectique (HFS) est une théorie homologique pour une variété symplectique munie d'un symplectomorphisme non-dégénéré. Si le symplectomorphisme est hamiltonien, l'homologie provient de l'étude de la fonctionnelle d'action symplectique sur le revêtement universel de l'espace des lacets de la variété symplectique. L'homologie de Floer symplectique est invariante par isotopie hamiltonienne du symplectomorphisme.
Reduced homologyIn mathematics, reduced homology is a minor modification made to homology theory in algebraic topology, motivated by the intuition that all of the homology groups of a single point should be equal to zero. This modification allows more concise statements to be made (as in Alexander duality) and eliminates many exceptional cases (as in the homology groups of spheres). If P is a single-point space, then with the usual definitions the integral homology group H0(P) is isomorphic to (an infinite cyclic group), while for i ≥ 1 we have Hi(P) = {0}.
Problème de la plus longue chaînevignette|Par suppression d'une arête rouge arbitraire, ce cycle hamiltonien donne une chaîne de longueur maximale. En théorie des graphes et en informatique théorique, le problème de la plus longue chaîne (ou le problème du plus long chemin dans le cas d'un graphe orienté) consiste à déterminer la plus longue chaîne élémentaire dans un graphe. Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet. La longueur d'une chaîne peut être mesurée par le nombre d'arêtes qui la composent ou, dans le cas de graphes pondérés, par la somme des poids des arêtes du chemin.
