Êtes-vous sûr de vouloir faire cela ?

- programme

| 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

De Milleville Hervé

admin scolarite

Pau

(0)

Module
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 : ING1

- 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
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
Prérequis et postrequis
Pédagogie et évaluation
Pédagogie et évaluation

L'examen est sur papier avec documents.

Bibliographie
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
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é | Publiée | 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é | Publiée | 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é | Publiée | 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é | Publiée | 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é | Publiée | 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