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.
Graphe diamantLe graphe diamant est, en théorie des graphes, un graphe possédant 4 sommets et 5 arêtes. Il peut être construit à partir du graphe complet à quatre sommets, K4 en lui retirant une arête quelconque. Il est hamiltonien, une autre façon de le construire étant de partir du graphe cycle C4 et de lui ajouter une arête quelconque. Le nom de graphe diamant est employé au sein de la classification de l'ISGCI (Information System on Graph Classes and their Inclusions).
Perfectly orderable graphIn graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.
K-arbrevignette|Le graphe de Goldner–Harary est un exemple d'un 3-arbre planaire. En théorie des graphes, un k- arbre est un type de graphe non orienté. Un graphe est un k-arbre s'il peut être obtenu de la manière suivante : on part du graphe complet à ( k + 1) sommets, puis on ajoute des sommets tels que, pour un sommet v ajouté, v a exactement k voisins dans le graphe au moment de l'ajout, et ces voisins forment une clique. Les k-arbres sont exactement les graphes de largeur arborescente donnée, maximaux au sens que l'on ne peut pas ajouter d'arêtes sans augmenter leur largeur arborescente.
Factorisation de graphesvignette|200x200px| Une 1-factorisation du graphe de Desargues : chaque classe de couleur est un 1-facteur. droite|vignette|200x200px| Le graphe de Petersen peut être partitionné en un 1-facteur 1 (en rouge) et un 2-facteur 2 (en bleu). Cependant, le graphe n'est pas 1-factorisable. En théorie des graphes, un facteur d'un graphe G est un graphe partiel, c'est-à-dire un graphe qui a le même ensemble de sommets que G et dont les arêtes sont contenues dans celles de G.
Théorème de TuránLe théorème de Turán est un résultat de théorie des graphes extrémaux découvert par Pál Turán. Ce théorème donne une borne supérieure sur le nombre d'arêtes dans les graphes ne contenant pas de cliques plus grosses qu'un paramètre r, et donne une caractérisation des graphes atteignant cette borne, ce sont les graphes de Turán. Ce résultat de 1941 a lancé la théorie des graphes extrémaux et possède de nombreuses preuves. Tout graphe G ayant n sommets, et ne contenant pas de clique de taille plus grande que r (i.
Pursuit–evasionPursuit–evasion (variants of which are referred to as cops and robbers and graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early work on problems of this type modeled the environment geometrically. In 1976, Torrence Parsons introduced a formulation whereby movement is constrained by a graph. The geometric formulation is sometimes called continuous pursuit–evasion, and the graph formulation discrete pursuit–evasion (also called graph searching).
Book embeddingIn graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness.
Graphe de MooreEn théorie des graphes, un graphe de Moore est un graphe régulier dont le nombre de sommets, pour un degré et un diamètre donnés, est maximal. Les graphes de Moore ont été nommés par Alan Hoffman et Robert Singleton en 1960 en hommage à Edward F. Moore, qui avait tenté de décrire et classifier ces graphes. Un graphe de Moore est un graphe régulier de degré d et de diamètre k qui possède un nombre de sommets égal à la borne supérieure : De façon générale, le nombre de sommets d'un graphe de degré maximal d et de diamètre k est inférieur ou égal à cette valeur.
Biconnected graphIn graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices. The property of being 2-connected is equivalent to biconnectivity, except that the complete graph of two vertices is usually not regarded as 2-connected. This property is especially useful in maintaining a graph with a two-fold redundancy, to prevent disconnection upon the removal of a single edge (or connection).
