Théorie des Graphes


Cette partie du cours MOMIrandum s'intéresse aux aspects "théoriques" des graphes. On y donne les principales définitions et propriétés nécessaires à l'utilisation des graphes dans les domaines "classiques" vus en école d'ingénieurs.


Définition d'un graphe et de ses caractéristiques principales :

graphe - graphe orienté - graphe non orienté - graphe valué

sommet - arc - arête - prédécesseur - successeur - fonction "Γ"

chaîne / chemin - cycle / circuit - boucle

Représentation mathématique d'un graphe

matrice d'adjacence - matrice d'indicence - matrice des degrés

Autres définitions et propriétes

rang

connexité - forte connexité

arbre et arborescence

fermeture transitive

...


Cette partie "théorie des graphes" est complétée :

- d'une part par le cours portant sur les algorithmes généraux de manipulation des graphes (détection de circuit, parcours, ...) ;

- d'autre part par les cours relatifs aux types de problèmes classiques associés aux graphes : chemin optimum, ordonnancement, flot.