Graphes eulériens

COLORATIONS :[pic 1]

W(G) plus grande clique

α(g) le plus grand stable                                 

X(G) coloration minimum, nombre chromatique

X(Kn) = n, X(Cn) = 2 si n est pair, χ(Cn) = 3 si n est impair (n : nombre de sommets)

Soit G un graphe quelconque. Alors, χ(G) ≥ ω(G).

Soit G un graphe à n sommets. Alors, χ(G) ≥ n/α(G).

W(G) ≤ X(G) = ∆(G) +1 si (G=Ka) ou cycle impair

n/α(G) ≤ X(G) ≤ = ∆(G)  

Soit G un graphe quelconque. Alors, χ(G) ≤ ∆(G) + 1.

(Théorème de Brooks). Pour tout graphe G, on a χ(G) ≤ ∆(G), sauf si G est un graphe complet ou un cycle de longueur impaire.

PLANARITE :

(Le théorème de Kuratowski). Un graphe G est planaire si et seulement si G ne contient pas de subdivision de K5 ni de K3,3.

[pic 2]

(Formule d’Euler). Soit G un graphe connexe plongé dans le plan. Soient n, m et f le nombre de sommets, arêtes et faces de G, respectivement. Alors on a n − m + f = 2.

EULERIENS / HAMILTONIEN :

Un graphe G est eulérien si et seulement si G est connexe, et tout sommet de G est de degré pair.

Un graphe G contient une chaîne eulérienne si et seulement si précisément deux sommets de G sont de degré impair.

CARTES :

On considère les mains de 5 cartes que l’on peut extraire d’un jeu de 52 cartes. L’ordre des cartes dans la main ne joue aucun rôle.

Combien y a-t-il de mains différentes ? 52 5 = 2598960

Combien y a-t-il de mains comprenant exactement un as ? 4.(48 I 4) = 778320

Combien y a-t-il de mains comprenant au moins un valet ? (52 I 5) − (48 I 5) = 886656.

Combien y a-t-il de mains comprenant (à la fois) au moins un roi et au moins une dame ?

(50 I 5) − 2 (48 I 5) + (44 I 5) = 260360.

À partir d’un jeu ordinaire de 52 cartes, on compose une main de trois cartes. Combien existe-t-il de façons différentes de composer

.trois as ? (4 I 3) = 4   ;   trois cœurs ? (13 I 3)   ; trois cartes d’une même couleur ?  4.(13 I 3)

une paire ? (deux cartes de même rang et une autre de rang différent)   [pic 3]

 trois couleurs différentes ? [pic 4]

RECURRENCE :

Démontrer par récurrence forte sur le nombre d’arêtes que |E| ≥ |V | − 1. 

 Soit P(n) la proposition “tout graphe connexe avec au plus m arêtes a au plus m + 1 sommets”. Cas de base : P(0). Un graphe connexe sans arêtes a au plus 1 sommet, donc n ≤ m + 1. Supposons que P(m) est vrai, et soit G un graphe connexe avec m+1 arêtes. Soit e une arête quelconque de G. Le graphe G 0 = G−e a m arêtes et au plus deux composantes connexes. Si G 0 est connexe, alors n ≤ m + 1 < m + 2. Si G 0 n’est pas connexe, G 0 consiste de deux composantes connexes G1 et G2. Par l’hypothèse de récurrence, n1 ≤ m1 + 1 et n2 ≤ m2 + 1 donc n ≤ m + 2 = (m + 1) + 1. Donc, P(m + 1) est vrai.

...