Remerciez-le!

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

Théorie des graphes et optimisation Chapitre 0: Introduction générale Khaoula B

Théorie des graphes et optimisation Chapitre 0: Introduction générale Khaoula BOUAZZI khaoula.bouazzi@ensi-uma.tn 2017/2018 1 K.BOUAZZI Théorie des graphes et optimisation Objectif Ce module s'adresse aux étudiants de deuxième année licence fondamentale en science de l’informatique (2eme IMM). Son bute est de familiariser et d'initier les étudiants à la notion et aux algorithmes d’optimisations. Après ce cours, un étudiant doit être capable de modéliser la structure et les applications des problèmes sous forme des graphes. Pré-requis : Algorithmique et structure des données, Atelier de Programmation, Algèbre. K.BOUAZZI Théorie des graphes et optimisation 2 Chapitre 0: Introduction générale Plan du cours de théorie des graphes 0. Introduction général 1.Elément fondamentaux de la théorie des graphes 2.Optimisation 3.Chemins optimaux dans les graphes 4.Problème des graphes 5.Recherche opérationnel & Programmation linéaire (Optionnel) 6.Réseaux de Pétri et chaine de Markov (Optionnel) 3 K.BOUAZZI Théorie des graphes et optimisation Evaluation de module de théorie des graphes et Optimisation 1.Note de séduite : Note des compte rendu+contribution au classe + présence 2.Note Devoir surveillé 3.Note examen 4 K.BOUAZZI Théorie des graphes et optimisation Références 1. THE FASCINATING WORLD OF GRAPH THEORY , Arthur Benjamin, Gary Chartrand , Ping Zhang, PRINCETON UNIVERSITY PRESS, PRINCETON AND OXFORD 2005. 2. http://www.le-dictionnaire.com/definition.php?mot=graphe , 12/01/2018. 3. https://fr.vikidia.org/wiki/Probl%C3%A8me_des_sept_ponts_de_K%C3% B6nigsberg 12/01/2018 5 K.BOUAZZI Théorie des graphes et optimisation Plan du cours de théorie des graphes 1.Définition de théorie des graphes 2.Historique de la théorie des graphes 3.Application de notion des graphes 4.Exercice 6 K.BOUAZZI Théorie des graphes et optimisation Chapitre 1: Introduction générale Définition de théorie des graphes 7 K.BOUAZZI Théorie des graphes et optimisation Définition d’un graphe:  En Mathématiques: Courbe représentative d’une fonction. En Dessin: Graffiti, dont les lettres ont un volume. En théorie des graphes : Objet de mathématiques combinatoires [2]généralisant le concept de relation binaire et celui de polyèdre, pouvant être représenté par un schéma reliant des sommets par des arcs ou des arêtes. K.BOUAZZI Théorie des graphes et optimisation 8 Chapitre 1: Introduction générale Introduction D’après Leonhard EULER en 1736 : « Théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de « points », appelés nœuds ou sommets (en référence aux polyèdres), et de « liens » entre ces points ; ces liens sont souvent symétriques (les graphes sont alors dits non orientés) et sont appelés des arêtes. » K.BOUAZZI Théorie des graphes et optimisation 9 Chapitre 1: Introduction générale Introduction Dans le livre THE FASCINATING WORLD OF GRAPH THEORY (2005) , les auteurs ont définit la théorie des graphes par : «The mathematical structure known as a graph has the valuable feature of helping us to visualize, to analyze, to generalize a situation or problem we may encounter and, in many cases, assisting us to understand it better and possibly find a solution.» K.BOUAZZI Théorie des graphes et optimisation 10 Chapitre 1: Introduction générale Introduction Dans le livre THE FASCINATING WORLD OF GRAPH THEORY, les auteurs ont définit la théorie des graphes par : «La structure mathématique connue sous le nom de graphe a la fonction précieuse de nous aider à visualiser, analyser, généraliser une situation ou un problème que nous pouvons rencontrer et, dans de nombreux cas, nous aider à mieux le comprendre et éventuellement trouver une solution.» K.BOUAZZI Théorie des graphes et optimisation 11 Chapitre 1: Introduction générale Chapitre 1: Introduction générale Historique de la théorie des graphes 12 K.BOUAZZI Théorie des graphes et optimisation Historique de la théorie des graphes L’histoire de la théorie des graphes débute peut-être avec les travaux d’Euler au 17éme siècle et trouve son origine dans l’étude de certains problèmes, tels que celui des ponts de Königsberg K.BOUAZZI Théorie des graphes et optimisation 13 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg La ville de Königsberg (Kaliningrad) est située sur les bord de la rivière Pregel en Prusse orientale. Elle en occupe les deux rives ainsi que deux iles. Au 17ème siècle, les 4 parties de la ville étaient réunie par 7 ponts, conformément au plan suivant: K.BOUAZZI Théorie des graphes et optimisation 14 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg K.BOUAZZI Théorie des graphes et optimisation 15 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg K.BOUAZZI Théorie des graphes et optimisation 16 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg Présentez les sept ponts de Königsberg par un graphe simple. K.BOUAZZI Théorie des graphes et optimisation 17 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg K.BOUAZZI Théorie des graphes et optimisation 18 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg K.BOUAZZI Théorie des graphes et optimisation 19 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg K.BOUAZZI Théorie des graphes et optimisation 20 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg K.BOUAZZI Théorie des graphes et optimisation 21 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg Première schématisation: Quatre zones A, B, C, D sept ponts qui les relient. K.BOUAZZI Théorie des graphes et optimisation 22 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg Simplifions encore: Quatre sommets et sept arêtes K.BOUAZZI Théorie des graphes et optimisation 23 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg Problème présentation: Étant donné que la ville est construite sur deux îles reliées par sept ponts, trouver un chemin quelconque permettant, à partir d'un point de départ au choix, de passer une et une seule fois par chaque pont, et de revenir à son point de départ (étant entendu qu'on ne peut traverser l'eau qu'en passant par les ponts !).Sa résolution fut recherchée par ses habitants tout au long du17éme siècle. K.BOUAZZI Théorie des graphes et optimisation 24 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg Question : peut-on faire une promenade en ville en passant une et une seule fois par chaque pont ? K.BOUAZZI Théorie des graphes et optimisation 25 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg Léonhard Euler (1736) a montré que le problème des sept ponts de Königsberg n'a pas de solution, [3] en appliquant une méthode de son invention, jetant ainsi les bases de la théorie des graphes. K.BOUAZZI Théorie des graphes et optimisation 26 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg Démonstration : Les deux contraintes importantes sont : 1. Le promeneur doit revenir à son quartier de départ à la fin de son parcours, c’est-à-dire suivre ce qu’on appelle un cycle. 2. Chaque pont doit être traversé une fois exactement (on appelle aujourd’hui « cycle eulérien » un tel cycle). K.BOUAZZI Théorie des graphes et optimisation 27 Chapitre 1: Introduction générale Historique: Problème de sept ponts de Königsberg Démonstration : Euler a remarqué ceci : chaque pont ne doit être parcouru qu’une fois donc il faut autant de ponts pour quitter un quartier que pour y revenir (sinon l’on ne reviendrait jamais au point de départ) ; il faut donc que chaque quartier comporte un nombre pair de ponts. Or, dans la ville de Königsberg, tous les quartiers sont reliés aux autres par un nombre impair de ponts. Par conséquent, il n’existe pas de cycle eulérien possible dans cette ville, et le problème de la promenade par les sept ponts n’a pas de solution ! K.BOUAZZI Théorie des graphes et optimisation 28 Chapitre 1: Introduction générale Définition d’un graphe: K.BOUAZZI Théorie des graphes et optimisation 29 Chapitre 1: Introduction générale Un graphe G est la donnée de : Un ensemble de sommets S; Un ensemble d’arêtes A ; Pour chaque arête i, l’ensemble si de ses sommets. Chapitre 0: Introduction générale Application de notion des graphes 30 K.BOUAZZI Théorie des graphes et optimisation Application des graphes La théorie des graphes s’est alors développée dans diverses disciplines telles que la chimie, la biologie, les sciences sociales. Depuis le début du 18éme siècle, elle constitue une branche à part entière des mathématiques, grâce aux travaux de König, Menger, Cayley puis de Berge et d’Erdös. K.BOUAZZI Théorie des graphes et optimisation 31 Chapitre 1: Introduction générale Application des graphes K.BOUAZZI Théorie des graphes et optimisation 32 Chapitre 1: Introduction générale Application des graphes K.BOUAZZI Théorie des graphes et optimisation Chap 1: Page 33 Chapitre 1: Introduction générale Application des graphes K.BOUAZZI Théorie des graphes et optimisation Chap 1: Page 34 Chapitre 1: Introduction générale Application des graphes K.BOUAZZI Théorie des graphes et optimisation Chap 1: Page 35 Chapitre 1: Introduction générale Application des graphes K.BOUAZZI Théorie des graphes et optimisation Chap 1: Page 36 Chapitre 1: Introduction générale Application des graphes De manière générale, un graphe permet de représenter la structure, les connexions d’un ensemble complexe en exprimant les relations entre ses éléments : réseau de communication, réseaux routiers, interaction de diverses espèces animales, circuits électriques,. . . K.BOUAZZI Théorie des graphes et optimisation 37 Chapitre 1: Introduction générale Application des graphes uploads/Philosophie/ chapitre-0-introduction-generale-converti.pdf