PolyarbreEn mathématiques, et notamment en théorie des graphes, un polyarbre (aussi appelé arbre dirigé, arbre orienté ou singly connected network) est graphe orienté acyclique dont le graphe non orienté sous-jacent est un arbre (théorie des graphes). En d'autres termes, si on remplace les arcs par des arêtes, on obtient un graphe non orienté qui est à la fois connexe et sans cycle. Une polyforêt (ou forêt dirigée ou forêt orientée) est un graphe orienté dont le graphe non orienté sous-jacent est une forêt.
Multi-arbreEn combinatoire et en théorie des ordres, le terme multi-arbre peut décrire l'une des deux structures suivantes : un graphe orienté acyclique dans lequel l'ensemble des sommets accessibles depuis un nœud est toujours un arbre, ou un ensemble partiellement ordonné dans lequel il n'existe pas quatre éléments a, b, c, et d qui forment un sous-ordre en diamant, avec et mais où b et c sont incomparables (un tel ensemble ordonné est aussi appelé diamond-free poset (ou ordre partiel sans diamant).
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.
Théorème de KirchhoffDans le domaine de la théorie des graphes, le théorème de Kirchhoff, aussi appelé matrix-tree theorem, nommé d'après le physicien Gustav Kirchhoff, est un théorème donnant le nombre exact d'arbres couvrants pour un graphe non orienté quelconque. C'est une généralisation de la formule de Cayley qui donne ce résultat pour les graphes complets non orientés. Le théorème de Kirchhoff s'appuie sur la notion de matrice laplacienne, définie elle-même comme la différence entre la matrice des degrés et la matrice d'adjacence du graphe.
Codage de PrüferEn mathématiques, le codage de Prüfer est une méthode pour décrire de façon compacte un arbre dont les sommets sont numérotés. Ce codage représente un arbre de n sommets numérotés avec une suite de n-2 termes. Une suite P donnée correspond à un et un seul arbre numéroté de 1 à n. Les suites de Prüfer ont été utilisées pour la première fois par Heinz Prüfer pour démontrer la formule de Cayley en 1918. On peut aussi les utiliser en programmation informatique pour enregistrer la structure d'un arbre de façon plus compacte qu'avec des pointeurs.
Graphe étoilethumb|upright=3|Les graphes en étoile S3, S4, S5 et S6. En mathématiques, et plus particulièrement en théorie des graphes, une étoile Sk est le graphe biparti complet K1,k. On peut aussi le voir comme un arbre avec un nœud et k feuilles, du moins lorsque k > 1. Enfin, on peut le définir comme un graphe connexe dont tous les sommets sauf un sont de degré 1. Certains auteurs définissent toutefois Sk comme l'arbre à k sommets de diamètre maximal 2. Attention, avec cette définition, une étoile n'a que k − 1 feuilles.
Résolution de labyrintheLa résolution de labyrinthe est le problème algorithmique qui consiste à trouver la sortie d'un labyrinthe (modélisé mathématiquement). On peut essayer de trouver la sortie d'un labyrinthe en longeant systématiquement un mur en le gardant, sans jamais le lâcher, à main droite ou à main gauche. Cette idée est vérifiée seulement dans le cas d'un labyrinthe parfait, mais elle peut conduire à explorer la totalité du labyrinthe, c'est-à-dire à passer au moins une fois dans toutes les cellules sans exception.
Graphe chenillethumb|upright=1.2|Un graphe chenille. En théorie des graphes, un graphe chenille ou plus simplement une chenille est un arbre dans lequel tous les sommets sont à distance au plus 1 d'un chemin central. Les graphes chenilles ont d'abord été étudiés dans une série d'articles de Harary et Schwenk. Le nom a été suggéré par A. Hobbs. Harary & Schwenk écrivent de façon colorée : « une chenille est un arbre qui se métamorphose en un chemin lorsque son cocon de points d'extrémité est supprimé ».
List of graphsThis partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see . Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer.
