Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Graphes exos Exercices ? Dans les exemples ci-dessous on a parfois construit les graphes et donné quelques éléments de réponse a ?n d'avoir assez vite une idée générale de ce qui est proposé on indique aussi les contenus illustrés ou introduits dans chacu

Exercices ? Dans les exemples ci-dessous on a parfois construit les graphes et donné quelques éléments de réponse a ?n d'avoir assez vite une idée générale de ce qui est proposé on indique aussi les contenus illustrés ou introduits dans chacun des exemples proposés La théorie des graphes est rarement abordée en France dans le cursus universitaire des enseignants il s'agit donc d'une nouveauté pour la plupart d'entre eux Néanmoins comme s'exerce dans ce domaine un mode de pensée auquel ils sont habitués ils peuvent envisager cet enseignement sans inquiétude tant pour eux-mêmes que pour leurs élèves Exemple les enveloppes Peut-on parcourir une fois et une seule les arêtes des graphes ci-dessous sans lever le crayon ? Contenu introduction des graphes arêtes sommets ordre sommets adjacents degré d ? un sommet cha? ne eulérienne théorème d ? Euler Exemple les ponts de K? nigsberg Au XVIIIème siècle les habitants de K? nigsberg actuellement Kaliningrad région de la Russie frontalière de la Pologne et de la Lituanie aimaient se promener le dimanche La ville de K? nigsberg comprenait ponts disposés selon le schéma ci-dessous Le souhait des habitants de K? nigsberg était de faire un trajet passant une fois et une seule par chaque pont Comment faire ? Contenu introduction des graphes arêtes sommets ordre sommets adjacents degré d ? un sommet cycle eulérien Exemple dominos Peut-on aligner tous les pions d ? un jeu de domino suivant la règle du domino On commencera par étudier la question avec un jeu dont les dominos comportent les chi ?res jusqu'à n pour n Une arête représente un domino Il faut trouver une cha? ne qui permet de parcourir toutes les arêtes une fois et une seule On ne s ? est pas occupé ici des doubles ? puisqu'on peut toujours les intercaler ? Contenu graphes complets cha? nes eulériennes degré d ? un sommet théorème d ? Euler CExemple traversée de frontières Cinq pays sont représentés ci-contre avec leurs frontières Est-il possible de partir d'un pays et d ? y revenir en franchissant chaque frontière une fois et une seule ? Contenu cha? ne eulérienne degré d ? un sommet théorème d ? Euler Exemple dessins de graphes -Parmi les graphes ci-dessous déterminer ceux qui sont susceptibles de décrire une même situation Peut-on dessiner des graphes simples pas d ? arêtes dont les extrémités sont confondues et au plus une arête joignant deux sommets dont la liste des degrés des sommets soit - - - - - - - - - - - - - ? Contenu représentations de graphes degrés de sommets Exemple associer un graphe à une situation Comparer les trois graphes dé ?nis ci-dessous on considère un octaèdre un sommet du graphe est associé à un sommet de l ? octaèdre et une arête correspond à une arête de l ? octaèdre on considère un cube un sommet du graphe est associé à une face du cube et deux sommets du graphe sont reliés par une arête si les