Graphe orientéthumb|Un graphe orienté .(Figure 1) Dans la théorie des graphes, un graphe orienté est un couple formé de un ensemble, appelé ensemble de nœuds et un ensemble appelé ensemble d'arêtes. Les arêtes sont alors nommées arcs, chaque arête étant un couple de noeuds, représenté par une flèche. Étant donné un arc , on dit que est l'origine (ou la source ou le départ ou le début) de et que est la cible (ou l'arrivée ou la fin) de . Le demi-degré extérieur (degré sortant) d'un nœud, noté , est le nombre d'arcs ayant ce nœud pour origine.
Graph rewritingIn computer science, graph transformation, or graph rewriting, concerns the technique of creating a new graph out of an original graph algorithmically. It has numerous applications, ranging from software engineering (software construction and also software verification) to layout algorithms and picture generation. Graph transformations can be used as a computation abstraction. The basic idea is that if the state of a computation can be represented as a graph, further steps in that computation can then be represented as transformation rules on that graph.
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.
Graphe (mathématiques discrètes)Dans le domaine des mathématiques discrètes, la théorie des graphes définit le graphe, une structure composée d'objets et de relations entre deux de ces objets. Abstraitement, lesdits objets sont appelés sommets (ou nœuds ou points), et les relations entre eux sont nommées arêtes (ou liens ou lignes). On distingue les graphes non orientés, où les arêtes relient deux sommets de manière symétrique, et les graphes orientés, où les arêtes, alors appelées arcs (ou flèches), relient deux sommets de manière asymétrique.
Cycle (théorie des graphes)thumb|Dans ce graphe, le cycle rouge est élémentaire. Le cycle bleu ne l'est pas. La chaine verte n'est pas fermée et ne forme donc pas un cycle. Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives distinctes (chaine simple) dont les deux sommets extrémités sont identiques. Dans les graphes orientés, la notion équivalente est celle de circuit, même si on parle parfois aussi de cycle (par exemple dans l'expression graphe acyclique orienté).
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.
Graphe dualEn théorie des graphes, le graphe dual d'un graphe plongé dans une surface est défini à l'aide des composantes de son complémentaire, lesquelles sont reliées entre elles par les arêtes du graphe de départ. Cette notion généralise celle de dualité dans les polyèdres. Il faut noter qu'un même graphe abstrait peut avoir des graphes duaux non isomorphes en fonction du plongement choisi, même dans le cas de plongements dans le plan. Un graphe (plongé) isomorphe à son dual est dit autodual.
Densité d'un grapheEn mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe. Ce paramètre mesure si le graphe a beaucoup d'arêtes ou peu. Un graphe dense (dense graph) est un graphe dans lequel le nombre d'arêtes (ou d'arcs) est proche du nombre maximal, par exemple un nombre quadratique par rapport au nombre de sommets. Un graphe creux (sparse graph) a au contraire peu d'arêtes, par exemple un nombre linéaire. La distinction entre graphe creux et dense est plutôt vague et dépend du contexte.
Théorie des graphesvignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs.
Chaîne (théorie des graphes)Dans un graphe non orienté, une chaîne reliant à , notée , est définie par une suite finie d'arêtes consécutives, reliant à . La notion correspondante dans les graphes orientés est celle de chemin. Une chaîne élémentaire est une chaîne ne passant pas deux fois par un même sommet, c'est-à-dire dont tous les sommets sont distincts. Une chaîne simple est une chaîne ne passant pas deux fois par une même arête, c'est-à-dire dont toutes les arêtes sont distinctes. Un cycle est une chaîne simple dont les deux extrémités sont identiques.
Graph operationsIn the mathematical field of graph theory, graph operations are operations which produce new graphs from initial ones. They include both unary (one input) and binary (two input) operations. Unary operations create a new graph from a single initial graph. Elementary operations or editing operations, which are also known as graph edit operations, create a new graph from one initial one by a simple local change, such as addition or deletion of a vertex or of an edge, merging and splitting of vertices, edge contraction, etc.
Graphe grilleIn graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space \mathbb{R}^n, forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lattice in the group-theoretical sense. Typically, no clear distinction is made between such a graph in the more abstract sense of graph theory, and its drawing in space (often the plane or 3D space). This type of graph may more shortly be called just a lattice, mesh, or grid.
Homogeneous relationIn mathematics, a homogeneous relation (also called endorelation) on a set X is a binary relation between X and itself, i.e. it is a subset of the Cartesian product X × X. This is commonly phrased as "a relation on X" or "a (binary) relation over X". An example of a homogeneous relation is the relation of kinship, where the relation is between people. Common types of endorelations include orders, graphs, and equivalences. Specialized studies of order theory and graph theory have developed understanding of endorelations.
Sémantique opérationnelleEn informatique, la sémantique opérationnelle est l'une des approches qui servent à donner une signification aux programmes informatiques d'une manière rigoureuse, mathématiquement parlant (voir Sémantique des langages de programmation). Une sémantique opérationnelle d'un langage de programmation particulier décrit comment chaque programme valide du langage doit être interprété en termes de suite d'états successifs dans la machine. Cette suite d'états est la signification du programme.
Graphe aléatoirevignette|Graphe orienté aléatoire avec 20 nœuds et une probabilité de présence d'arête égale à 0,1. En mathématiques, un graphe aléatoire est un graphe généré par un processus aléatoire. Le premier modèle de graphes aléatoires a été popularisé par Paul Erdős et Alfréd Rényi dans une série d'articles publiés entre 1959 et 1968. Il y a deux modèles d'Erdős et Rényi, formellement différents, mais étroitement liés : le graphe aléatoire binomial et le graphe aléatoire uniforme.
Sémantique dénotationnelleEn informatique, la sémantique dénotationnelle est une des approches permettant de formaliser la signification d'un programme en utilisant les mathématiques. Parmi les autres approches, on trouve la sémantique axiomatique et la sémantique opérationnelle. Cette discipline a été introduite par Christopher Strachey et Dana Scott. En général, la sémantique dénotationnelle utilise des techniques de programmation fonctionnelle pour décrire les langages informatiques, les architectures et les programmes.
Relation inverseIn mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent of'. In formal terms, if and are sets and is a relation from to then is the relation defined so that if and only if In set-builder notation, The notation is analogous with that for an inverse function. Although many functions do not have an inverse, every relation does have a unique converse.
SemanticsSemantics () is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and computer science. In English, the study of meaning in language has been known by many names that involve the Ancient Greek word σῆμα (sema, "sign, mark, token"). In 1690, a Greek rendering of the term semiotics, the interpretation of signs and symbols, finds an early allusion in John Locke's An Essay Concerning Human Understanding: The third Branch may be called σημειωτική [simeiotikí, "semiotics"], or the Doctrine of Signs, the most usual whereof being words, it is aptly enough termed also λογικὴ, Logick.
Sémantique des langages de programmationEn informatique théorique, la sémantique formelle (des langages de programmation) est l’étude de la signification des programmes informatiques vus en tant qu’objets mathématiques. Comme en linguistique, la sémantique, appliquée aux langages de programmation, désigne le lien entre un signifiant, le programme, et un signifié, objet mathématique. L'objet mathématique dépend des propriétés à connaître du programme. La sémantique est également le lien entre : le langage signifiant : le langage de programmation le langage signifié : logique de Hoare, automates.
Théorèmes d'isomorphismeEn mathématiques, les trois théorèmes d'isomorphisme fournissent l'existence d'isomorphismes dans le cadre de la théorie des groupes. Ces trois théorèmes d'isomorphisme sont généralisables à d'autres structures que les groupes. Voir notamment « Anneau quotient », « Algèbre universelle » et « Groupe à opérateurs ». Le premier théorème d'isomorphisme affirme qu'étant donné un morphisme de groupes , on peut rendre injectif en quotientant par son noyau Ker f, qui est un sous-groupe normal de G.
