PréordreEn mathématiques, un préordre est une relation binaire réflexive et transitive. C'est-à-dire que si E est un ensemble, une relation binaire sur E est un préordre lorsque : (réflexivité) ; (transitivité). Un ensemble préordonné est un ensemble muni d'un préordre, ou plus formellement un couple où désigne un ensemble et un préordre sur . Les ordres sont les préordres antisymétriques. Les relations d'équivalence sont les préordres symétriques. Dans un anneau commutatif, la relation « divise » est une relation de préordre.
Giant componentIn network theory, a giant component is a connected component of a given random graph that contains a significant fraction of the entire graph's vertices. More precisely, in graphs drawn randomly from a probability distribution over arbitrarily large graphs, a giant component is a connected component whose fraction of the overall number of vertices is bounded away from zero. In sufficiently dense graphs distributed according to the Erdős–Rényi model, a giant component exists with high probability.
Algorithme d'Edmonds pour les couplagesEn informatique, plus précisément en théorie des graphes, l'algorithme d'Edmonds pour les couplages (blossom algorithm en anglais), aussi connu sous le nom d'algorithme des fleurs et des pétales est un algorithme pour construire des couplages maximaux sur les graphes. L'algorithme a été développé par Jack Edmonds en 1961, et publié en 1965. Étant donné un graphe quelconque G = (V, E), l'algorithme trouve un couplage M tel que chaque sommet de V est incident à au plus une arête dans E et M est de cardinal maximal.
Mathématiques appliquéesvignette|280px|En théorie des graphes, principales topologies typiques de graphes. Les mathématiques appliquées sont une branche des mathématiques qui s'intéresse à l'application du savoir mathématique aux autres domaines.
Graphe planaireDans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs.
MatroïdeEn mathématiques, et plus particulièrement en combinatoire, un matroïde est une structure introduite comme un cadre général pour le concept d'indépendance linéaire. Elle est donc naturellement liée à l'algèbre linéaire (déjà au niveau du vocabulaire : indépendant, base, rang), mais aussi à la théorie des graphes (circuit, cycle), à l'algorithmique (algorithme glouton), et à la géométrie (pour diverses questions liées à la représentation). La notion a été introduite en 1935 par Whitney. Le mot matroïde provient du mot matrice.
Graphe bipartiEn théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints et tels que chaque arête ait une extrémité dans et l'autre dans . Un graphe biparti permet notamment de représenter une relation binaire. Il existe plusieurs façons de caractériser un graphe biparti. Par le nombre chromatique Les graphes bipartis sont les graphes dont le nombre chromatique est inférieur ou égal à 2. Par la longueur des cycles Un graphe est biparti si et seulement s'il ne contient pas de cycle impair.
Hamiltonian pathIn the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path.
Matrice d'adjacenceEn mathématiques, en théorie des graphes, en informatique, une matrice d'adjacence pour un graphe fini à n sommets est une matrice de dimension n × n dont l'élément non diagonal a est le nombre d'arêtes liant le sommet i au sommet j. L'élément diagonal a est le nombre de boucles au sommet i (pour des graphes simples, ce nombre est donc toujours égal à 0 ou 1). Cet outil mathématique est très utilisé comme structure de données en informatique (tout comme la représentation par liste d'adjacence), mais intervient aussi naturellement dans les chaînes de Markov.
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.
