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.
Problème de flot maximumthumb|right|Un exemple de graphe de flot avec un flot maximum. la source est , et le puits . Les nombres indiquent le flot et la capacité. Le problème de flot maximum consiste à trouver, dans un réseau de flot, un flot réalisable depuis une source unique et vers un puits unique qui soit maximum. Quelquefois, on ne s'intéresse qu'à la valeur de ce flot. Le s-t flot maximum (depuis la source s vers le puits t) est égal à la s-t coupe minimum du graphe, comme l'indique le théorème flot-max/coupe-min.
Public-domain-equivalent licensePublic-domain-equivalent license are licenses that grant public-domain-like rights and/or act as waivers. They are used to make copyrighted works usable by anyone without conditions, while avoiding the complexities of attribution or license compatibility that occur with other licenses. No permission or license is required for a work truly in the public domain, such as one with an expired copyright; such a work may be copied at will.
Connexité simpleEn topologie générale et en topologie algébrique, la notion de simple connexité raffine celle de connexe par arcs. Dans un espace connexe par arcs, deux points quelconques peuvent toujours être reliés par un chemin. Dans un espace simplement connexe, cela est toujours possible d'une et une seule façon, l'unicité étant à comprendre au sens de « à déformation (isotopie) près ». Intuitivement, là où un espace connexe est simplement « d'un seul tenant », un espace simplement connexe est de plus sans « trou » ni « poignée ».
Public-domain softwarePublic-domain software is software that has been placed in the public domain, in other words, software for which there is absolutely no ownership such as copyright, trademark, or patent. Software in the public domain can be modified, distributed, or sold even without any attribution by anyone; this is unlike the common case of software under exclusive copyright, where licenses grant limited usage rights.
Connectivity (graph theory)In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.
Base de données orientée grapheUne base de données orientée graphe est une base de données orientée objet utilisant la théorie des graphes, donc avec des nœuds et des arcs, permettant de représenter et stocker les données. Par définition, une base de données orientée graphe correspond à un système de stockage capable de fournir une adjacence entre éléments voisins : chaque voisin d'une entité est accessible grâce à un pointeur physique. C'est une base de données orientée objet adaptée à l'exploitation des structures de données de type graphe ou dérivée, comme des arbres.
Licence de libre diffusionUne licence de libre diffusion (parfois abrégé LLD) ou licence ouverte est une licence s'appliquant à une œuvre de l'esprit par laquelle l'auteur concède certains des droits que lui offre le droit d'auteur quant à l'utilisation, à la modification, à la rediffusion et à la réutilisation de l'œuvre dans des œuvres dérivées. Tout comme les licences libres dont elles dérivent et qu'elles englobent, elles facilitent la prolifération d'une œuvre en autorisant la copie et l'usage sous certaines conditions.
Short Message Servicevignette|Affichage d'un SMS en néerlandais. vignette|Affichage d'un SMS en anglais d'une alerte incendie sur un iPhone. Le service de messagerie SMS, plus connu sous le sigle de SMS (pour « Short Message Service ») ou les noms de « texto » ou de « minimessage », permet de transmettre de courts messages textuels. C'est l'un des services de la téléphonie mobile (il a été introduit par la norme GSM). Dans certaines régions du monde comme l’Amérique du Nord, le Royaume-Uni ou les Philippines, on parle de « messagerie texte ».
Nombre de croisements (théorie des graphes)vignette| Une représentation du graphe de Heawood avec trois croisements. C'est le nombre minimum de croisements parmi toutes les représentations de ce graphe, qui a donc un nombre de croisements . En théorie des graphes, le nombre de croisements d'un graphe G est le plus petit nombre d'intersections d'arêtes d'un tracé du graphe G. Par exemple, un graphe est planaire si et seulement si son nombre de croisements est nul. La détermination du nombre de croisements tient une place importante dans le tracé de graphes.
Coupe (théorie des graphes)En théorie des graphes, une coupe d'un graphe est une partition des sommets en deux sous-ensembles. On appelle aussi coupe l'ensemble des arêtes ayant une extrémité dans chaque sous-ensemble de la partition. Si les arêtes ont un poids, le poids de la coupe est la somme des poids respectifs des arêtes de la coupe. Sinon, c'est le nombre d'arêtes dans la coupe. Cet objet apparaît dans la modélisation de nombreux problèmes concernant les réseaux, où l'on recherche une coupe s-t, c'est-à-dire une coupe séparant deux sommets s et t spécifiés.
Arbre couvrant de poids minimalthumb|L'arbre couvrant de poids minimal d'un graphe planaire. Chaque arête est identifiée avec son poids qui, ici, est approximativement sa longueur. En théorie des graphes, étant donné un graphe non orienté connexe dont les arêtes sont pondérées, un arbre couvrant de poids minimal (ACM), arbre couvrant minimum ou arbre sous-tendant minimum de ce graphe est un arbre couvrant (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale (c'est-à-dire de poids inférieur ou égal à celui de tous les autres arbres couvrants du graphe).
