× RIP ! L'équipe de développement annonce l'arête de développement du site.

Connaissez-vous la théorie des graphes ?

2

La théorie des graphes est, avec la combinatoire, une des pierres angulaires de ce qu’il est commun de désigner par mathématiques discrètes1.

En 1935 le mathématicien suisse Leonhard Euler présenta un article à l’Académie de Saint-Pétersbourg, publié en 1741, le traitait du problème des sept ponts de Königsberg. Le problème consistait à trouver une promenade à partir d’un point donné qui fasse revenir à ce point en passant une fois et une seule par chacun des sept ponts de la ville de Königsberg. Euler avait formulé qu’un graphe n’est eulérien que si chaque sommet a un nombre pair d’arêtes. L’usage est de s’y référer comme théorème d’Euler, bien que la preuve n’y ait été apportée que 130 ans plus tard par le mathématicien allemand Carl Hierholzer.

 Un problème similaire consiste à passer par chaque sommet exactement une fois, et fut d’abord résolu avec le cas particulier d’un cavalier devant visiter chaque case d’un échiquier par le théoricien d’échec arabe Al-Adli dans son ouvrage Kitab ash-shatranj paru vers 840  (901 ans avant l’article de Euler) et perdu depuis. Ce problème du cavalier fut étudié plus en détails au XVIIIe siècle par les mathématiciens français Alexandre-Théophile Vandermonde, Pierre Rémond de Montmort et Abraham de Moivre; le mathématicien britannique Thomas Kirkman (en) étudia le problème plus général du parcours où on ne peut passer par un sommet qu’une fois, mais un tel parcours prit finalement le nom de chemin hamiltonien d’après le mathématicien irlandais William Rowan Hamilton, et bien que ce dernier n’en ait étudié qu’un cas particulier.2

  Cependant, elle n’a reçu qu’assez tardivement une attention soutenue de la part de la communauté mathématique. En effet, on peut dire que les premiers développements majeurs de la théorie des graphes datent du milieu du vingtième siècle (n. Biggs, C. Berge, W.T. Tutte, …) . Ainsi, un des premiers ouvrages, si pas le premier, traitant de théorie des graphes « Theorie der endlichen und unendlichen Graphen » écrit par König remonte à 1936. Depuis cette époque, la théorie des graphes s’est largement développée et fait à présent partie du cursus standard  en mathématiques de bon nombre d’universités.3

1

Ceci dit, qu’es- ce qu’un graphe ?

Un graphe  G =(V,E) est essentiellement défini par une relation binaire

E ⊆ V x V sur un ensemble V le plus souvent fini. Les graphes sont utilisés pour modéliser de nombreuses situations et leurs applications sont par conséquent aussi nombreuses que variées : dans d’autres branches des mathématiques (algèbre, combinatoire, . .  ) , en informatique, en recherche opérationnelle (tournées de distribution, ordonnancement de tâches, construction de circuits imprimés, . . . ), en cartographie (coloriage de cartes), en chimie, etc . . . .

 

Au côté algébrique de la théorie des graphes, on s’intéresse, à cet élément mathématique point de vue caractéristique ou propriétés ;  à titre d’exemple ;  un graphe peut-être représenté par plusieurs matrices (notamment la matrice d’adjacence), et les valeurs propres d’une matrice constituent son spectre ; il s’agit de la théorie spectrale des graphes, on cite aussi les morphismes de graphe, et tout ceci s’inscrit dans le vaste domaine ; la théorie algébrique des graphes.

Par essence, en mathématiques discrètes et a fortiori en théorie des graphes, de nombreux raisonnements ont une composante combinatoire importante.

Ainsi, des preuves pouvant être jugées “difficiles” consistent souvent en une succession, parfois longue, de raisonnements simples (mais pas toujours aisés à saisir).

 

[divider]

1 Appelées aussi mathématiques finies, ce sont l’étude des structures mathématiques fondamentalement discrètes, la notion de continuité n’étant  pas exigée ou supportée.

http://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes#D.C3.A9finition_de_graphe_et_vocabulaire

Théorie des graphes, Michel Rigo, Université de Liège- Faculté des sciences

Département de mathématiques

 

Categories: Articles, mathématiques

A propos de l'auteur :

Hamza Abouabid étudiant en 3 année physique au sien de la faculté des sciences Ain Chock Casablanca , Admin des sites coursfaciles.com et AB7AT.COM

a écrit 73 articles sur le site :).

Suivez moi sur :

Laissez un commentaire


  • RSS
  • Youtube
  • Digg
  • Facebook
  • Twitter
  • Linkedin
  • Partenaire

  • Articles :


    100 de100 | 100 vote 68 point de vue visiteur