Graphe arête-connexeEn théorie des graphes, un graphe k-arête-connexe est un graphe connexe qu'il est possible de déconnecter en supprimant k arêtes et tel que ce k soit minimal. Il existe donc un ou plusieurs ensembles de k arêtes dont la suppression rende le graphe déconnecté, mais la suppression de k-1 arêtes, quelles qu'elles soient, le fait demeurer connexe. Un graphe régulier de degré k est au plus k-arête-connexe et k-sommet-connexe. S'il est effectivement k-arête-connexe et k-sommet-connexe, il est qualifié de graphe optimalement connecté.
Component (graph theory)In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices.
Test de planaritéEn théorie des graphes, le problème du test de planarité est le problème algorithmique qui consiste à tester si un graphe donné est un graphe planaire (c'est-à-dire s'il peut être dessiné dans le plan sans intersection d'arêtes). Il s'agit d'un problème bien étudié en informatique pour lequel de nombreux algorithmes pratiques ont été donnés, souvent en décrivant de nouvelles structures de données. La plupart de ces méthodes fonctionnent en temps O(n) (temps linéaire), où n est le nombre d'arêtes (ou de sommets) du graphe, ce qui est asymptotiquement optimal.
Graphe de flot de contrôleEn informatique, un graphe de flot de contrôle (abrégé en GFC, control flow graph ou CFG en anglais) est une représentation sous forme de graphe de tous les chemins qui peuvent être suivis par un programme durant son exécution. Dans un GFC, les sommets du graphe représentent un bloc de base, c'est-à-dire un bout de code d'un seul tenant sans sauts ni cibles de sauts. Les cibles de sauts marquent le début d'un bloc de base, tandis que les sauts en marquent la fin. Les arcs représentent les sauts dans le flot de contrôle.
Geometric graph theoryGeometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices; thus, it can be described as "the theory of geometric and topological graphs" (Pach 2013).
Cycle (géométrie algébrique)En géométrie algébrique, les cycles sont des combinaisons formelles de fermés irréductibles d'un schéma donné. Le quotient du groupe des cycles par une relation d'équivalence convenable aboutit aux qui sont des objets fondamentaux. Tous les schémas considérés ici seront supposés noethériens de dimension finie. On fixe un schéma qu'on supposera noethérien de dimension finie . Pour tout entier positif ou nul , on appelle -cycle irréductible (resp. -cocycle irréductible) de un fermé irréductible de dimension (resp.
Union-findthumb|Partition avec 8 classes (qui sont des singletons) obtenue avec MakeSet(1), ..., MakeSet(8).|255x255px thumb|Partition avec 3 classes disjointes obtenue après Union(1, 2), Union(3, 4), Union(2, 5), Union(1, 6) et Union(2, 8).|255x255px En informatique, union-find est une structure de données qui représente une partition d'un ensemble fini (ou de manière équivalente une relation d'équivalence).
Arête (géométrie)En géométrie dans l'espace, une arête est une droite délimitant deux demi-plans qui constituent les faces d’un angle diédral, ou plus spécialement le côté d’une face d’un polyèdre. Plus généralement, une arête d'un solide géométrique est la ligne d'intersection de deux surfaces de ce solide. À ce titre, l'arête n'est pas nécessairement une droite euclidienne. Un angle formé par deux demi-droites perpendiculaires à l’arête, issues d'un point de l’arête et incluses dans chacune des faces d’un dièdre, ne dépend pas du choix du point.
Peripheral cycleIn graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygons, because Tutte called cycles "polygons") were first studied by , and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.
Graphe des cyclesEn mathématiques, et plus particulièrement en théorie des groupes, le graphe des cycles d'un groupe représente l'ensemble des cycles de ce groupe, ce qui est particulièrement utile pour visualiser la structure des petits groupes finis. Pour les groupes ayant moins de 16 éléments, le graphe des cycles détermine le groupe à isomorphisme près. Un cycle est l'ensemble des puissances d'un élément donné du groupe ; a, la n-ième puissance de l'élément a, est définie comme le produit de a par lui-même n fois (avec les conventions a = a et a = e, l'élément neutre du groupe).
