Cours Harmonisation Combinatoire
Graphe
G=(V,E) / V est l'ensemble des Sommets et E est l'ensemble des arretes . |V|=n |E|=m (arc => orienté , arretes => non Orienté)
degré: Nb d'arret pour un sommet x ----> d(x)
Theoreme
d(x) = 2m
Corollaire
Nb sommet de degré impair est pair
d(x) { x app V et d(x)=0(2) } pair
+
d(x) { x app V et d(x)=1(2) }
====
2m pair
=>
d(x) { x app V et d(x)=1(2) } est pair
Ex 1 : Montrer qu'un grpahe simple (n>2) il