Sous-graphe
- Sous-graphe
-
En théorie des graphes, un sous-graphe est un graphe contenu dans un autre graphe. Formellement, un graphe H = (VH,EH) est un sous-graphe de G = (VG,EG) si 
et 
. L'ensemble des sommets du sous-graphe H est un sous-ensemble de l'ensemble des sommets de G et l'ensemble de arêtes de H est un sous-ensemble de l'ensemble des arêtes de G
Un sous-graphe couvrant ou graphe partiel est un sous-graphe ayant le même ensemble de sommets que le graphe qui le contient. Formellement, H est un sous-graphe couvrant de G (i.e. H couvre G) si VH = VG et . Ainsi le graphe complet Kn couvre tout graphe simple à n sommets.
Un sous-graphe induit est un sous-graphe défini par un sous ensemble de sommets. Formellement, H est un sous-graphe induit de G si, pour tout couple (x,y) de sommets de H, x est connecté à y dans H si et seulement si x est connecté à y dans G. Autre formulation de la condition : l'ensemble des arêtes de H correspond à l'ensemble des arêtes de G incidentes à deux sommets de H.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Sous-graphe de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
sous-graphe — [sugʀaf] n. m. ÉTYM. XXe (in Larousse, 1975); de sous , et graphe. ❖ ♦ Math. Graphe obtenu à partir d un autre graphe par restriction des règles à une partie du graphe initial … Encyclopédie Universelle
Graphe Planaire — Dans 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… … Wikipédia en Français
Graphe diamant — Représentation du graphe diamant. Nombre de sommets 4 Nombre d arêtes 5 Distribution des degrés 2 (2 sommets) 3 (2 sommets) Rayon 1 … Wikipédia en Français
Graphe roue — Quelques exemples de graphe roue. Notation Wn Nombre de sommets n Nombre d arêtes 2(n … Wikipédia en Français
Graphe de Hoffman-Singleton — Schéma du graphe de Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés … Wikipédia en Français
Graphe de Conway-Smith — Nombre de sommets 63 Nombre d arêtes 315 Distribution des degrés 10 régulier Diamètre 4 Maille 3 Automorphismes 15 120 Propriétés Distance transitif … Wikipédia en Français
Graphe complet — K5 Notation Kn Nombre de sommets n Nombre d arêtes … Wikipédia en Français
Graphe Complet — K5 Notation Kn Nombre de sommets n Nombre d arêtes n(n − 1) / 2 … Wikipédia en Français
Graphe biparti complet — K3,2 Notation Km,n Nombre de sommets m + n … Wikipédia en Français
Graphe Gabriel — Graphe de Gabriel Un graphe de Gabriel est un graphe qui connecte un ensemble de point dans un plan Euclidien. Étant donné un ensemble S de points dans un plan, deux points P et Q de S sont connectés par une arête dans le graphe de Gabriel de S… … Wikipédia en Français
