Isomorphisme de graphesEn mathématiques, dans le cadre de la théorie des graphes, un isomorphisme de graphes est une bijection entre les sommets de deux graphes qui préserve les arêtes. Ce concept est en accord avec la notion générale d'isomorphisme, une bijection qui préserve les structures. Plus précisément, un isomorphisme f entre les graphes G et H est une bijection entre les sommets de G et ceux de H, telle qu'une paire de sommets {u, v} de G est une arête de G si et seulement si {ƒ(u), ƒ(v)} est une arête de H.
LexBFSLexBFS, ou parcours en largeur lexicographique est un algorithme de théorie des graphes. C'est un raffinement de l'algorithme de parcours en largeur (BFS pour Breadth First Search en anglais). Ce parcours est très utile pour étudier certaines classes de graphes et pour obtenir des algorithmes de reconnaissance rapides de ces classes. L'algorithme de parcours en largeur (Breadth First Search algorithm ou BFS) est usuellement défini de la manière suivante: Initialiser une de sommets du graphe avec le nœud de départ du parcours comme unique élément de la file.
Théorème de Kőnig (théorie des graphes)vignette|Exemple d'un graphe biparti avec un couplage maximum (en bleu) et une couverture de sommets minimale (en rouge), tous les deux de taille 6. Le théorème de Kőnig est un résultat de théorie des graphes qui dit que, dans un graphe biparti, la taille du transversal minimum (i. e. de la couverture par sommets minimum) est égale à la taille du couplage maximum. La version pondérée du théorème est appelée théorème de Kőnig-. Un couplage d'un graphe G est un sous-ensemble d'arêtes de G deux-à-deux non adjacentes ; un sommet est couplé s'il est extrémité d'une arête du couplage.
Distance (théorie des graphes)En théorie des graphes, la distance entre deux nœuds d'un graphe est la longueur d'un plus court chemin entre ces deux nœuds. La longueur d'un chemin est sa longueur en nombre d'arêtes. Pour un graphe pondéré c'est la somme des poids des arêtes empruntées. Pour les graphes non orientés, c'est une distance au sens mathématique, tandis que pour les graphes orientés elle ne vérifie pas la propriété de symétrie. Cette notion permet entre autres de définir le diamètre et le rayon d'un graphe. Catégorie:Concept
Graphe cycleLes graphes cycles, ou n-cycles, forment une famille de graphes. Le graphe cycle est constitué d'un unique cycle élémentaire de longueur n (pour ). C'est un graphe connexe non-orienté d'ordre n à n arêtes. Il est 2-régulier, c'est-à-dire que chacun de ses sommets est de degré 2. Beaucoup de termes sont employés pour désigner le graphe cycle : n-cycle, polygone et n-gone. Le terme de graphe cyclique est parfois employé, mais il pose problème car il s'oppose normalement à graphe acyclique. Nombre chromatique.
Notebook (programmation)vignette|Notebook du logiciel informatique IPython.|338x338px En programmation informatique, un notebook, aussi fréquemment appelé calepin électronique, voire simplement calepin est une interface de permettant de combiner des sections en langage naturel et des sections en langage informatique. Les notebooks sont notamment utilisés en science des données pour explorer et analyser des données. Les notebooks peuvent ensuite être enregistrés sous forme de document. C'est un exemple de programmation lettrée.
Iterative deepening depth-first searchIn computer science, iterative deepening search or more specifically iterative deepening depth-first search (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found. IDDFS is optimal like breadth-first search, but uses much less memory; at each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first.
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.
MultigraphIn mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called parallel edges), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge. There are 2 distinct notions of multiple edges: Edges without own identity: The identity of an edge is defined solely by the two nodes it connects. In this case, the term "multiple edges" means that the same edge can occur several times between these two nodes.
IPythonIPython est un terminal interactif, ou shell, pour le langage de programmation Python qui propose des fonctionnalités telles que l'introspection, une syntaxe additionnelle, la complétion et un historique riche. En 2014, la communauté de développement décide de scinder le projet en deux : la partie spécifique au langage Python reste dans le projet IPython ; la partie indépendante du langage passe dans un nouveau projet nommé Jupyter (pour Julia, Python, R). La version 3.0 est la dernière version « monolithique » d'IPython.
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.
Rooted graphIn mathematics, and, in particular, in graph theory, a rooted graph is a graph in which one vertex has been distinguished as the root. Both directed and undirected versions of rooted graphs have been studied, and there are also variant definitions that allow multiple roots. Rooted graphs may also be known (depending on their application) as pointed graphs or flow graphs. In some of the applications of these graphs, there is an additional requirement that the whole graph be reachable from the root vertex.
