Graph embeddingIn topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that: the endpoints of the arc associated with an edge are the points associated with the end vertices of no arcs include points associated with other vertices, two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold.
Tri topologiqueEn théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe acyclique orienté (ou dag, de l'anglais directed acyclic graph) est un ordre total sur l'ensemble des sommets, dans lequel s précède t pour tout arc d'un sommet s à un sommet t. En d'autres termes, un tri topologique est une extension linéaire de l'ordre partiel sur les sommets déterminés par les arcs. Soit un graphe orienté avec et . Un ordre topologique sur ce graphe peut donner par exemple la succession des sommets 7, 1, 2, 9, 8, 4, 3, 5, 6.
Coloration des arêtes d'un graphethumb|Coloration des arêtes du graphe de Desargues avec trois couleurs. En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs.
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 .
Graphe orienté acycliqueEn théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.
Théorie topologique des graphesEn mathématiques, la théorie topologique des graphes est une branche de la théorie des graphes . Elle étudie entre autres les plongements de graphes dans des surfaces, les graphiques en tant qu'espaces topologiques ainsi que les immersions de graphes. Un plongement d'un graphe dans une surface donnée, une sphère par exemple, est une façon de dessiner ce graphe sur cette surface sans que deux arêtes se croisent. Un problème fondamental de la théorie topologique des graphes, souvent présenté comme un casse - tête mathématique, est le problème des trois chalets.
Stable (théorie des graphes)thumb|280px|L'ensemble des sommets en bleu dans ce graphe est un stable maximal du graphe. En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient. La taille maximum d'un stable d'un graphe, noté I(G), est un invariant du graphe. Il peut être relié à d'autres invariants, par exemple à la taille de l'ensemble dominant maximum, noté dom(G).
Sommet (théorie des graphes)vignette|Dans ce graphe, les sommets 4 et 5 sont voisins alors que les sommets 3 et 5 sont indépendants. Le degré du sommet 4 est égal à 3. Le sommet 6 est une feuille. En théorie des graphes, un sommet, aussi appelé nœud et plus rarement point, est l'unité fondamentale d'un graphe. Deux sommets sont voisins s'ils sont reliés par une arête. Deux sommets sont indépendants s'ils ne sont pas voisins. alt=A small example network with 8 vertices and 10 edges.|vignette|Réseau de huit sommets (dont un isolé) et 10 arêtes.
Tracé de graphesEn théorie des graphes, le tracé de graphes consiste à représenter des graphes dans le plan. Le tracé de graphes est utile à des applications telles que la conception de circuits VLSI, l'analyse de réseaux sociaux, la cartographie, et la bio-informatique. Les graphes sont généralement représentés en utilisant des points, disques ou boites pour représenter les sommets, et des courbes ou des segments pour représenter les arêtes. Pour les graphes orientés, on utilise habituellement ses flèches en bout d'arête pour représenter l'orientation.
Graphe planaireDans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs.
Edge coverIn graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time. Formally, an edge cover of a graph G is a set of edges C such that each vertex in G is incident with at least one edge in C.
Voisinage (théorie des graphes)En théorie des graphes on dit que deux sommets d'un graphe non-orienté sont voisins ou adjacents s'ils sont reliés par une arête. Le voisinage d'un sommet peut désigner l'ensemble de ses sommets voisins ou bien un sous-graphe associé, par exemple le sous-graphe induit. Dans un graphe orienté, on emploie généralement le terme de prédécesseur ou de successeur. Dans un graphe non orienté , le voisinage d'un sommet , souvent noté (N pour neighbourhood) peut désigner plusieurs choses : L'ensemble des sommets voisins : Les sous-graphe de induit par les sommets précédents, avec ou sans selon les versions.
Parcours de grapheEn théorie des graphes, un parcours de graphe est un algorithme consistant à explorer les sommets d'un graphe de proche en proche à partir d'un sommet initial. Un cas particulier important est le parcours d'arbre. Le mot parcours est également utilisé dans un sens différent, comme synonyme de chemin (un parcours fermé étant un circuit). Il existe de nombreux algorithmes de parcours. Les plus couramment décrits sont le parcours en profondeur et le parcours en largeur.
Graphe cycleLes graphes cycles, ou n-cycles, forment une famille de graphes. Le graphe cycle est constitué d'un unique cycle élémentaire de longueur n (pour ). C'est un graphe connexe non-orienté d'ordre n à n arêtes. Il est 2-régulier, c'est-à-dire que chacun de ses sommets est de degré 2. Beaucoup de termes sont employés pour désigner le graphe cycle : n-cycle, polygone et n-gone. Le terme de graphe cyclique est parfois employé, mais il pose problème car il s'oppose normalement à graphe acyclique. Nombre chromatique.
Line graphEn théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes.
Graphe de PetersenLe graphe de Petersen est, en théorie des graphes, un graphe particulier possédant et . Il s'agit d'un petit graphe qui sert d'exemple et de contre-exemple pour plusieurs problèmes de la théorie des graphes. Il porte le nom du mathématicien Julius Petersen, qui l'introduisit en 1898 en tant que plus petit graphe cubique sans isthme dont les arêtes ne peuvent être colorées avec trois couleurs. Il a cependant été mentionné par Alfred Kempe pour la première fois auparavant, en 1886.
Théorie des graphesvignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs.
Segment (mathématiques)vignette|Le segment . En géométrie, un segment de droite (souvent abrégé en « segment ») est une portion de droite délimitée par deux points, appelés extrémités du segment. Un segment reliant deux points et est noté ou et représente la partie de la droite qui se situe « entre » les points et . Intuitivement, un segment correspond à un fil tendu entre deux points, en négligeant l’épaisseur du fil et la déformation due à son poids.
Graphe (mathématiques discrètes)Dans le domaine des mathématiques discrètes, la théorie des graphes définit le graphe, une structure composée d'objets et de relations entre deux de ces objets. Abstraitement, lesdits objets sont appelés sommets (ou nœuds ou points), et les relations entre eux sont nommées arêtes (ou liens ou lignes). On distingue les graphes non orientés, où les arêtes relient deux sommets de manière symétrique, et les graphes orientés, où les arêtes, alors appelées arcs (ou flèches), relient deux sommets de manière asymétrique.
Graphe completEn théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux, c'est-à-dire que tout couple de sommets disjoints est relié par une arête. Si le graphe est orienté, on dit qu'il est complet si chaque paire de sommets est reliée par exactement deux arcs (un dans chaque sens). Un graphe complet est un graphe dont tous les sommets sont adjacents. À isomorphisme près, il n'existe qu'un seul graphe complet non orienté d'ordre n, que l'on note .
