Informatico
Páginas: 2 (335 palabras)
Publicado: 17 de noviembre de 2010
Licence d’Informatique 2010-2011
8 Novembre 2010
PROJET en Algorithmique des Graphes
Graphes bipartis P5-libres
I. Préliminaires.
Soit G=(S, A) un graphe nonorienté. Nous notons par n le nombre de sommets de G et par m le nombre de ses arêtes. Définition 1. Soit Z un graphe, le graphe G est appelé Z- libre s’il n’existe pasde sous graphe de G isomorphe à Z. Notation 1. Une chaîne sans cordes de k sommets est notée Pk (cf. ci-dessous pour une illustration d’un P5
Un P5
L’objectif duprojet est l’étude des graphes bipartis P5-libres II. Propriétés des graphes bipartis P5-libres
Soit G un graphe biparti, nous noterons par B et par N l’ensemble dessommets blancs et respectivement des sommets noirs de G. Le graphe G sera noté G= (B+N, A). Théorème 1. Soit G= (B+N,A) un graphe biparti et connexe. Alors G est P5-libre si etseulement si tout couple (x,y) des sommets de G vérifie V(x) ⊇V(y) ou V(x) ⊆ V(y), avec V(x), V(y) l’ensemble des voisins de x et respectivement de y. Théorème 2 Soit G=(B+N, A) un graphe biparti et connexe. Alors G est P5-libre si et seulement s’il existe une partition π = B1 + …+ Bh des sommets blancs de G vérifiant : 1. ∀ x,y ∈ Bi, i= 1,…,h, nous avons V(x)=V(y). 2. ∀ x ∈ Bi, ∀ x ∈ Bj, i,j = 1,…,h et i < j, nous avons V(x) ⊃ V(y) (cf. Figure ci-dessous pour une illustration du Théorème 2) B3 B2 B1Un graphe biparti P5-libre
1
Théorème 3. Soit G= (B+N,A) un graphe biparti et connexe. Soit π(B)= B1 + …+ Bl et π(N)= N1 + …+ Nk une partition des sommets blancset respectivement des sommets noirs vérifiant : a) si x et y sont dans la même classe d’une partition alors degré(x)=degré(y) b) ∀ x ∈Bi , ∀ y ∈Bj , i≠j, degré(x)
8 Novembre 2010
PROJET en Algorithmique des Graphes
Graphes bipartis P5-libres
I. Préliminaires.
Soit G=(S, A) un graphe nonorienté. Nous notons par n le nombre de sommets de G et par m le nombre de ses arêtes. Définition 1. Soit Z un graphe, le graphe G est appelé Z- libre s’il n’existe pasde sous graphe de G isomorphe à Z. Notation 1. Une chaîne sans cordes de k sommets est notée Pk (cf. ci-dessous pour une illustration d’un P5
Un P5
L’objectif duprojet est l’étude des graphes bipartis P5-libres II. Propriétés des graphes bipartis P5-libres
Soit G un graphe biparti, nous noterons par B et par N l’ensemble dessommets blancs et respectivement des sommets noirs de G. Le graphe G sera noté G= (B+N, A). Théorème 1. Soit G= (B+N,A) un graphe biparti et connexe. Alors G est P5-libre si etseulement si tout couple (x,y) des sommets de G vérifie V(x) ⊇V(y) ou V(x) ⊆ V(y), avec V(x), V(y) l’ensemble des voisins de x et respectivement de y. Théorème 2 Soit G=(B+N, A) un graphe biparti et connexe. Alors G est P5-libre si et seulement s’il existe une partition π = B1 + …+ Bh des sommets blancs de G vérifiant : 1. ∀ x,y ∈ Bi, i= 1,…,h, nous avons V(x)=V(y). 2. ∀ x ∈ Bi, ∀ x ∈ Bj, i,j = 1,…,h et i < j, nous avons V(x) ⊃ V(y) (cf. Figure ci-dessous pour une illustration du Théorème 2) B3 B2 B1Un graphe biparti P5-libre
1
Théorème 3. Soit G= (B+N,A) un graphe biparti et connexe. Soit π(B)= B1 + …+ Bl et π(N)= N1 + …+ Nk une partition des sommets blancset respectivement des sommets noirs vérifiant : a) si x et y sont dans la même classe d’une partition alors degré(x)=degré(y) b) ∀ x ∈Bi , ∀ y ∈Bj , i≠j, degré(x)
Leer documento completo
Regístrate para leer el documento completo.