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.
Arbre (théorie des graphes)En théorie des graphes, un arbre est un graphe acyclique et connexe. Sa forme évoque en effet la ramification des branches d'un arbre. Par opposition aux arbres simples, arbres binaires, ou arbres généraux de l'analyse d'algorithme ou de la combinatoire analytique, qui sont des plongements particuliers d'arbres (graphes) dans le plan, on appelle parfois les arbres (graphes) arbres de Cayley, car ils sont comptés par la formule de Cayley. Un ensemble d'arbres est appelé une forêt.
Graphe fortement régulierEn théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe régulier. Soit G = (V,E) un graphe régulier ayant v sommets et degré k. On dit que G est fortement régulier s'il existe deux entiers λ et μ tels que Toute paire de sommets adjacents a exactement λ voisins communs. Toute paire de sommets non-adjacents a exactement μ voisins communs. Un graphe avec ces propriétés est appelé un graphe fortement régulier de type (v,k,λ,μ).
Chordal bipartite graphIn the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has a chord, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows. Chordal bipartite graphs have various characterizations in terms of perfect elimination orderings, hypergraphs and matrices.
Well-covered graphIn graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970. The well-covered graphs include all complete graphs, balanced complete bipartite graphs, and the rook's graphs whose vertices represent squares of a chessboard and edges represent moves of a chess rook.
Perfect graph theoremIn graph theory, the perfect graph theorem of states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by , and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs. A perfect graph is an undirected graph with the property that, in every one of its induced subgraphs, the size of the largest clique equals the minimum number of colors in a coloring of the subgraph.
PlanarizationIn the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph. Planarization may be performed by using any method to find a drawing (with crossings) for the given graph, and then replacing each crossing point by a new artificial vertex, causing each crossed edge to be subdivided into a path. The original graph will be represented as an immersion minor of its planarization.
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.
