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.
Addition matriciellevignette|Illustration d'une addition matricielle L'addition matricielle est une opération mathématique qui consiste à produire une matrice qui est le résultat de l'addition de deux matrices de même type. L'addition des matrices est définie pour deux matrices de même type. La somme de deux matrices de type (m, n), et , notée A + B, est à nouveau une matrice de type (m, n) obtenue en additionnant les éléments correspondants, i.e., pour tous i, j, Par exemple: L'ensemble des matrices de type (m, n) avec la loi d'addition forment un groupe abélien.
List edge-coloringIn mathematics, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring. An instance of a list edge-coloring problem consists of a graph together with a list of allowed colors for each edge. A list edge-coloring is a choice of a color for each edge, from its list of allowed colors; a coloring is proper if no two adjacent edges receive the same color. A graph G is k-edge-choosable if every instance of list edge-coloring that has G as its underlying graph and that provides at least k allowed colors for each edge of G has a proper coloring.
Coloration de listevignette|301x301px| Une instance de coloration de liste du graphe biparti complet K 3,27 avec trois couleurs par sommet. Pour tout choix de couleurs des trois sommets centraux, l'un des 27 sommets extérieurs ne peut être coloré, ce qui montre que le nombre chromatique de liste de K 3,27 est au moins quatre. En théorie des graphes, la coloration de liste est une coloration des sommets d'un graphe où la couleur de chaque sommet est restreinte à une liste de couleurs autorisées.
Matrice binaireUne matrice binaire est une matrice dont les coefficients sont soit 0, soit 1. En général ces coefficients sont les nombres de l'algèbre de Boole dans laquelle on appelle B l'ensemble constitué de deux éléments appelés valeurs de vérité {VRAI, FAUX}. Cet ensemble est aussi noté B = {1, 0} ou B = {⊤, ⊥}. On privilégie souvent la notation B = {1, 0}. Quand on programme des algorithmes utilisant ces matrices, la notation {VRAI, FAUX} peut coexister avec la notation {1, 0} car de nombreux langages acceptent ce polymorphisme.
Graphe complémentaireframe|right|Le graphe de Petersen, à gauche et son complémentaire, à droite. En théorie des graphes, le graphe complémentaire ou graphe inversé d'un graphe simple est un graphe simple ayant les mêmes sommets et tel que deux sommets distincts de soient adjacents si et seulement s'ils ne sont pas adjacents dans . Le graphe complémentaire ne doit pas être confondu avec le complémentaire dans le sens de la théorie des ensembles. En effet, l'ensemble des sommets de G reste inchangé. Le complémentaire du complémentaire est le graphe original.
Line graphEn théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes.
Vertex coverIn graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations.
Sommet (géométrie)vignette|droite|Le sommet d'un angle est le point d'intersection où se réunissent deux segments de droites. En géométrie, un sommet est un point particulier d'une figure : un sommet d'un polygone, d'un polyèdre, ou plus généralement d'un polytope, est un 0-simplexe de celui-ci ; c'est l'extrémité d'au moins une arête (par analogie, on parle aussi de sommets en théorie des graphes) ; dans un polyèdre, en chaque sommet, convergent au moins trois faces et un nombre égal d'arêtes (voir aussi le théorème de Descartes-Euler, qui relie le nombre de sommets, d'arêtes et de faces d'un polyèdre) ; le sommet d'un angle est le point d'intersection des deux côtés de cet angle ; le sommet d'un cône est le point d'intersection de toutes les génératrices de ce cône.
File (structure de données)En informatique, une file dite aussi file d'attente (en anglais queue) est un type abstrait basé sur le principe « premier entré, premier sorti » ou PEPS, désigné en anglais par l'acronyme FIFO () : les premiers éléments ajoutés à la file seront les premiers à en être retirés. vignette|First In First Out - Premier Entré Premier Sorti. Le type décrit le fonctionnement d'une : les premiers arrivés sont les premiers à sortir (PEPS, FIFO en anglais pour First in, first out).
Figure de sommetEn géométrie, une figure de sommet d'un sommet donné d'un polytope est, de façon intuitive, l'ensemble des points directement reliés à ce sommet par une arête. Ceci s’applique également aux pavages infinis, ou pavages remplissant l’espace avec des cellules polytopiques. De façon plus précise, une figure de sommet pour un n-polytope est un (n-1)-polytope. Ainsi, une figure de sommet pour un polyèdre est une figure polygonale, et la figure de sommet pour un polychore est une figure polyèdrique.
