	Libellé	Visibilité	Publiée	date de création	date de mise à jour
	ING1	SEMI PRIVEE		2010/04/1212/04/2010 16:56	2012/01/2525/01/2012 18:36

module Théorie des graphes (ressource créée le 20/01/2009 17:57 et mise à jour le 05/02/2012 16:01)

Ressources parentes :

Syllabus
Présentation
Contributeurs
Documents
Activités
Travaux
FAQ

Objectifs du module

Objectifs du module

Dans ce cours, on aborde les principaux théorèmes et définitions de la théorie des graphes.

En TD, on s'assure de toujours illustrer les concepts via des exemples de modélisation de problèmes concrets.

Thèmes détaillés

Le cours de théorie des graphes est composé de 5 chapitres :

1. Généralités sur les graphes non orientés

2. Arbres couvrants et arbres couvrants de poids minimal, connectivité

3. Coloration : problème de l'emploi du temps

4. Chaînes, cycles eulériens et hamiltoniens

5. Graphes orientés, recherche arborescente

Prérequis et postrequis

Pédagogie et évaluation

L'examen est sur papier avec documents.

Bibliographie

Jean-Claude Fournier, Théorie de graphes et applications, Lavoisier 2006.
Claude Berge, Graphes, Gauthier-Villars 1983.
Cormen, Leiserson, Rivest, Stein, Introduction to algorithms, 3ème édition, chapitre 22 à 26

Sites Internet

The on-line encyclopedia of integer sequences : https://oeis.org/

Nombre d'arbres en fonction du nombre de sommets : https://oeis.org/A000055

Archives des articles de Pour la science de Jean-Paul Delahaye : http://www2.lifl.fr/~delahaye/pls/

Que le monde est petit ! http://www2.lifl.fr/~delahaye/pls/2003/106.pdf

Les lois de tout ou rien http://www2.lifl.fr/~delahaye/pls/1995/029.pdf

Une propriété cachée des graphes http://www2.lifl.fr/~delahaye/pls/2008/168.pdf

Démocratie et notoriété sur internet http://www2.lifl.fr/~delahaye/pls/2005/135.pdf

Le secret de google http://www2.lifl.fr/~delahaye/pls/2010/193.pdf

La fin des dames anglaises ? http://www2.lifl.fr/~delahaye/pls/2008/165.pdf

interstices.info

Application de la théorie des graphes à Pacman http://interstices.info/pacman

Lexique de la théorie des graphes : http://fr.wikipedia.org/wiki/Lexique_de_la_théorie_des_graphes

Glossary of graph theory : http://en.wikipedia.org/wiki/Glossary_of_graph_theory

Henry Markram builds a brain in a supercomputer http://www.ted.com/talks/henry_markram_supercomputing_the_brain_s_secrets.html

Sebastian Seung : I am my connectome http://www.ted.com/talks/lang/en/sebastian_seung.html

Niveau : ING1 – TRONC COMMUN

ECTS : 1 ects

Volume Horaire : 15 heures

Prérequis : Algorithmique I

Evaluation : Un examen et un projet de pôle.
L'examen est sur papier avec documents.
Le projet de pôle regroupe les matières Java, UML, Théorie des graphes et Algorithmique II et intervient pour 20% de la note finale

Objectif :

Dans ce cours, on aborde les principaux théorèmes et définitions de la théorie des graphes.

En TD, on s'assure de toujours illustrer les concepts via des exemples de modélisation de problèmes concrets.

Contenu

Le cours de théorie des graphes est composé de 5 chapitres :

1. Généralités sur les graphes non orientés

2. Arbres couvrants et Arbres courvrant minimums, Connectivité.

3. Coloration : Problème de l'emploi de temps.

4. Chaînes, Cycles eulériens et hamiltoniens.

5. Graphes Orientés, Recherche Arborescente.

Références :

Jean-Claude Fournier, Théorie de graphes et applications , Lavoisier 2006.
Claude Berge, Graphes, Gauthier-Villars 1983.

Entrez votre message

Objet :

Contenu :

Site :
Groupe :

Nom	Fonction
Ranisavljevic Elisabeth	participe
Bourhattas Abderrahim	responsable
RANISAVLJEVIC Elisabeth	participe
Manolessou Marietta	responsable
Forest Jean-Paul	participe
El Janati Abdessalam	responsable
Le Nir Yannick	participe
BONATO Roberto	participe
Jourdan Marias Astrid	participe
Dujol Romain	participe
Kanawati Maria	participe
ING1 ING1 (Tronc commun)	inscrit
Tous les contributeurs	*

Toutes
Corrigé
Texte Intégral
Série d'exercices
Support de présentation

