Éléments de théorie des graphes 42513

Extrait / Introduction

Extrait / Introduction :

I Préambule...................... II Définitions et terminologie Graphe orienté GO Graphe non orienté GNO................. Degré d’un graphe Chemin Types de graphes...... Arbre................. Graphe complet (clique) Graphe biparti Graphe valué ou pondéré ................. Hypergraphe ................................... III Problèmes de coloration Résolution du problème de coloration........... Méthode pour trouver toutes les colorations possibles Heuristique .......... Applications ............... IV Problèmes de cheminsMatrice d’adjacence ... Plus court chemin V Problèmes d’ordonnancementMéthode française MPM (Méthode Potentiel Métra). Dates « au plus tôt ».......................................... Dates « au plus tard »......................................... Exploitation de ce graphe .................................. Méthode américaine : PERT....................................... VI Automates....................... Automates avec actionsVII Arbres couvrants .............. VIII Graphes planaires ............. Coloration de graphes planaires...............

Plan

Plan :

I Préambule...................... II Définitions et terminologie Graphe orienté GO Graphe non orienté GNO................. Degré d’un graphe Chemin Types de graphes...... Arbre................. Graphe complet (clique) Graphe biparti Graphe valué ou pondéré ................. Hypergraphe ................................... III Problèmes de coloration Résolution du problème de coloration........... Méthode pour trouver toutes les colorations possibles Heuristique .......... Applications ............... IV Problèmes de cheminsMatrice d’adjacence ... Plus court chemin V Problèmes d’ordonnancementMéthode française MPM (Méthode Potentiel Métra). Dates « au plus tôt ».......................................... Dates « au plus tard »......................................... Exploitation de ce graphe .................................. Méthode américaine : PERT....................................... VI Automates....................... Automates avec actionsVII Arbres couvrants .............. VIII Graphes planaires ............. Coloration de graphes planaires...............

Signaler un abus