TIPE sur la théorie des graphes

Résumé du document

TIPE sur la théorie des graphes. Programmation en Turbo Pascal. Notions abordées : graphes orientés, pondérés, planaires, connexes, chemin eulérien. Le thème principal traité est l'algorithme de Welsh et Powell pour le célèbre théorème des 4 couleurs.

Extraits

[...] Leonhard Euler avec le problème des sept ponts de Königsberg. Plus récemment Claude Berge a posé les bases de la théorie moderne des graphes. I Différents domaines et types d'interventions. théorie général définition Utililité :Un réseau routier ,un réseau social. Le Web, les automates : . [...]

[...] Théorème : tout graphe planaire est coloriable en 4 couleurs exposé du problème Clorer la carte des régions françaises ci-dessous sans donner la même couleur à deux régions adjacentes (=voisine) utilisation des graphes Construction des graphes de la carte : 1région = 1 sommet 1 arc relie deux sommets représentant deux régions voisines Les régions sont numérotées dans leur décroissant de leur degré (nombre de sommets adjacents) algorithme de Wells et Powell Étape 1 Classer les sommets du graphe dans l'ordre décroissant de leur degré, et attribuer à chacun des sommets son numéro d'ordre dans la liste obtenue. Étape 2 Parcourir la liste dans l'ordre, attribuer une couleur non encore utilisée au premier sommet non encore coloré, et attribuer cette même couleur à chaque sommet non encore coloré et non adjacent à un sommet de cette couleur. Étape 3 S'il reste des sommets non colorés dans le graphe, revenir à l'étape 2. [...]

[...] exemple : A théorème d'Euler problème : trouver un chemin permettant de passer une et une seule fois par chaque pont, et de revenir à son point de départ, ( recherche d'un cycle eulérien théorème d'Euler Théorème : Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair. Les sommets C D A B sont de degré donc la ville n'est effectivement pas traversable Exemple de la maison On constate que les sommets C et E étant impairs, le problème n'a pas de solution. graphes pondérés Un voyageur souhaite se rendre de Berne à Milan. Graphe pondéré : On appelle graphe pondéré, un graphe dont les arêtes (ou les arcs s'il est orienté) ont été affectées d'un nombre appelé poids. [...]

[...] Sinon, la coloration est terminée. programmation en pascal programme program colorer; uses crt; const MAX_SOMMET = 100; MAX_ARETES = 1000; type Arete = RECORD a : integer; b : integer; end; type Graphe = RECORD n : integer; nb_aretes : integer; A : array[ MAX_ARETES] of Arete; end; type Table =RECORD nb_donnees : integer; cases : array[ MAX_SOMMET] of integer; end; type Couleur = array[ MAX_SOMMET] of integer; à une couleur on associe un entier pour faciliter la programation la procedure init servira à initialiser la table comme une table nulle . [...]