Libellé	Visibilité	Type	date de création	date de mise à jour	Ressource(s) parente(s)
Corrigé5.pdf	PUBLIQUE	Corrigé	2009/03/1010/03/2009 09:19	2011/03/2525/03/2011 05:16	Graphes Orientés et Recherche arborescente
CorrigéExamen2011.pdf	PUBLIQUE	Corrigé	2011/06/2121/06/2011 09:43	2011/06/2121/06/2011 09:44
Corrigé1	PUBLIQUE	Corrigé	2009/01/2626/01/2009 12:35	2012/01/3131/01/2012 10:46	Généralités
Cours 3: Coloriage de Graphes	PRIVEE	Support de présentation	2009/02/0606/02/2009 18:14	2012/02/0202/02/2012 16:35	Coloriage
cours1.pdf	PRIVEE	Texte Intégral	2009/01/2323/01/2009 10:52	2009/02/0707/02/2009 10:52	Généralités
cours2.pdf	PRIVEE	Support de présentation	2009/01/3030/01/2009 16:46	2011/03/2525/03/2011 05:33	Arbres Couvrants
cours4.pdf	PRIVEE	Support de présentation	2009/02/1616/02/2009 09:14	2011/03/2525/03/2011 05:21	Tournées Eulériennes et Hamiltonniennes
cours5.pdf	PRIVEE	Support de présentation	2009/03/0909/03/2009 09:22	2009/03/2424/03/2009 09:22	Graphes Orientés et Recherche arborescente
TD1.pdf	PRIVEE	Série d'exercices	2009/01/2323/01/2009 13:35	2011/03/2525/03/2011 05:48	Généralités
TD2.pdf	PRIVEE	Série d'exercices	2009/02/0202/02/2009 09:22	2011/03/2525/03/2011 05:24	Arbres Couvrants
TD3 Coloriage	PRIVEE	Série d'exercices	2009/02/0606/02/2009 18:15	2009/02/2121/02/2009 18:15	Coloriage
TD4.pdf	PRIVEE	Série d'exercices	2009/02/1616/02/2009 09:14	2011/03/2525/03/2011 05:22	Tournées Eulériennes et Hamiltonniennes
TD5.pdf	PRIVEE	Série d'exercices	2009/03/0909/03/2009 09:36	2011/03/2525/03/2011 05:19	Graphes Orientés et Recherche arborescente

Libellé	Visibilité	date de création	date de mise à jour	Ressource(s) parente(s)
Corrigé5.pdf	PUBLIQUE	2009/03/1010/03/2009 09:19	2011/03/2525/03/2011 05:16	Graphes Orientés et Recherche arborescente
CorrigéExamen2011.pdf	PUBLIQUE	2011/06/2121/06/2011 09:43	2011/06/2121/06/2011 09:44
Corrigé1	PUBLIQUE	2009/01/2626/01/2009 12:35	2012/01/3131/01/2012 10:46	Généralités

	Libellé	Visibilité	Publiée	date de création	date de mise à jour		Ressource(s) parente(s)
	cours1.pdf	PRIVEE		2009/01/2323/01/2009 10:52	2009/02/0707/02/2009 10:52		Généralités

Libellé	Visibilité	date de création	date de mise à jour	Ressource(s) parente(s)
TD1.pdf	PRIVEE	2009/01/2323/01/2009 13:35	2011/03/2525/03/2011 05:48	Généralités
TD2.pdf	PRIVEE	2009/02/0202/02/2009 09:22	2011/03/2525/03/2011 05:24	Arbres Couvrants
TD3 Coloriage	PRIVEE	2009/02/0606/02/2009 18:15	2009/02/2121/02/2009 18:15	Coloriage
TD4.pdf	PRIVEE	2009/02/1616/02/2009 09:14	2011/03/2525/03/2011 05:22	Tournées Eulériennes et Hamiltonniennes
TD5.pdf	PRIVEE	2009/03/0909/03/2009 09:36	2011/03/2525/03/2011 05:19	Graphes Orientés et Recherche arborescente

Libellé	Visibilité	date de création	date de mise à jour	Ressource(s) parente(s)
Cours 3: Coloriage de Graphes	PRIVEE	2009/02/0606/02/2009 18:14	2012/02/0202/02/2012 16:35	Coloriage
cours2.pdf	PRIVEE	2009/01/3030/01/2009 16:46	2011/03/2525/03/2011 05:33	Arbres Couvrants
cours4.pdf	PRIVEE	2009/02/1616/02/2009 09:14	2011/03/2525/03/2011 05:21	Tournées Eulériennes et Hamiltonniennes
cours5.pdf	PRIVEE	2009/03/0909/03/2009 09:22	2009/03/2424/03/2009 09:22	Graphes Orientés et Recherche arborescente

TD

Libellé	Visibilité	date de création	date de mise à jour
Arbres Couvrants	PRIVEE	2009/01/3030/01/2009 16:46	2009/02/1414/02/2009 16:46
Coloriage	PRIVEE	2009/02/0606/02/2009 18:14	2009/02/2121/02/2009 18:14
Généralités	PRIVEE	2009/01/2323/01/2009 10:39	2009/02/0707/02/2009 10:39
Graphes Orientés et Recherche arborescente	PRIVEE	2009/03/0909/03/2009 09:22	2009/03/2424/03/2009 09:22
Tournées Eulériennes et Hamiltonniennes	PRIVEE	2009/02/1616/02/2009 09:13	2009/03/0303/03/2009 09:13

Pas de ressources dans cette rubrique