[CAPES][Oral type I] Graphe

[Anonyme]

Concernant le sujet 2, le cours est assez conséquent sur le théorie des
graphes.
Je trouve le sujet ambigu.
Faut-il se contenter de donner un éventail d'exercices introduisant les
notions ou rester sur le schéma classique Cours + Applications ?

J'ai rendu un mémoire de maîtrise, il y a quelques années sur la théorie des
graphes et dans mon souvenir la partie d'introduction comportait près de 40
pages en définition et résultats simples. Est-il raisonnable dans un sujet
de CAPES de type I de passer sous silence toute cette partie définition ?

Merci d'avance pour vos remarques...

[Anonyme]

Je peux te donner le plan que nous avons fait à l'iufm:
I.Representation d'une situation
On a presenté un probleme(invitaion avec des personne qui ne s'entendent
pas combien peut on inviter de personnes au max?), et on definit graphe
orienté,non orienté, sommets,aretes
On revient à l'exemple.
Def ordre, degré,sous graphe
On revient a l'exemple

Proposition: la somme des degres d'un graphe est egale a deux fois le nbr
d'arete du graphe

II.Recherche d'ensembles d'objets compatibles

Probleme: six produits chimiques dt certains st incompatibles.Combien faut
il de boites differentes pour les transporter?

On va alors resoudre le probleme en effectuant un alogo de coloration

Proposition:Soit d le plus haut degré des sommets d'un graphe alors le nbr
chromatique de ce graphe est inf ou egal a d+1

III.Existence d'un chemin
le fameux pb des ponts de Konigsberg

On def chaine,chaine eulerienne, graphe connexe

Theoreme d'Euler

Resolution du pb

IV Recherche de plus court chemin

Algo de Dijkstra et un exple

Eventuellemt un V sur les graphes proba mais ca va etre dur de rentrer ds
les tps)

Pour les exemples et algo tu les trouve tt simplement dans des livres de
Terminal eco

Bon courage!!!

[Anonyme]

Merci pour les infos