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.
Graphe (type abstrait)thumb|upright=1.3|Un graphe orienté, dont les arcs et certains sommets sont « valués » par des couleurs. En informatique, et plus particulièrement en génie logiciel, le type abstrait graphe est la spécification formelle des données qui définissent l'objet mathématique graphe et de l'ensemble des opérations qu'on peut effectuer sur elles. On qualifie d'« abstrait » ce type de données car il correspond à un cahier des charges qu'une structure de données concrète doit ensuite implémenter.
Évolution de l'usage des navigateurs webvignette|Part de marché des principaux navigateurs web depuis 2008, selon StatCounter. vignette|Chronologie des navigateurs Web. L’évolution de l'usage des navigateurs Web est l'évolution de l'usage du logiciel de navigation web que les internautes ont observée à travers le temps. Elle est la conséquence d'une compétition entre les sociétés développant ces logiciels pour dominer le marché. Cette évolution a surtout été marquée par le combat entre Internet Explorer et Netscape Navigator (en particulier sur la plate-forme Windows) à la fin des années 1990.
Graphe cordalthumb|Un cycle, en noir, avec deux cordes, en vert. Si l'on s'en tient à cette partie, le graphe est cordal. Supprimer l'une des arêtes vertes rendrait le graphe non cordal. En effet, l'autre arête verte formerait, avec les trois arêtes noires, un cycle de longueur 4 sans corde. En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle.
Algorithme de KruskalEn informatique, l'algorithme de Kruskal est un algorithme de recherche d'arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe non-orienté et pondéré. Il a été conçu en 1956 par Joseph Kruskal. On considère un graphe connexe non-orienté et pondéré : chaque arête possède un poids qui est un nombre qui représente le coût de cette arête. Dans un tel graphe, un arbre couvrant est un sous-graphe connexe sans cycle qui contient tous les sommets du graphe.
Algorithme A*En informatique, plus précisément en intelligence artificielle, l'algorithme de recherche A* (qui se prononce A étoile, ou A star en anglais) est un algorithme de recherche de chemin dans un graphe entre un nœud initial et un nœud final tous deux donnés. En raison de sa simplicité il est souvent présenté comme exemple typique d'algorithme de planification, domaine de l'intelligence artificielle.
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.
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.
Automorphisme de graphevignette|On peut définir deux automorphismes sur le graphe maison : l'identité et la permutation qui échange les deux « murs » de la « maison ». En mathématiques et en particulier en théorie des graphes, un automorphisme de graphe est une bijection de l'ensemble des sommets vers lui-même qui préserve l'ensemble des arêtes. On peut voir l'automorphisme de graphes comme un isomorphisme de graphes du graphe dans lui-même. On peut en général s'arranger pour mettre en évidence visuellement les automorphismes de graphes sous forme de symétries dans le tracé du graphe.
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é).
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.
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.
