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 V_H \subset V_G et E_H \subset E_G. 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 E_H \subset E_G. 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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”