Component (graph theory)In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices.
Arbre de TrémauxEn théorie des graphes, un arbre de Trémaux, pour un graphe non orienté G, est un arbre couvrant de G, enraciné en l'un de ses sommets, avec la propriété que deux sommets qui sont voisins dans G sont reliés l'un à l'autre en tant qu'ascendant et descendant dans l'arbre. Les arbres obtenus par un parcours en profondeur (en anglais depth-first search trees) et les chaînes hamiltoniennes sont des arbres de Trémaux.
Circuit rankIn graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph (the size of a cycle basis). Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula where m is the number of edges in the given graph, n is the number of vertices, and c is the number of connected components.
Pseudo-forêtvignette|upright=1.2 |Une 1-forêt (une pseudo-forêt maximale), composée de trois 1-arbres En théorie des graphes, une pseudo-forêt est un graphe non orienté, ou même un multigraphe dans lequel chaque composante connexe possède au plus un cycle. De manière équivalente, une pseudo-forêt est un graphe dans lequel deux cycles ne sont pas connectés par une chaîne. Un pseudo-arbre est une pseudo-forêt connexe. Les noms évoquent l'analogie avec les arbres et les forêts plus couramment étudiés : un arbre est un graphe connexe sans cycle ; une forêt est une union disjointe d'arbres.
Arbre couvrantDans le domaine mathématique de la théorie des graphes, un arbre couvrant d'un graphe non orienté et connexe est un arbre inclus dans ce graphe et qui connecte tous les sommets du graphe. De façon équivalente, c'est un sous-graphe acyclique maximal, ou encore, un sous-graphe couvrant connexe minimal. Dans certains cas, le nombre d'arbres couvrants d'un graphe connexe est facilement calculable. Par exemple, si lui-même est un arbre, alors , tandis que si est un n-cycle, alors .
Maille (théorie des graphes)En théorie des graphes, la maille d'un graphe est la longueur du plus court de ses cycles. Un graphe acyclique est généralement considéré comme ayant une maille infinie (ou, pour certains auteurs, une maille de −1). La maille d'un graphe est la longueur du plus court de ses cycles. Image:Petersen graph blue.svg|Le [[graphe de Petersen]] a une maille de 5 et est une cage. Image:Heawood_Graph.svg|Le [[graphe de Heawood]] a une maille de 6 et est une cage. Image:Frucht_graph.neato.
Complexité paramétréeEn algorithmique, la complexité paramétrée (ou complexité paramétrique) est une branche de la théorie de la complexité qui classifie les problèmes algorithmiques selon leur difficulté intrinsèque en fonction de plusieurs paramètres sur les données en entrée ou sur la sortie. Ce domaine est étudié depuis les années 90 comme approche pour la résolution exacte de problèmes NP-complets. Cette approche est utilisée en optimisation combinatoire, notamment en algorithmique des graphes, en intelligence artificielle, en théorie des bases de données et en bio-informatique.
Morphisme de graphesUn morphisme de graphes ou homomorphisme de graphes est une application entre deux graphes (orientés ou non orientés) qui respecte la structure de ces graphes. Autrement dit l'image d'un graphe dans un graphe doit respecter les relations d'adjacence présentes dans . thumb|alt=Un homomorphisme entre deux graphes|Le graphe de gauche se projette dans le graphe de droite, par exemple de cette façon là Si et sont deux graphes dont on note les sommets V(G) et V(H) et les arêtes E(G) et E(H), une application qui envoie les sommets de G sur ceux de H est un morphisme de graphes si : , .
Biconnected componentIn graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components.
Test de planaritéEn théorie des graphes, le problème du test de planarité est le problème algorithmique qui consiste à tester si un graphe donné est un graphe planaire (c'est-à-dire s'il peut être dessiné dans le plan sans intersection d'arêtes). Il s'agit d'un problème bien étudié en informatique pour lequel de nombreux algorithmes pratiques ont été donnés, souvent en décrivant de nouvelles structures de données. La plupart de ces méthodes fonctionnent en temps O(n) (temps linéaire), où n est le nombre d'arêtes (ou de sommets) du graphe, ce qui est asymptotiquement optimal.
Mineur (théorie des graphes)La notion de mineur d'un graphe est un concept de théorie des graphes. Il a été défini et étudié par Robertson et Seymour dans une série d'articles intitulée Graph minors (I à XXIII), publiée dans le Journal of Combinatorial Theory entre 1983 et 2011. Soit un graphe non orienté fini. Un graphe est un mineur de s'il peut être obtenu en contractant des arêtes d'un sous-graphe de .
Circle packing theoremThe circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in general, on any Riemann surface) whose interiors are disjoint. The intersection graph of a circle packing is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent.
