Le
nombre d'or est une
proportion, définie initialement en
géométrie comme l'unique rapport
entre deux longueurs
et
telles que le rapport de la somme des deux longueurs (
) sur la plus grande (
) soit égal à celui de la plus grande (
) sur la plus petite (
) c'est-à-dire lorsque
. Le découpage d'un segment en deux longueurs vérifiant cette propriété est appelé par
Euclide découpage en « extrême et moyenne raison ». Le nombre d'or est maintenant souvent désigné par la lettre
φ (phi).
soit approximativement
1 1,618 033 988 7.
L'histoire de cette proportion commence à une
période imprécise de l'antiquité. À la
Renaissance,
Luca Pacioli, un moine franciscain italien, la met à l'honneur dans un manuel de mathématiques et la surnomme divine proportion en l'associant à un idéal envoyé du ciel. Cette vision se développe et s'enrichit d'une dimension esthétique, principalement au cours des
xixe et
xxe siècles où naissent les termes de section dorée et de nombre d'or.
Le nombre d'or se trouve parfois dans la nature ou des œuvres humaines, comme dans les
capitules du
tournesol ou dans certains monuments à l'exemple de ceux conçus par
Le Corbusier. Il est aussi étudié comme une clé explicative du monde, particulièrement pour la « beauté ». Il est érigé en théorie esthétique et justifié par des arguments d'ordre scientifique ou mystique : omniprésence dans les sciences de la nature et de la vie, proportions du corps humain ou dans les arts comme la peinture, l'architecture ou la musique.
Certains artistes, tels le compositeur
Xenakis ou le poète
Paul Valéry ont adhéré à une partie plus ou moins vaste de cette vision, soutenue par des livres populaires. À travers la médecine, l'archéologie ou les sciences de la nature et de la vie, la science infirme les théories de cette nature
[réf. nécessaire] car elles sont fondées sur des
généralisations abusives et des hypothèses inexactes.
Les triangles
OAB et
OCA sont semblables si et seulement si les longueurs
a et
b respectent la proportion d'or.
Le nombre d'or possède une première définition d'origine géométrique, fondée sur la notion de
proportion :
Définition de la proportion d'or — Deux longueurs strictement positives a et b respectent la « proportion d'or » si et seulement si, le rapport de a sur b est égal au rapport de a + b sur a :
Il existe une interprétation graphique de cette définition, conséquence des propriétés des
triangles semblables illustrée par la
figure 1. Les segments bleus sont de longueur
a et le rouge de longueur
b. Dire que la proportion définie par
a et
b est d'or revient à dire que les triangles
OAB et
OCA sont semblables. Euclide exprime la « proportion d'or », qu'il appelle « extrême et moyenne raison », de la manière suivante :
« Une droite est dite coupée en extrême et moyenne raison lorsque la droite entière est au plus grand segment comme le plus grand segment est au plus petit. »
Le rapport a / b ne dépend pas des deux valeurs a et b, dès lors que ces deux nombres sont en proportion d'extrême et de moyenne raison. Ceci donne une nouvelle définition du nombre d'or :
Définition du nombre d'or — Le nombre d'or est le
nombre réel positif, noté φ, égal à la fraction
a /
b si
a et
b sont deux nombres en proportion d'extrême et de moyenne raison. Il est donné par la formule :
Sa valeur approximative est donc
1 1,618 033 988 7.
La proportion
(1), définissant la proportion d'or, peut être écrite de la manière suivante, obtenue en multipliant l'égalité par
:
Ce qui revient à dire que φ est solution d'une équation du second degré. Cette propriété donne lieu à une troisième définition :
Définition alternative du nombre d'or — Le nombre d'or est l'unique solution positive de l'
équation du second degré suivante :
Cette équation est équivalente à celle indiquant que l'inverse de l'
inconnue x est égal à
x - 1, ce qui implique que le développement décimal de 1/
x est le même que celui de
x, auquel on a retranché sa
partie entière.
Il existe deux modes de définition du nombre d'or, celle
géométrique qui s'exprime en termes de proportion et celle
algébrique qui définit le nombre comme l'unique racine positive d'une équation. Cette double approche permet de résoudre un problème d'algèbre, en l'occurrence une équation du second degré, à l'aide de méthode géométrique, on parle d'
algèbre géométrique.
Rectangle et spirale d'or[modifier]
Les calculs précédents permettent, à l'aide d'une
règle et d'un compas de dessiner une proportion d'extrême et de moyenne raison. La méthode est illustrée sur la figure de gauche. On dessine un cercle de centre
C et de
rayon 1 (en orange). Puis, de l'extrémité du rayon, on élève un segment (en vert) perpendiculaire au rayon, de longueur 1/2, et on trace le cercle de centre
C' et de rayon 1/2. Le segment bleu qui a pour extrémités
C et le point du cercle
C' dans le prolongement de
C C' est de longueur φ.
Rectangles d'or et divine proportion
Cette méthode permet aussi de construire un « rectangle d'or », c'est-à-dire un rectangle de longueur a et de largeur b tel que a et b soient en proportion d'extrême et de moyenne raison. En d'autres termes, un rectangle est dit d'or si le rapport entre la longueur et la largeur est égal au nombre d'or.
Pour tracer un rectangle d'or de longueur a et de largeur b, le plus simple est de dessiner un carré de côté b. En prenant le milieu de la base comme centre, on trace un cercle passant par les deux sommets opposés. L'intersection de la droite prolongeant la base du carré et du cercle détermine l'extrémité de la base du rectangle d'or. Il apparait comme construit par l'adjonction à un carré de côté de longueur b, d'un rectangle de côtés de longueur b et a - b, comme le montre la figure de droite. Un rapide calcul montre que ce rectangle est encore d'or :
Il est possible de réitérer le processus précédent et d'intégrer un carré de côté
a -
b dans le rectangle d'or de côté
b,
a -
b, comme indiqué sur la figure de gauche. Cette méthode peut être prolongée indéfiniment. Si, dans chaque carré est dessiné un quart de cercle d'extrémités deux côtés du carré, comme sur la figure, on obtient une spirale. Ce graphique est une bonne approximation d'une spirale d'or, d'
équation polaire :
Cette spirale est un cas particulier de
spirale logarithmique. Comme toute spirale de cette famille, elle possède une propriété caractéristique, si
A est un point de la spirale, alors la droite passant par le centre de la spirale et
A fait un angle constant avec la
tangente à la spirale en
A. Une telle spirale est dite
équiangle.
D'autres figures se dessinent à l'aide du nombre d'or à l'instar de l'« œuf d'or »
2.
Pentagone et pentagramme[modifier]
Une fois la proportion d'extrême et de moyenne raison construite, il est simple de dessiner un pentagone.
Un
pentagone régulier se construit à l'aide de la proportion d'extrême et moyenne raison. Soit un cercle de diamètre
OP1 et de rayon
a, illustré sur la figure de gauche. Si
b est le nombre réel plus petit que
a tel que
a et
b soient en proportion d'or, et
P2,
P3,
P4 et
P5 les intersections du cercle de diamètre
OP1 avec les deux cercles de centre
O et de rayon
a +
b et
b, alors les cinq points
Pi définissent un pentagone.
Le
pentagramme associé, c'est-à-dire la figure composée des cinq diagonales du pentagone (Cf. figure de droite), contient aussi de multiples proportions d'extrêmes et moyennes raisons. Elles s'expriment simplement à l'aide de
triangles isocèles dont les longueurs des côtés sont en proportion d'or. De tels triangles sont appelés « triangles d'or ». Il en existe de deux types différents, les jaunes ayant une base proportionnelle à
a et deux côtés à
b et les orange ayant une base proportionnelle à
b et deux côtés à
a. Les triangles foncés sont semblables aux plus clairs de même couleur, la proportion entre clair et foncé est encore d'or.
Les triangles jaunes possèdent deux angles de 36°, soit le cinquième d'un
angle plat et un de 108°, soit les trois cinquièmes d'un angle plat. Un tel triangle est parfois appelé « triangle d'argent ». Les triangles orange possèdent deux angles de 72°, soit les deux cinquièmes d'un angle plat et un angle de 36°. Avec des triangles d'or et d'argent dont les côtés sont toujours
a et
b, il est possible de paver intégralement un plan euclidien de manière non périodique. Un tel pavage est dit de
Penrose.
L'analyse des mesures des triangles d'argent et d'or permettent de déterminer les valeurs trigonométriques associées au pentagone. Considérons un triangle d'argent de base φ et donc de côtés adjacents de longueur 1. Ce triangle, coupé en son milieu, comme sur la figure de droite, est un triangle rectangle d'
hypoténuse de longueur 1. Sa base est de longueur φ/2 car elle correspond à la demi-base du rectangle d'argent. On en déduit :
Un raisonnement analogue s'applique au triangle d'or. Les côtés ont toujours une longueur 1, la base est en proportion d'or donc de longueur φ - 1. On en déduit que le cosinus de 72° est égal à (φ - 1)/2. À partir de ces valeurs et de différentes formules, il est possible de calculer les images par les fonctions trigonométriques des multiples ainsi que les moitiés de l'angle 36°.
Une autre manière de déterminer les différentes valeurs caractéristiques d'un pentagone consiste à utiliser le
plan complexe. Les affixes des sommets sont les
racines cinquièmes de l'unité. Comme 5 est un
nombre de Fermat, le
théorème de Gauss-Wantzel a pour conséquence que le pentagone régulier est constructible à la règle et au compas : les racines s'obtiennent par résolutions successives d'équations du second degré. Dans le plan complexe, les affixes des sommets du pentagone sont 1 et les racines du cinquième
polynôme cyclotomique X4+
X3+
X2+
X+1.
[afficher]
Valeurs de fonctions trigonométriques faisant intervenir le nombre d'or
Un autre chemin que celui de la géométrie permet de mieux comprendre les propriétés du nombre d'or, l'
arithmétique. Elle met en évidence ses propriétés
algébriques ainsi que les profondes relations entre des sujets apparemment aussi différents que la
suite de Fibonacci ou sa relation avec de difficiles
équations diophantiennes. Une équation diophantienne est une équation dont les coefficients sont entiers et dont les solutions recherchées sont entières. Pour citer un exemple célèbre, celui-ci correspond à un cas particulier du
dernier théorème de Fermat :
Il fut résolu
3 par
Dirichlet en
1825, ce qui lui valut une célébrité immédiate.
Carl Friedrich Gauss, un mathématicien du
xixe siècle, disait des problèmes de cette nature :
« Leurs charmes particuliers viennent de la simplicité des énoncés jointe à la difficulté des preuves. »4
Fraction continue[modifier]
La
fraction continue est une manière d'approcher un
nombre réel, dans le cas du nombre d'or, elle est simple. On peut l'approcher par les valeurs 1 ou 1 + 1/1. La fraction suivante est plus précise :
Le prolongement à l'infini de cette méthode donne exactement le nombre d'or :
Le fait que la fraction ne s'arrête jamais montre que le nombre d'or n'est pas un
nombre rationnel. Une démonstration est proposée dans l'article détaillé. On reconnaît, sous la première barre de fraction l'expression du nombre d'or. On en déduit plusieurs expressions algébriques de φ :
La dernière formule donne une nouvelle expression du nombre d'or :
Cette propriété possède des conséquences remarquables si φ est utilisé comme base d'un système de nombre (voir
base d'or).
La fraction continue approximant le nombre d'or possède systématiquement la plus petite valeur possible pour chacun de ses coefficients, à savoir 1. En conséquence, il est le nombre irrationnel qui s'approxime le plus mal par des rationnels. On dit de lui qu'il est
le plus irrationnel des
nombres réels5 (cf. Théorème de Hurwitz sur les approximations diophantiennes).
Suite de Fibonacci[modifier]
Le calcul des couples de numérateurs et dénominateurs obtenus par la fraction continue donne les valeurs suivantes (1,1), (2,1), (3,2), (5,3)… le dénominateur correspond au numérateur de la fraction précédente. Il est aussi égal au nième terme de la suite de Fibonacci (un). Elle est définie par récurrence :
Les deux premiers termes sont égaux à 1 et les autres à la somme des deux précédents. Pour obtenir une bonne approximation du nombre d'or, il suffit de choisir une valeur de n suffisamment élevée et considérer la fraction un+1/un. En termes mathématiques, cela s'exprime sous la forme suivante :
Si la suite de Fibonacci permet de déterminer une approximation du nombre d'or, la réciproque est vraie. Plus exactement, on dispose de la formule suivante :
La valeur |1-φ|n ne fait que diminuer lorsque n s'accroît, elle est toujours suffisamment petite pour pouvoir être négligée, il suffit de prendre l'entier le plus proche de l'expression précédente en négligeant le terme en (1 - φ)n, on obtient :
Cette propriété est vérifiée pour toute suite définie par la relation de récurrence un+2 = un+1 + un, indépendamment des valeurs prises par u1 et u2.
Équation diophantienne[modifier]
La fraction continue offre des rationnels b/a offrant presque des solutions à l'équation qui s'écrit sous les formes suivantes :
L'égalité stricte à zéro est impossible, elle n'autorise que les solutions triviales. En effet, aucun nombre rationnel ne vérifie la proportion d'or, ce qui justifie l'équation diophantienne suivante :
Cette identité est liée à l'équation (1) précédente et donc au nombre d'or. Si (a, b) et (c, d) forment deux couples, solutions de l'équation (1), la partie de gauche de l'identité est égale à plus ou moins un. La partie de droite de l'identité décrit donc une solution (e, f) si e = ac + bd et f = ad + bc + bd. La découverte d'une multiplication particulière *, permet de construire autant de solutions que désiré, à partir d'une unique si elle n'est pas triviale :
En combinant une solution (a, b) avec elle-même on en obtient une nouvelle (a2 + b2, 2a.b + b2). Le couple (1, 1) est solution de l'équation (1), donc le couple (2, 3) l'est aussi. Elle est d'ailleurs déjà obtenue avec la méthode précédente. Avec la solution (2, 3) on obtient (13, 21) et avec la solution (13, 21) on obtient (610, 987). On vérifie que le couple (610, 987) est bien une solution de l'équation :
On en déduit que la fraction 987/610 est une excellente approximation du nombre d'or. En effet, 987/610 = 1,618 032 7… une précision proche du millionième.
Entiers de Q(√5)[modifier]
Les nombres de la forme
(avec
a et
b entiers relatifs) forment un ensemble stable par addition et multiplication, qu'on peut d'ailleurs définir de manière plus abstraite par les formules suivantes, sur les couples (
a,
b) :
et
;
on obtient ainsi une structure équipée d'une addition et d'une multiplication, qu'on appelle un
anneau commutatif.
Cet anneau peut aussi être construit à partir d'une équation diophantienne liée au nombre d'or, sa relation avec φ peut ainsi être vue plus directement. Il se conçoit simplement en considérant les nombres réels de la forme a + φ.b, où a et b désignent deux nombres entiers. L'identité de Brahmagupta, définissant la multiplication se lit :
Ainsi les puissances de φ sont tous de la forme a + φ.b, plus précisément φn = un-1 + un.φ, où (un) désigne la suite de Fibonacci.
Ces deux anneaux possèdent des structures
identiques ; le terme consacré pour décrire cette situation est celui d'
isomorphisme. Ce sont deux sous-anneaux du corps des nombres réels, ou du corps
Q(
√5), ensemble des nombres de la forme
a +
b√5, avec
a et
b rationnels. On montre que les nombres de la forme
a + φ.
b, avec
a et
b entiers relatifs, sont les
entiers de Q(√5), c'est-à-dire ceux qui sont racines d'un polynôme de la forme
X2+
cX+
d, avec
c et
d entiers relatifs. L'anneau des entiers de
Q(
√5) est le cadre naturel sous-jacent à toute l'« arithmétique du nombre d'or ». À certains égards, il est analogue à
Z, l'ensemble des entiers naturels. Il est
commutatif, et
intègre. Le terme
intègre signifie que le produit de deux éléments non nuls est non nul. La ressemblance est plus profonde : cet anneau est
euclidien, c'est-à-dire qu'il dispose d'une
division euclidienne semblable à celle de l'arithmétique des entiers
classiques. Les outils de l'arithmétique usuelle sur
Z, comme le
théorème de Bachet-Bézout, le
lemme d'Euclide, le
théorème fondamental de l'arithmétique ou en plus sophistiqué le
petit théorème de Fermat sont tous des conséquences de la division euclidienne. Elle offre des propriétés analogues pour « l'arithmétique du nombre d'or ». Cette analogie profonde pousse les arithméticiens à parler d'entiers pour décrire les éléments de cet ensemble. La compréhension de l'arithmétique de
Z passe souvent par celles des
nombres premiers. Les entiers de
Q(
√5) ont aussi leurs propres
éléments premiers. Un nombre premier de
Z n'est pas toujours premier parmi les entiers de
Q(
√5), comme le montre le contre-exemple 19 :
Cette différence engendre des modifications dans l'application des théorèmes classiques. Par exemple si
p est un nombre premier différent de 5 tel que le reste de sa division euclidienne par 5 soit un
carré parfait, donc égal à 1 ou à 4, le petit théorème de Fermat indique que φ
p-1 - 1 est un multiple de
p. Ceci montre que
up-1 est un multiple de
p ainsi que
up-2 - 1, en effet, φ
p-1 - 1 =
up-2 - 1 +
up-1.φ. Les démonstrations sont proposées dans l'article détaillé.
Fragments d'histoire[modifier]
Pour Thomas L. Heath,
Platon est le premier grec à « oser » étudier les propriétés d'un nombre «scandaleux car irrationnel, celui maintenant appelé « nombre d'or ».
Les historiens
6,7 considèrent que l'histoire du nombre d'or commence lorsque cette valeur est l'objet d'une étude spécifique. Pour d'autres, la détermination d'une figure géométrique contenant au moins une proportion se calculant à l'aide du nombre d'or suffit. La
pyramide de Khéops (vers 2600 av. J.-C.) devient, selon cette dernière convention, un bon candidat pour l'origine
8.
D'autres encore se contentent[évasif] des restes d'un monument dont des dimensions permettent d'approximer le nombre d'or. Selon ce critère, un amas de pierres sous la mer des Bahamas est une origine plus ancienne
9. Ces vestiges, dont l'origine humaine et la datation sont incertaines
10 sont dénommés « temple d'
Andros ».
Les historiens s'accordent tous sur l'existence d'une
origine ancienne[évasif], mais l'absence de document d'époque définitif interdit une connaissance indiscutable de l'origine
11. Dans ce cadre, l'hypothèse est parfois émise que le nombre d'or a son origine chez
les pythagoriciens12,13 : ils auraient connu et construit empiriquement le dodécaèdre régulier.
Les pythagoriciens connaissaient déjà une construction du pentagone à l'aide de
triangles isocèles. À cette époque, l'étude du nombre d'or est essentiellement géométrique,
Hypsiclès, un mathématicien grec du
iie siècle av. J.-C., en fait usage pour la mesure de
polyèdres réguliers7. Elle revient chaque fois qu'un pentagone est présent.
Le premier texte mathématique indiscutable est celui des
Éléments d'
Euclide (vers 300 av. J.-C.). Dans la
3e définition du
Livre vi, le nombre d'or est défini comme une proportion géométrique :
« Une droite est dite coupée en extrême et moyenne raison quand, comme elle est tout entière relativement au plus grand segment, ainsi est le plus grand relativement au plus petit. »
Sa relation avec le pentagone, l'
icosaèdre et le
dodécaèdre régulier est mise en évidence. Il est donc lié aux problèmes géométriques déjà résolus par les pythagoriciens
20, mais selon l'historien des sciences
Thomas Heath (s'appuyant sur
Proclus),
c'est probablement Platon qui en avait fait ensuite un sujet d'étude spécifique[Contradiction !] :
« L'idée que Platon initia l'étude
(du nombre d'or) comme sujet intrinsèque n'est pas du tout contradictoire avec la supposition que le problème d'
Eucl. ii. 11 a été résolu par les pythagoriciens
13. »
Les
mathématiques arabes apportent un nouveau regard sur ce nombre, plus tard qualifié d'or. Ce n'est pas tant ses propriétés géométriques qui représentent pour eux son intérêt, mais le fait qu'il soit solution d'
équations du second degré.
Al-Khawarizmi, un mathématicien perse du
viiie siècle, propose plusieurs problèmes consistant à diviser une longueur de dix unités en deux parties. L'un d'eux possède comme solution la taille initiale divisée par le nombre d'or.
Abu Kamil propose d'autres questions de même nature dont deux sont associées au nombre d'or. En revanche, ni pour Al-Khawarizmi ni pour Abu Kamil, la relation avec la proportion d'extrême et moyenne raison n'est mise en évidence. Il devient ainsi difficile de savoir si la relation avec le nombre d'or était claire pour eux
21.
Leonardo Pisano, plus connu sous le nom de Fibonacci, introduit en Europe les équations d'Abu Kamil. Dans son livre
Liber Abaci, on trouve non seulement la longueur des deux segments d'une ligne de 10 unités mais aussi, clairement indiquée la relation entre ces nombres et la proportion d'Euclide
22. Son livre introduit la
suite qui porte maintenant son nom, connue
« aux Indes » depuis
23 le
vie siècle. En revanche la relation avec le nombre d'or n'est pas perçue par l'auteur. Un élément de cette suite est la somme des deux précédents.
Trois siècles plus tard,
Luca Pacioli rédige un livre dénommé
La divine proportion24, illustré par
Léonard de Vinci. Si l'aspect mathématique n'est pas nouveau, le traitement de la question du nombre d'or est inédit. L'intérêt du nombre ne réside pas tant dans ses propriétés mathématiques que mystiques, elles
« concordent avec les attributs qui appartiennent à Dieu24… ». Pacioli cite les dix raisons qui l'ont convaincu. L'incommensurabilité prend, sous la plume de l'auteur, la forme suivante
« De même que Dieu ne peut se définir en termes propres et que les paroles ne peuvent nous le faire comprendre, ainsi notre proportion ne se peut jamais déterminer par un nombre que l'on puisse connaître, ni exprimer par quelque quantité rationnelle, mais est toujours mystérieuse et secrète, et qualifiée par les mathématiciens d'irrationnelle24 ».
Pacioli rédige ainsi l'envoi de son livre :
« une œuvre nécessaire à tous les esprits perspicaces et curieux, où chacun de ceux qui aiment à étudier la philosophie, la perspective, la peinture, la sculpture, l'architecture, la musique et les autres disciplines mathématiques, trouvera une très délicate, subtile et admirable doctrine et se délectera de diverses questions touchant à une très secrète science24. », il est en revanche discret sur la manière dont s'applique cette proportion. Dans son traité d'architecture
25, l'auteur se limite aux proportions
26 de
Vitruve, un architecte de la
Rome antique. Elles correspondent à des fractions d'entiers, choisies à l'image du corps humain
27. S'il cite comme exemple une statue du grec
Phidias, ce n'est que pour y voir le nombre d'or dans un
dodécaèdre régulier, une figure associée au pentagone symbole de la quintessence, une représentation du divin
28. Les architectes de la Renaissance n'utilisent pas le nombre d'or
29,30.
Les mathématiciens de l'époque ne sont pas en reste. Les spécialistes des
équations polynomiales que sont
Gerolamo Cardano et
Raphaël Bombelliindiquent comment calculer le nombre d'or à l'aide d'équations de second degré
31. Un résultat plus surprenant est anonyme. Une note manuscrite, datant du début du
xvie siècle et écrite dans la traduction de Pacioli des éléments d'Euclide de 1509, montre la connaissance de la relation entre la suite de Fibonacci et le nombre d'or. Si l'on divise un terme de la suite par son précédent, on trouve une approximation du nombre d'or. Plus le terme est élevé, plus l'approximation est bonne et elle peut devenir aussi précise que souhaitée
32. Ce résultat est, plus tard, retrouvé par
Johannes Kepler puis par
Albert Girard33. Kepler est fasciné par le nombre d'or, il dit de lui
« La géométrie contient deux grands trésors : l’un est le théorème de Pythagore ; l’autre est la division d’une ligne en moyenne et extrême raison. Le premier peut être comparé à une règle d’or ; le second à un joyau précieux34 »
xixe siècle : naissance d'un mythe[modifier]
Adolf Zeising appuie sa théorie sur des exemples naturels incontestables. Un Tournesol présente une figure où apparaît la
suite de Fibonacci, ainsi que la spirale d'or.
Sur le front des mathématiques, l'intérêt diminue. Au
xviiie siècle, le nombre d'or ainsi que les
polyèdres réguliers sont considérés
« avec assez de justice, comme une branche inutile de la géométrie35 ». Concernant le nombre d'or, on lui prête encore un peu d'attention au siècle suivant : Jacques Binet retrouve en 1843 un résultat oublié, démontré initialement par
Leonhard Euler en 1765
36. Si la lettre φ désigne le
nombre d'or, le
n-ième terme de la suite de Fibonacci est donné par la formule
(φn – (1 − φ)n)⁄√5. Ce résultat est maintenant connu sous le nom de
Formule de Binet. L'essentiel des travaux se reporte sur la suite de Fibonacci.
Édouard Lucas trouve des propriétés subtiles associées à cette suite, auquel il donne pour la première fois le nom de Fibonacci
37. Son résultat le plus important porte le nom de
Loi d'apparition des nombres premiers au sein de la suite Fibonacci38,39.
D'autres sont plus polémiques. Pour retrouver le nombre d'or dans le
Parthénon, il est nécessaire d'user de conventions spécifiques.
C'est durant ce siècle que les termes de « section dorée », puis « nombre d'or » apparaissent. On les trouve dans une réédition d'un livre de mathématiques élémentaires écrit par Martin Ohm. L'expression est citée dans une note de bas de page :
« Certains ont l'habitude d'appeler la division en deux telles parties unesection d'or31. » Cette réédition fait surface dans une période située entre 1826 et 1835, en revanche son origine est un mystère.
L'intérêt resurgit au milieu du siècle, avec les travaux du philosophe allemand
Adolf Zeising. Avec lui, le nombre d'or devient un véritable système, une clé pour la compréhension de nombreux domaines, tant artistiques — comme l'architecture, la peinture, la musique —, que scientifiques — avec la biologie et l'anatomie
40. Une dizaine d'années plus tard, il publie un article
41 sur le
pentagramme,
« manifestation la plus évidente et la plus exemplaire de cette proportion ». Une relecture de la métaphysique pythagoricienne lui permet de conclure à l'existence d'une loi universelle fondée sur le pentagramme, et donc, sur le nombre d'or. Malgré une approche scientifique douteuse
42,43, la théorie de Zeising obtient un franc succès.
En France, pouvoir codifier de manière scientifique la beauté est une idée qui séduit. Les dimensions du
Louvre, de l'
Arc de triomphe sont mesurées avec attention. Des délégations sont chargées de mesurer précisément la taille des
pyramides d'Égypte ainsi que du
Parthénon. Les cathédrales ne sont pas en reste. La France trouve son champion en
Charles Henry (en), un érudit qui s'inscrit dans l'esprit positiviste de son temps. Dans un texte fondateur
44, à l'origine du mouvement
pointilliste, il associe au nombre d'or, une théorie de la couleur et des lignes. Son influence auprès de peintres comme
Seurat ou
Pissarro n'est pas négligeable, mais son attachement au nombre d'or n'est pas aussi profond que chez son collègue allemand : en
1895, il finit par abandonner définitivement l'idée de quantifier le beau
45.
xxe siècle : le paroxysme[modifier]
Toute spirale n'est pas d'or. Celle du
nautile n'a rien à voir avec la divine proportion
46.
Loin de s'éteindre avec le déclin du positivisme, la popularité du nombre d'or ne fait que croître durant la première partie du siècle. Le prince roumain
Matila Ghyka en devient l'incontestable chantre. Il reprend les thèses du siècle précédent et les généralise. Tout comme Zeising, il s'appuie tout d'abord sur les exemples issus de la nature, comme les coquillages ou les plantes. Il applique cette universalité à l'architecture avec des règles plus souples que son prédécesseur. Cette théorie avait déjà influé sur les notations, le nombre d'or étant noté φ en référence au sculpteur Phidias, concepteur du Parthénon
47.
La dimension mystique n'est pas absente chez Ghyka
48 et trouve ses origines dans la
philosophie pythagoricienne. L'absence de trace écrite sur le nombre d'or chez les pythagoriciens s'expliquerait par le culte du secret. Cette idée est largement reprise et généralisée
49 par les mouvements de pensées ésotériques au
xxe siècle. Le nombre d'or serait une trace d'un savoir perdu, nommé Tradition Primordiale ou Connaissance Occulte chez les
Rose-Croix ou des mouvements connexes. On le retrouve chez les passionnés de l'
Atlantide, qui voient dans la
pyramide de Khéops ou le temple d'Andros la preuve d'un savoir mathématique oublié
50. Ce mouvement de pensée reprend des idées développées en Allemagne au
xixe siècle par Franz Liharzik (1813 - 1866), pour qui la présence du nombre d'or, de
π et de
carrés magiques est la preuve « incontestable »
51 d'un groupe restreint d'initiés possédant la science mathématique absolue
52.
En
1929, une époque troublée par des idées d'un autre âge, Ghyka n'hésite pas à tirer comme conclusion de son étude sur le nombre d'or, la suprématie de ce qu'il considère comme sa race :
« le point de vue géométrique a caractérisé le développement mental (…) de toute la civilisation occidentale (…) ce sont la géométrie grecque et le sens géométrique (…) qui donnèrent à la race blanche sa suprématie technique et politique53. » Si le prince n'insiste que très médiocrement sur cet aspect du nombre d'or, d'autres n'ont pas ses scrupules. Ils usent de l'adéquation de la morphologie d'une population avec les différentes
proportions divines pour en déduire une supériorité qualifiée de
raciale. Ce critère permet de fustiger certaines populations, sans d'ailleurs la moindre analyse
54. Le nombre d'or est, encore maintenant, sujet à de prétendues preuves de supériorité culturelle, sociale ou ethnique
55.
Sans cautionner ces idées extrêmes, certains intellectuels ou artistes éprouvent une authentique fascination pour le nombre d'or ou son mythe. Le
compositeur Iannis Xenakis utilise ses propriétés mathématiques pour certaines compositions
56. L'
architecte Le Corbusier reprend l'idée consistant à établir les dimensions d'un bâtiment en fonction de la morphologie humaine et utilise pour cela le nombre d'or.
Paul Valéry un poète et intellectuel écrit à ce sujet des vers dans son
Cantique des colonnes :
« Filles des nombres d'or
Fortes des lois du ciel
Sur nous tombe et s'endort
Un dieu couleur de miel. »
Le peintre
Salvador Dalí fait référence au nombre d'or et sa mythologie dans sa peinture, par exemple dans un tableau dénommé
Le Sacrement de la dernière Cène.
Sur le plan mathématique, le nombre d'or suit une trajectoire inverse, son aura ne fait que diminuer et il quitte le domaine de la recherche pure. Il existe néanmoins une exception, la
revueFibonacci Quarterly57 sur la suite de Fibonacci,
dont l'objet est plus ludique qu'associé à la recherche[réf. nécessaire]. En revanche, le nombre d'or apparaît comme la clé de quelques sujets scientifiques. La question de
phyllotaxie, se rapportant à la
spirale que l'on trouve dans certains végétaux comme les écailles de la pomme de pin est-elle vraiment liée à la proportion d'Euclide ? Cette question fait couler beaucoup d'encre dès le siècle précédent.
Wilhelm Hofmeister suppose que cette spirale est la conséquence d'une
règle simple
58. Pour le botaniste allemand
Julius von Sachs, ce n'est qu'un orgueilleux jeu mathématique, purement subjectif
59. En 1952, un scientifique, père fondateur de l'
informatique,
Alan Turing propose un mécanisme qui donnerait raison à Hofmeister
60. Deux physiciens français, Stéphane Douady et Yves Couder, finissent par trouver l'expérience confirmant Hofmeister et Turing
61. La présence du nombre d'or dans le monde végétal ne semble ni fortuite ni subjective
62.
L'absence de nombre d'or dans la
spirale logarithmique décrivant la forme d'une
galaxie rend l'astronome sceptique sur l'usage de cette proportion dans ce contexte.
La thèse de l'omniprésence du nombre d'or est souvent reprise
63. Si un avis définitif sur ce phénomène est difficile à propos de l'œuvre des hommes, il est plus aisé de comprendre la différence d'opinion que soulève cette question pour les sciences de la nature. Elle provient de l'usage des critères utilisés pour lier ou non le nombre d'or avec un phénomène.
Dans le monde végétal, les écailles des pommes de pins engendrent des spirales particulières, dites
logarithmiques. Ces spirales se construisent à l'aide d'un
nombre réel non nul quelconque. Si ce nombre est égal au nombre d'or, les proportions correspondent à la moyenne et extrême proportion d'Euclide et la suite de Fibonacci apparaît. Ce phénomène se produit sur les
étamines d'une fleur de tournesol. La présence du nombre d'or n'est pas controversée dans ce cas
64.
Une organisation autour d'un schéma pentagonal des atomes d'un cristal de quartz explique l'usage du nombre d'or pour l'étude d'un tel minéral.
En revanche, si ce nombre n'est pas égal au nombre d'or, alors ni proportion d'or, ni suite de Fibonacci ne sont pertinents dans l'étude de la spirale logarithmique correspondante, comme celles que forment la
coquille du mollusque le
nautilus63, les yeux sur les plumes d'un paon
65 ou encore certaines
galaxies.
En
minéralogie, il existe des
cristaux dont les atomes s'organisent selon un schéma pentagonal. Les proportions entre les côtés et les diagonales du pentagone font intervenir le nombre d'or. Il est aussi présent dans des structures dites
quasi cristallines. Les atomes dessinent des triangles d'or qui remplissent l'espace sans pour autant présenter de périodicité, on obtient un
pavage de Penrose. Pour la même raison que précédemment, le nombre d'or est présent et l'on retrouve la suite de Fibonacci
[réf. à confirmer]66. Le pentagone n'est pas présent dans tous les cristaux. La structure
cubique à faces centrées d'un
diamant ne fait pas intervenir le nombre d'or.
Ainsi, selon l'axe d'analyse, la réponse sur l'omniprésence du nombre d'or est différente. Pour un scientifique, spécialiste dans un domaine, l'usage du nombre d'or est finalement plutôt rare, limité à quelques sujets comme la
phyllotaxie du tournesol ou la
cristallographie du
quartz. S'il recherche des concepts explicatifs pour mieux comprendre son domaine, la proportion d'Euclide est rarement de ceux-là. D'autres
63 utilisent l'analogie ainsi que l'esthétique comme critère. La divine proportion est pour eux présente dans les cieux, la vie animale et végétale, les minéraux et finalement dans toute la nature.
Une
pomme de pin illustre par ses écailles un phénomène de
phyllotaxie. On trouve des spirales dont la proportion est proche de celle d'Euclide. Le nombre d'écailles dans une spirale ainsi que le nombre de spirales correspond à deux nombres consécutifs dans la suite de Fibonacci.
Le mécanisme ne fait pas toujours apparaître le nombre d'or. Pour l'
Achimenes erecta, on remarque ici trois jeux de trois feuilles. Chaque jeu est pivoté d'un sixième de tour par rapport à la génération précédente. On obtient encore deux jeux de spirales, mais qui n'ont plus rien à voir avec le nombre d'or.
En
biologie, l'ordonnancement des écailles d'une pomme de pin ou de l'écorce d'un ananas induit des
spirales ordonnées par des nombres entiers, souvent associés au nombre d'or. Sur la figure de gauche, on observe 8 spirales, chacune formée de 13 écailles dans un sens et 13 spirales formées de 8 écailles dans l'autre sens. Les proportions de ces spirales ne sont pas très éloignées de celles d'une spirale d'or. Les nombres 8 et 13 sont deux nombres consécutifs de la suite de Fibonacci et leur rapport est proche du nombre d'or. Un phénomène analogue se produit avec les
étamines des tournesols, cette fois avec les couples d'entiers (21,34), (34,55) et (55, 89). Chacun de ces couples correspond à deux entiers consécutifs de la suite de Fibonacci.
La phyllotaxie ne suit pas toujours les lois du nombre d'or. À droite, on voit un mécanisme analogue sur des feuilles, les deux spirales sont toujours logarithmiques mais ne suivent plus la proportion d'or. Les nombres de spirales dans un sens et dans l'autre sont égaux.
Ce mécanisme est régi par la
règle de Hofmeister :
« Le primordium apparaît périodiquement dans le plus grand espace disponible. » Un
primordium correspond à un embryon de partie de plante : écaille, feuille, d'étamine, etc. Ce mécanisme est contrôlé par la production d'une substance inhibitrice, appelée morphogène, émise par les primordia. Ainsi une nouvelle pousse ne peut naître que le plus loin possible des précédentes.
Dans le cas de l'Achimenes erecta, la tige pousse rapidement par rapport à la feuille, la deuxième feuille naît dans la direction opposée, le rapport entre la croissance de la tige et le temps d'apparition d'un nouveau primordium fait que la troisième position la meilleure est à un angle d'un tiers de tour par rapport à la première feuille et deux tiers par rapport à la deuxième. Finalement on obtient l'apparition de trois feuilles, décalées d'un tiers de tour l'une par rapport à l'autre, puis d'un nouveau jeu de trois feuilles, décalé d'un sixième de tour par rapport au jeu précédent.
La pomme de pin suit la même règle pour le primordium de l'écaille. La croissance de la tige entre deux primordia est beaucoup plus modérée. Le troisième primordium naît en conséquence entre les deux premiers, avec un angle légèrement plus faible du côté du premier primordium, la tige ayant un peu grandi. Douady et Couder ont montré qu'un tel mécanisme produit deux jeux de spirales d'or de directions opposées dont les nombres de spirales par jeu correspondent à deux éléments consécutifs de la suite de Fibonacci. Plus la croissance entre l'apparition de deux primordia est petite, plus élevés sont les deux éléments consécutifs de la suite
64.
Le squelette de Zeising ne respecte pas précisément les proportions du corps humain, le crâne est par exemple irréaliste.
Le corps humain est un enjeu souvent corrélé à celui du nombre d'or. Il comporte différentes facettes. Tout d'abord scientifique, la question maintes fois posée est de savoir si le corps, à l'image de la fleur de tournesol, possède une relation plus ou moins directe avec le nombre d'or. En terme artistique, la « divine proportion » est-elle utilisable pour représenter le corps ? Il existe enfin un enjeu esthétique. Si le nombre d'or, comme le pense
56 le compositeur Xenakis, est relié à notre corps, son usage peut être une technique pour obtenir de l'harmonie.
La première corrélation recherchée est dans les dimensions du corps humain. Elle débouche sur la tentative d'un système de mesure construit à l'aide du seul nombre d'or. Zeising fonde toute une anatomie
68 sur cette arithmétique. Après un vif effet de mode, cette approche est finalement abandonnée. Ses proportions sont à la fois trop imprécises et ne correspondent que trop mal à l'anatomie du corps humain. Les proportions du crâne, par exemple, ne sont pas réalistes
69. D'autres raisons, plus profondes encore, sont la cause de l'abandon d'une démarche de cette nature. L'
anatomie médicalen'est pas à la recherche d'une proportion particulière, mais des limites qui, si elles sont dépassées deviennent pathologiques. Elle utilise des fractions simples ainsi que des plages de longueur, mais jamais le nombre d'or. Là où certains voient une
divine proportion, comme dans le rapport de la longueur de l'avant-bras sur celui de la main, l'anatomiste scientifique calcule le rapport entre la longueur de la main et celle de l'avant bras, il voit 2/3. La différence entre les deux approches, inférieure à 8 %, ne lui paraît pas justifier une telle complexité, au vu des variations observées entre les individus.
Stephen Jay Gould, un
paléontologue, a montré à quel point les mesures anthropométriques visant à étayer les doctrines de cette époque étaient biaisées par leurs auteurs
70.
Une autre raison
71 est que les dimensions d'un être humain sont en constante évolution. En un siècle, la
stature du Français moyen a augmenté de 9 centimètres, et cette croissance n'est pas uniforme. Le jeu des proportions d'un corps humain est essentiellement dynamique, cet aspect rend difficile d'imaginer une proportion unique, clé universelle de l'anatomie humaine. Une approche de cette nature, trop normative et intemporelle, n'a pas beaucoup de sens scientifique en anatomie. Si cet axe de recherche n'est plus d'actualité, cela ne signifie pas l'abandon de la quête du nombre d'or dans le corps humain. Le cerveau est maintenant source d'attention
72. Cette théorie reste minoritaire et controversée.
Les contraintes artistiques sont de natures différentes. Les artistes, attentifs au travail des médecins, ont imaginé des
modules ou systèmes de proportions, propres au corps humain. Le désir de le représenter impose une démarche de cette nature. Un très ancien module est celui des Égyptiens
73, la classique proportion qu'est le rapport de la taille complète à la hauteur du nombril est estimée à 19/11, relativement loin du nombre d'or. Les modules sont, en général, purement fractionnaires. Tel est le cas de celui inventé par les Égyptiens, par
Polyclète, qui nous est rapporté par Vitruve, de celui de Cousin, de Vinci ou de
Dürer. Il est néanmoins difficile d'en déduire que Dürer croyait en un canon universel. Il initie une conception fondée sur la pluralité des types de beauté
74, ayant chacune ses proportions propres.
Œuvre de l'homme[modifier]
L'idée que le nombre d'or possède une qualité visuelle intrinsèque est largement citée
75. Un argument est la présence de la divine proportion dans de nombreux chefs d'œuvre. Cependant les commentaires précis sont rares, ce qui amène à rechercher le rapport d'Euclide, sans information directe de la part de l'auteur. L'existence d'une forme géométrique ayant des concordances avec le tableau est, pour certains, un élément de preuve. Pour d'autres
76, une démarche de cette nature est peu convaincante.
Les dimensions de
La Naissance de Vénus de
Sandro Botticelli respectent assez précisément la
divine proportion. Il est pourtant très peu probable que cela indique une quelconque volonté de l'auteur.
Un exemple est celui de
La Naissance de Vénus de
Sandro Botticelli77. Ses dimensions, 172,5 ×
278,5 cm, respectent précisément la proportion. Le carré, associé au rectangle d'or, correspond à un rythme du tableau ; enfin, la diagonale du rectangle restant, ainsi que celle symétrique, sont des lignes de force. Ce raisonnement n'a pas convaincu certains spécialistes. Le tableau semble faire partie d'un
diptyque avec
Le Printemps, un autre tableau du maître. L'aile d'Aura, un des dieux, est étrangement coupée. Pour en avoir le cœur net, une analyse finit par être faite. Le verdict est sans appel : Botticelli avait choisi une taille analogue à celle du
Printemps78 ; le haut de
La Naissance est amputé de
32,5 cm et avait, à sa conception, la taille du
Printemps. Dans ce cas, la
divine proportion n'a pas été choisie par le créateur.
De nombreuses indications laissent penser que ce n'est pas du côté de la divine proportion qu'il faut chercher à comprendre les
rythmes du
Saint Jérôme de
Léonard de Vinci.
Pour certains, il existe un fondement scientifique à la beauté :
« … la nature, ministre de la divinité, lorsqu'elle façonna l'homme, en disposa la tête avec toutes les proportions voulues24… ». Cette idée n'est pas une invention de Pacioli, le traité de peinture
79 de
Leon Battista Alberti, établissant les premières règles de la
perspective, était déjà l'illustration d'une philosophie analogue. La découverte de lois
scientifiques, modifie la peinture et permet d'incarner un nouvel idéal. Si l'approche mathématique d'Alberti obtient un large consensus, peu d'éléments laissent penser à un succès analogue pour la loi de la divine proportion.
Un exemple est le cas Vinci.
Pacioli est un de ses amis proches, Vinci connaît suffisamment ses théories pour illustrer son livre. À travers
ses codex, son
Traité de la peinture et les multiples analyses de ses sources
80, la pensée de Vinci sur la proportion en peinture nous est connue. Si, pour le maître, la peinture s'apparente à une science
81, ses thèses sont forts éloignées de celle de son ami. Sa première source est l'observation et l'expérience, et non les mathématiques :
« … l'expérience ayant été la maîtresse de ceux qui écrivent bien, je la choisis pour maîtresse et, en tout cas ferai appel à elle82 ». Cette attitude se traduit, par exemple pour le choix des proportions humaines. À travers de multiples dissections, il mesure systématiquement les rapports entre les dimensions des différents os et muscles. Ses planches médicales l'amènent à une conception de l'anatomie dont les rapports sont de même nature que celle de la médecine moderne : ils sont fort nombreux et s'expriment à l'aide de fractions composées de petits facteurs entiers
83. La science de Vinci s'applique aussi sur des sujets déjà traités comme la perspective. Une fois encore, sa logique est plus proche de l'observation que de la rigidité mathématique. Les lois qu'il ajoute à celles d'Alberti traitent de la couleur : une chose éloignée voit sa couleur tirer vers le bleu, ainsi que de la netteté
« comment les choses qui s'éloignent doivent être moins nettes proportionnellement à leur distance84 ». Les règles régissant la proportion chez Vinci sont subtiles et en opposition avec des
articulations albertiennes, trop claires à ses yeux85, comme l'application directe d'une proportion sans lien avec ses observations.
À l'instar du Saint Jérôme à droite, beaucoup d'exemples de
rectangle d'or trouvés chez un peintre
86 supposent une approche de la proportion sans justification de la part du peintre ou, comme ici, contraire aux règles établies par son auteur. Ni
Arasse dans son volumineux ouvrage sur Vinci, ni Marani dans le sien
87 ne font référence à une explication de cette nature.
Le nombre d'or a aussi influencé les peintres du
groupe de Puteaux, appelé aussi « Section d'or », groupe qui se crée autour de
Jacques Villon en 1911. Leur emploi du nombre d'or en peinture est cependant davantage intuitif que purement mathématique.
Le
théâtre d'Épidaure contient deux séries de gradins, l'une de 21, l'autre de 34, deux nombres consécutifs de la suite de Fibonacci dont le rapport est proche du nombre d'or.
L'usage du nombre d’or dans les constructions anciennes est un sujet de controverse. Pour le prince Ghyka, l’archéologie offre la preuve de l'universalité du canon de beauté qu'est le nombre d'or. L'argument principal est le vaste nombre d'exemples. Le prince reprend les travaux de son prédécesseur Zeising et l'enrichit considérablement. Le
théâtre d'Épidaure possède deux séries de gradins l'une de 21 et l'autre de 34 marches, deux éléments consécutifs de la suite de Fibonacci.
Si l'on en croit les canons de la beauté de
Polyclète, le sculpteur à qui l'on attribue l’
éphèbe Westmacott, les proportions du corps humain sont des fractions d'entiers et non le nombre d'or.
Les plus convaincus citent le temple d'
Andros et celui de
Salomon comme exemple d'utilisation du nombre d'or. Pour le temple d'Andros, sa forme actuelle est un losange dont deux côtés ont un rapport approximativement égal à 5/3, une valeur proche du nombre d'or. L'origine de ces vestiges, qui daterait de 10 000 ans, n'est pas avérée. Ce site, non reconnu par les archéologues officiels
50 est pour ses partisans une preuve de l'existence de l'
Atlantide9. Le temple de Salomon aurait une dimension d'un rapport 2/1, certains
88 remarquent que ce sont deux termes consécutifs de la suite de Fibonacci, un élément suffisant à leurs yeux pour voir la trace du nombre d'or.
La
pyramide de Khéops convainc un public plus vaste. Cet exemple est cité depuis le milieu du
xixe siècle, une époque où la méconnaissance presque totale de l'
égyptologie donne naissance à d'innombrables mythes
42. La coïncidence entre les dimensions de la pyramide et le nombre d'or est ici excellente. Le rapport entre la longueur de la plus grande pente d'une des faces et la demi-longueur d'un côté correspond au nombre d'or avec une précision de moins de 1 %. Le scepticisme des professionnels est la conséquence de la connaissance actuelle de la civilisation égyptienne
89. En effet, les systèmes de longueur utilisés dans les documents connus pour mesurer les pentes et les longueurs horizontales ne coïncident pas, interpréter leur rapport n’a donc pas beaucoup de sens
90. On ne trouve pas non plus la moindre trace religieuse ou esthétique qui justifie un choix de cette nature
91. Cette faiblesse pousse Taylor, à l'origine de cette hypothèse, à créer de toutes pièces une citation de Hérodote
42,92.
Le cas grec est encore plus populaire et très largement étayé. Mais l'écart entre la culture grecque et le nombre d'or laisse perplexe les spécialistes
93. Ces proportions
incommensurables, que sont la diagonale d'un carré ou celle d'Euclide, sont vécues comme un scandale
94, une trahison
95 des dieux à l'époque de Pythagore. Un grec n'imagine pas qu'un nombre puisse être autre chose qu'une fraction d'entiers. L'existence de proportions, comme celle d'Euclide, qui ne sont pas des nombres est une source de chaos intellectuel, à l'opposé des valeurs philosophiques et mystiques des pythagoriciens
96. On raconte que
Hippase de Métaponte aurait été exclu de la confrérie des pythagoriciens pour avoir dévoilé le scandale de l'incommensurabilité d'une diagonale d'un
dodécaèdre régulier, une autre indique qu'il aurait péri noyé
97, conséquence de son impiété. Qu'une proportion aussi négative soit utilisée pour les monuments apparaît étonnant. Les textes d'architecture grecs confirment l'usage des nombres rationnels pour définir les proportions des bâtiments. Les
proportions harmonieuses sont longuement relatées par
Vitruve un architecte, auteur du célèbre traité
De architectura en dix volumes. Pour ce faire, il utilise largement, au volume
ix, les mathématiques de Platon, Pythagore ou d'autres mathématiciens. Les proportions proviennent du module de
Polyclète, un sculpteur grec contemporain de
Phidias. Le traité de Vitruve ne contient aucune trace de proportion irrationnelle à l'exception de la diagonale du carré
27.
Enfin, les exemples choisis par le prince sont controversés. Retrouver la
divine proportion dans la façade du Parthénon demande des conventions spécifiques, comme d'inclure trois des quatre marches du fronton
98 ou de tronquer le toit
99. L'usage de mesures non spécifiques donne une proportion différente
100. Pour faire apparaître le nombre d'or dans les proportions des monuments grecs, Ghyka
101 n'hésite pas à utiliser des fractions comme 1/φ
4, bien difficile à différencier de 1/4, ou d'une racine quatrième de φ. Les techniques hellénistiques sont pourtant
incapables[réf. souhaitée] de réaliser
un tel calcul[Lequel ?].
Le Corbusier est l'architecte qui théorise l'usage du nombre d'or dans son métier. S'il reprend l'idée de Vitruve, consistant à proportionner un bâtiment aux dimensions d'un corps humain, il y associe d'autres éléments justifiant l'usage de la proportion d'Euclide.
Le nombre d'or permet de créer un curieux
système de numération. Les mathématiques nous apprennent qu'il est possible de construire une
numération positionnelle, non seulement avec dix, comme celle des humains, ou avec deux, pour les ordinateurs, mais avec n'importe quel nombre réel strictement positif et différent de
un. Celui construit avec le nombre d'or, appelé
base d'or, lui semble le plus adapté à l'architecture. Au premier contact, il est un peu étrange. Par exemple dans ce système 100 est égal à 10 + 1, ce qu'un mathématicien lit φ
2 = φ + 1.
Cette
échelle harmonique, pour reprendre son expression
102, permet de réconcilier les atouts du système métrique décimal, pratique et abstrait, avec ceux du système anglais des pouces et des pieds, naturel mais peu pratique. En calant les différentes
dizaines, c'est-à-dire ici les puissances du nombre d'or, sur les dimensions humaines, Le Corbusier cherche à obtenir un système alliant les deux avantages. La deuxième unité correspond à la taille d'un avant-bras, la troisième à la distance entre le nombril et le sommet de la tête, la quatrième à celle entre le sol et le nombril d'un homme debout et la cinquième à la taille d'un adulte.
En termes d'architecture, cette démarche offre un moyen naturel pour incarner l'idéal de Vitruve. Chaque dizaine correspond à une proportion humaine et les différentes proportions se répondent entre elles. En termes d'
urbanisme, Le Corbusier cherche à trouver un moyen de normalisation. En
1950, date de parution du premier tome sur le
Modulor, nom qu'il donne à ce système, les besoins de reconstruction sont vastes et la rationalisation de la production, un impératif. L'auteur parle de
machine à habiter. Cette démarche, vise aussi un objectif esthétique. La normalisation dispose d'un avantage, elle permet
plus d'harmonie. Le tracé régulateur, c'est-à-dire l'échelle construite sur la suite de Fibonacci y joue un rôle :
« Le tracé régulateur n'apporte pas d'idée poétique ou lyrique ; il n'inspire nullement le thème ; il n'est pas créateur ; il est équilibreur. Problème de pure plasticité103 »
es
hypercubes, ou
n-cubes, forment une famille de
graphes. Dans un hypercube
, chaque sommet porte une
étiquette de longueur
sur un alphabet
, et deux sommets sont
adjacents si leurs étiquettes ne diffèrent que d'un symbole. C'est le graphe squelette de l'
hypercube, un polytope
n-dimensionnel, généralisant la notion de
carré (
n = 2) et de
cube (
n = 3). Dans les années 1980, des ordinateurs furent réalisés avec plusieurs processeurs connectés selon un hypercube : chaque processeur traite une partie des données et ainsi les données sont traitées par plusieurs processeurs à la fois, ce qui constitue un
calcul parallèle. L'hypercube est couramment introduit pour illustrer des algorithmes parallèles, et de nombreuses variantes ont été proposées, soit pour des cas pratiques liés à la construction de machines parallèles, soit comme objets théoriques.
L'hypercube
consiste en deux sommets d'étiquettes
et
; les étiquettes de ces sommets étant différentes par un seul symbole, ils sont donc reliés. Pour passer à la dimension supérieure, on fabrique une copie du graphe : à la partie d'origine, on rajoute le symbole
, et sur la partie copiée le symbole
; chaque sommet de la partie d'origine est ensuite relié à son équivalent dans la copie. Ainsi,
consiste en quatre sommets étiquetés
,
,
et
. L'illustration ci-dessous montre en rouge les arêtes connectant les sommets d'origine à leurs équivalents dans la copie, et l'exemple se poursuit jusqu'à
et
. Cette méthode de construction est récursive, puisque pour construire
on se fonde sur
.
Enfin, on peut construire le graphe directement en appliquant sa définition. On dispose
sommets, et chacun a une étiquette unique dans l'
espace vectorielD 1 
, c'est-à-dire une étiquette de la forme
. Deux sommets sont reliés par une arête s'ils diffèrent exactement sur un symbole de leurs étiquettes, soit formellement pour le graphe
:
Un cycle dans un hypercube
constitué de deux hypercubes
. En rouge, un chemin dans le premier hypercube
, en bleu les arêtes le reliant à sa copie et en vert le chemin dans la copie. Le cycle est de longueur 2 + 2 + 2 = 6, qui est pair.
- Degré. Deux sommets sont connectés s'ils diffèrent exactement sur un symbole de leurs étiquettes. Comme l'étiquette a symboles, chaque sommet est connecté à exactement voisins : tout sommet a donc degré , autrement dit le graphe est -régulier.
- Nombre de sommets. Par la construction récursive, on voit que pour passer de à , il faut faire une copie du graphe, autrement dit le nombre de sommets est doublé. Si
est le nombre de sommets du graphe , on obtient ainsi 
, et le premier cas est 
; en déroulant la récurrence, on obtient 
, c'est-à-dire que le graphe a sommets.
- DiamètreA 1. Une des propriétés du produit cartésien est que le diamètre
de 
est égal à 
. Comme est leproduit cartésien de graphes complets 
, son diamètre est égal à 
.
Les sommets de l'hypercube
sont répartis en deux ensemble. Ceux en vert ont un nombre impair de 1 et ceux en rouge un nombre pair. Le voisin d'un sommet est nécessairement de couleur différente, donc le graphe est biparti.
- Cycles. Par construction, le plus petit cycle correspond à , qui est isomorphe au cycle
(i.e. le cycle de longueur 4). Le graphe est formé par deux graphes : si l'on souhaite un cycle de longueur supérieur à 4 dans , alors on choisit 
arêtes dans un des deux graphes , arêtes dans l'autre et 2 arêtes supplémentaires pour naviguer entre les deux graphes, ce qui porte le total d'arêtes à 
; ce mécanisme est illustré dans la figure ci-contre avec un cycle de longueur 6, et permet de prouver que les cycles dans un hypercube sont toujours de longueur paire.
- Nombre chromatique. Un graphe est biparti si et seulement s'il ne contient pas de cycle impair, et il découle donc de la propriété précédente que l'hypercube est biparti. Un graphe biparti est celui pouvant être colorié avec deux couleurs, et ainsi le nombre chromatique de l'hypercube est
. Pour voir qu'un graphe est biparti, il suffit de trouver un schéma afin de ranger chaque sommet dans un ensemble 
ou 
, de façon telle que tout sommet d'un ensemble ait comme voisins uniquement des sommets de l'autre ensemble. Dans le cas de l'hypercubeD 2, l'ensemble peut être constitué des sommets dont l'étiquette a un nombre pair de 1, et est l'ensemble de sommets dont l'étiquette a un nombre impair de 1. Un sommet étant connecté à tous ceux dont l'étiquette diffère exactement d'un symbole, il en découle que le nombre de 1 des voisins d'un sommet est soit supérieur soit inférieur : ainsi, un sommet pair sera connecté à des sommets impairs, et vice-versa.
- Planaire. L'hypercube est planaire (c'est-à-dire pouvant se dessiner sur un plan sans croiser deux arêtes) uniquement pour
. Pour 
, plusieurs arêtes vont se croiser mais déterminer le nombre minimum d'arêtes qui vont se croiser est un problème NP-completD 2 ; on sait par exemple qu'il y en a 8 pour .
- Eulérien. Un graphe a un chemin eulérien si et seulement si tout sommet est de degré pair. Comme est -régulier, il en résulte qu'il n'y a un chemin eulérien que pour pair.
- Hamiltonien. étant un cycle, il est aussi un circuit hamiltonien. Pour construire un circuit hamiltonien dans , on sait qu'il y a un circuit hamiltonien dans le graphe d'origine et dans sa copie : supprimons une arête dans chacun de ces circuits et raccordons les sommets ainsi libérés pour créer un circuit hamiltonien dans l'ensemble. Ce processus est illustré ci-dessous pour et . Le nombre exact de cycles hamiltoniens est donné ci-dessousD 2 pour les premiers hypercubes ; au-delà, l'estimation la plus précise quant au nombre
de circuits hamiltoniens dans est donnéeD 3 par :
.
Nombre de cycles hamiltoniens dans l'hypercubeD 2
| n | Sans compter les cycles isomorphes | En comptant tous les cycles |
|---|
| 2 | 1 | 1 |
|---|
| 3 | 1 | 6 |
|---|
| 4 | 9 | 1344 |
|---|
| 5 | 275 065 | 906 545 760 |
|---|
- Graphe de Hamming. Un graphe de Hamming
est le graphe obtenu par produit cartésien de 
graphes complets 
. L'hypercube 
étant obtenu par produit cartésien de copies de , il découle de la définition que tout hypercube est isomorphe à 
. Une définition alternative d'un graphe de Hamming montre le rapport direct avec celle utilisée pour introduire l'hypercube : est le graphe dont les sommets sont 
, l'ensemble des mots de longueur sur un alphabet 
, où 
. Deux sommets sont adjacents dans s'ils sont à une distance de Hamming de 1, c'est-à-dire si leurs étiquettes ne diffèrent que d'un symbole.
- Distance-régulier. Un hypercube est un graphe distance-régulierB 1 et son vecteur d'intersection est
.
- Diagramme de Hasse. L'hypercube est isomorphe au diagramme de Hasse d'une algèbre de Boole à n éléments.
- Reconnaissance. Étant donné une liste d'adjacence, on peut savoir en temps et espace linéaire si le graphe qu'elle représente est un hypercubeA 2.
- Code de GrayC 1. Les étiquettes ordonnées des sommets dans un cycle hamiltonien sur définissent le code de Gray sur bits. De plus, ce code suit une construction similaire à celle de l'hypercube : les mots de bits sont déterminés en copiant les mots de
puis en rajoutant 0 devant l'original, 1 devant la copie, et en inversant les mots de la copie.
- Distance-unité. L'hypercube est un graphe distance-unité : il peut s'obtenir à partir d'une collection de points du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1.
Aspects algébriques[modifier]
Groupe d'automorphisme[modifier]
Le groupe d'automorphisme
de l'hypercube
est d'ordre
. Il est isomorphe au produit en couronne des
groupes symétriques 
et
:
D 4. Le produit en couronne de
A et
B étant défini comme le
produit semi-direct 
où
est l'ensemble des fonctions de
A dans
B et où
A agit sur
par décalage d'indice :
pour 
et 
.
L'hypercube
est un graphe
arc-transitif : son groupe d'automorphisme
agit transitivement sur l'ensemble de ses arcs. Étant donné deux arêtes
e1 =
u1v1 et
e2 =
u2v2 de
G, il existe deux automorphismes
et
tels que
,
, et
,
,
,
.
L'hypercube
est donc
a fortiori symétrique. Le groupe
agit donc également transitivement sur l'ensemble de ses sommets et sur l'ensemble de ses arêtes. En d'autres termes, tous les sommets et toutes les arêtes d'un hypercube jouent exactement le même rôle d'un point de vue d'isomorphisme de graphe.
Graphe de Cayley[modifier]
Cela découle d'une propriété plus générale statuant que tous les graphes de Hamming sont des graphes de Cayley
A 4.
Matrice d'adjacence et spectre[modifier]
La
matrice d'adjacence 
de l'hypercube
est définie ci-dessous. Par la définition récursive de l'hypercube, pour passer à la dimension supérieure
, on duplique
et connecte les sommets d'origine à leur équivalent dans la copie.
On obtient ainsi la matrice d'adjacence
ci-dessous :
| 00 | 01 | 10 | 11 |
|---|
| 00 | 0 | 1 | 1 | 0 |
|---|
| 01 | 1 | 0 | 0 | 1 |
|---|
| 10 | 1 | 0 | 0 | 1 |
|---|
| 11 | 0 | 1 | 1 | 0 |
|---|
Au niveau de la matrice, l'opération passant de
à
se comprend comme suit : les entrées
correspondent à la matrice d'origine, et se trouvent dupliquées en
. Dans les autres entrées, on connecte chaque sommet à sa copie. Ainsi, la forme générale de la matrice est donnée de la façon suivante
D 6, où
représente la
matrice identité de dimension
:
Pour comprendre l'évolution du
spectre de la matrice en fonction de
, il faut revenir à la définition comme
produit cartésien. Le spectre d'un produit cartésien
est
, où
est le spectre de
et
le spectre de
; autrement dit, le spectre est la somme de toutes les paires possibles
A 5. Sachant que le spectre de
est
, on en déduit que le spectre de
est
: en effet, elles correspondent aux combinaisons
,
,
. Si l'on passe au stade suivant, soit
, on a d'un côté le spectre
de
, et de l'autre
de
: le résultat du produit cartésien est
.
On en déduit par récurrence la formule suivante pour le
polynôme caractéristique de la matrice d'adjacence (et donc du graphe):
. Ce polynôme caractéristique n'admet que des racines entières. Le graphe d'un hypercube est donc un graphe intégral, un graphe dont le spectreest constitué d'entiers.
Chemins et sous-graphes[modifier]
Pour aller d'un sommet à un autre, on utilise à nouveau le fait que deux sommets sont connectés s'ils diffèrent exactement sur un symbole de leurs étiquettes. Ainsi, un
chemin est trouvé en faisant correspondre une à une les coordonnées du sommet de destination avec celui d'origine. Par exemple, pour aller de
à
, on obtient
. Dans le cas général, pour aller de
à
on obtient :
Notons deux choses. Premièrement, la longueur d'un chemin entre deux sommets est le nombre de symboles sur lesquels leurs étiquettes diffèrent : ainsi, si les étiquettes sont complètement différentes, le chemin sera de longueur
, ce qui est une autre explication quant au diamètre du graphe. Deuxièmement, le chemin choisi n'est pas unique : au lieu d'aller de
en
, on aurait tout d'abord pu passer par
avant d'aller en
. Le nombre de chemins différents pour aller entre deux sommets est un problème de combinatoire : considérons que les sommets diffèrent sur
symboles, combien de façons a-t-on de générer des chemins ? On a
choix pour le premier symbole à changer, puis
choix pour le second symbole à changer, jusqu'à un seul choix quand il n'y a plus qu'un symbole à changer ; ainsi, le nombre de chemins entre deux sommets différant sur
symboles est
.
Hypercubes induits[modifier]
Les chemins entre deux sommets ont d'autres propriétés intéressantes, particulièrement pour les sous-graphes qu'ils définissent. Ainsi, l'union des chemins entre deux sommets distants de
(
i.e. différant de
symboles) donne
A 2 l'hypercube
. Ceci est illustré par l'exemple ci-dessous : dans le cas de deux sommets voisins
et
, il n'y a qu'un chemin et on obtient l'hypercube
; dans le cas où ils sont à distance 2, il y a deux chemins entre eux qui définissent
, et s'ils sont à distance 3 alors l'union des chemins représente l'ensemble de l'hypercube
.
Le nombre
d'hypercubes
compris dans
est donné par la formule suivante
D 7 :
L'hypercube est aussi un
graphe médian, et en particulier le seul graphe médian régulier. On peut donc appliquer la formule suivante des graphes médians
D 7 :
Certains types de sous-graphe sont particulièrement utiles en termes de communications. Par exemple, un
spanner est un sous-graphe couvrant, c'est-à-dire qui contient tous les sommets, mais qui contient moins d'arêtes. Contenir moins d'arêtes peut augmenter les distances entre des sommets du graphe, et l'on distingue ainsi les spanners multiplicatifs, où la distance peut être multipliée par un facteur
, des spanners additifs où la distance peut être augmentée d'un montant
. Dans le cas d'un spanneur additif sur
, des résultats
D 8 concernent les degrés du spanneur :
- si
et 
, alors le plus petit degré maximal 
est 
.
- si
et est grand, il existe un spanneur de degré moyen au plus 
.
Pour avoir un spanner 2-additif de
on sélectionne les arêtes satisfaisant une des trois conditions.
De nombreuses études sur les spanners, et des constructions pour des modèles généralisés de l'hypercube, sont dues à Arthur L. Liestman et Thomas C. Shermer
B 2. Ils ont en particulier proposé un spanner additif avec un montant
où les arêtes sont celles dont les extrémités
sont données par les trois conditions suivantes :
Ce processus est illustré dans l'image ci-contre où les arêtes satisfaisant une des conditions sont surlignées ; l'ensemble de ces arêtes constitue le spanner. Pour obtenir un chemin entre deux sommets, considérons que l'on démarre d'un sommet
. On inverse d'abord ses coordonnées paires, car la condition (1) impose l'existence d'une arête sur tout sommet commençant par 0 avec une différence sur bit pair. On change ensuite la première coordonnée en 1 grâce à la condition (3), à partir de quoi on peut inverser toutes les coordonnées impaires par la condition (2). Si le sommet de destination est
alors on est arrivé car on commence par 1 et les coordonnées paires comme impaires ont pu être inversé ; si le sommet de destination est
on utilise une dernière inversion par la condition (3). Le cas où le sommet d'origine est
est traité de façon similaire : inverser les coordonnées impaires, passer la première coordonnée en 0, inverser les coordonnées paires, passer la première coordonnée en 1 si nécessaire. Dans l'image ci-contre, on voit le délai de 2 si on cherche un chemin de
à
: ce qui se ferait normalement directement en une étape doit se faire en trois étapes, en passant par
et
.
Dans le problème de la diffusion (anglais
broadcast), un nœud source souhaite diffuser une information à tous les autres nœuds. Dans le modèle classique, à chaque étape un nœud donné peut transmettre au plus une information, cette information utilisant une arête et étant transmise à la fin de l'étape. Dans ce modèle, la diffusion la plus performante est celle où, à chaque étape, chaque nœud en contacte un autre, c'est-à-dire que le nombre de nœuds contactés est doublé. Le nombre d'étapes minimal est donc
; un graphe pouvant finir une diffusion en
étapes quelle que soit l'origine et en minimisant le nombre d'arêtes est un
graphe de diffusion minimale (anglais
minimal broadcast graph). Dans le cas où
, le nœud source doit avoir au moins
voisins car il doit diffuser à chaque étape pour faire doubler le nombre de voisins ; la source n'étant pas fixée, on obtient que chaque nœud doit avoir au moins
voisins d'où
arêtes (
vient du partage de chaque arête dans un graphe non-orienté), ce qui est précisément le cas d'un hypercube. Ainsi, l'hypercube est un graphe de diffusion minimale.
Parmi les problèmes proches se trouve le commérage (anglais
gossip) où chaque nœud veut échanger une information avec tous les autres, autrement dit chaque nœud est la source d'une diffusion. Des cas particuliers s'intéressent aux variantes locales : par exemple, dans un commérage 'local', chaque nœud veut apprendre les messages de ses voisins
D 9.
Architectures de machines parallèles[modifier]
L'addition de 8 nombres en séquentiel (haut) et en parallèle (bas). Les étapes sont numérotées en rouge.
Pour avoir une idée du gain en performances en utilisant des machines parallèles, considérons l'addition de
nombres. Sur une machine séquentielle, on additionne le premier nombre avec le second, puis on rajoute le troisième, etc., Au total,
étapes sont nécessaires. Sur une machine parallèle, chaque processeur réalise l'addition d'une paire de nombres en une étape, puis les résultats de deux paires sont additionnés, etc. Au total,
étapes sont nécessaires. Ainsi, pour 1 000 nombres, une machine séquentielle utilisera 999 étapes tandis qu'il n'en faut que 11 sur une machine parallèle ; un autre exemple est illustré ci-contre. Le gain est encore plus significatif pour d'autres opérations, par exemple une instance d'inversion de matrice peut nécessiter 40 000 étapes sur une machine séquentielle contre 61 sur une machine parallèle
D 10.
Au début des années 1960, des idées furent proposées pour concevoir un ordinateur parallèle avec une architecture en hypercube : « il y a
modules, chacun connecté directement à
autres ; en particulier, chaque module est placé sur le sommet d'un cube n-dimension, et les arêtes de ce cubes sont les câbles »
D 10. Les justifications dans le choix de l'hypercube peuvent paraître faible au regard des connaissances actuelles sur les familles de graphes, mais il s'avère que l'hypercube a de nombreuses propriétés utiles : il est
arc-transitif et
distance-transitif (en), ce qui implique que toutes ses arêtes jouent le même rôle et que tous ses sommets ont les mêmes propriétés de distance. Par ailleurs, le compromis entre le degré des sommets et la distance entre eux reste raisonnable, et la navigation peut se faire de façon délocalisée, ce qui est une des principales raisons citées à l'origine. En résumé, les propriétés de transitivité permettent d'obtenir une égalité entre les processeurs, et la communication entre les processeurs peut-être rapide (distance faible) en ayant besoin de peu d'informations (délocalisé).
Vingt ans se sont écoulés entre les idées du début des années 1960 et la première production, avec le
Cosmic CubeD 11 de
Caltech (64 processeurs Intel 8086/86 embarquant chacun 128Kb de mémoire) en 1983. De nombreuses autres machines sont alors produites, comme les Ametek série 2010, les
Connection Machine (en)D 12 CM-1/CM-2, les
nCUBE (en) et les iPSC d'
Intel. De nombreuses études sur les performances des machines parallèles utilisant une architecture en hypercube sont réalisées au
laboratoire national d'Oak Ridge sous le contrat DE-AC05-84OR21400
D 13. En effet, ce laboratoire créé à l'origine pour le
Projet Manhattan (conception de la première
bombe atomique) s'est reconverti sur des sujets tels que la sécurité nationale et les
supercalculateurs. Parmi les modèles étudiés figurent les Intel iPSC/860, iPSC/1 et iPSC/2, ainsi que les nCUBE 3200 et 6400 ; les caractéristiques de ces machines sont résumées ci-dessous.
Configurations de supercalculateurs avec architectures en hypercubeD 13
| iPSC/860 | iPSC/2 | iPSC/1 | N6400 | N3200 |
|---|
| Nombre de nœuds | 128 | 64 (max 128) | 64 (max 128) | 64 (max 8192) | 64 (max 1024) |
|---|
| Processeur du nœud | Intel i860 | Intel 80286/387 | Intel 80386/287 | 64-bit | 32-bit |
|---|
| Fréquence d'horloge | 40 MHz | 16 MHz | 8 MHz | 20 MHz | 8 MHz |
|---|
| Mémoire par nœud | 8M | 4M (max 16M) | 512K (max 4.5M) | 4M (max 64M) | 512K |
|---|
| Débit nominal | 22 Mb/s | 22 Mb/s | 10 Mb/s | 20 Mb/s | 8 Mb/s |
|---|
| Système d'exploitation | NX V3.2 | XENIX | XENIX | Vertex v2.0 | Vertex 2.3 |
|---|
Les performances précises de ces processeurs peuvent être trouvées dans les rapports d'Oak Ridge. Au niveau de l'analyse des performances pour la communication, il est préférable d'utiliser un modèle à coût linéaire plutôt qu'à coût constant. Autrement dit, on ne peut pas considérer qu'envoyer un message
ait un coût en temps fixe
quelle que soit la longueur du message : on considère plutôt que le coût en temps est fonction de la longueur du message, et qu'initier la transmission a également un coût
, ce qui entraîne le modèle
. Le coût
est significatif par rapport à
: cela prend par exemple prend 697µs pour établir la communication dans un iPSC/2, mais seulement 0.4µs pour chaque bit transmit.
Algorithmes parallèles[modifier]
Répartir les données sur un hypercube[modifier]
Division de données sur un hypercube
On souhaite appliquer un filtre sur une image.
De nombreuses informations sur les algorithmes pour des architectures en hypercubes à la fin des années 80 furent publiées dans la troisième conférence
Hypercube Concurrent Computers and ApplicationsA 6 (« Ordinateurs concurrents en hypercube et applications »). Utiliser une machine parallèle n'augmente pas
automatiquement la performance d'un algorithme : non seulement les algorithmes doivent être conçus de façon à tirer profit de l'architecture, mais les données ne peuvent pas toujours être partitionnées pour être traitées par différents processeurs, et ces processeurs ont également besoin de communiquer. Dans l'exemple de l'addition, le coût de communication était considéré comme négligeable, et ceci est l'hypothèse que nous conserverons par la suite : en effet, les propriétés de la machine (temps de communication, lecture/écriture, ...) sont généralement ignorés dans l'analyse des algorithmes, et on se concentre sur les dépendances entre les données et les façons de rendre le calcul parallèle sur un hypercube.
Une des opérations les plus courantes en traitement d'image consiste à utiliser un filtre linéaire, c'est-à-dire à appliquer une
matrice de convolution. Pour bénéficier de l'architecture en hypercube, l'image doit être divisée en zones égales, et chaque zone assignée à un processeur. Mudge et Abdel-Rahman ont suggéré de considérer l'image comme étant une
table de Karnaugh utilisant le
code de GrayD 14, ainsi que sur l'exemple ci-contre : si on considère une zone de l'image et ses coordonnées dans la table, alors on obtient directement le processeur auquel l'assigner. Par ailleurs, l'utilisation du code de Gray conserve l'adjacence : deux zones adjacentes dans l'image seront placées sur deux processeurs adjacents, sauf pour les coins. Le filtre, tel que celui de
Sobel, est appliqué par chaque processeur à la zone qui lui est assigné. Si le filtre a besoin de certains pixels dépassant la zone disponible à un processeur, il peut la demander au processeur voisin en utilisant les propriétés d'adjacence ; pour des coûts plus faibles en communication, chaque processeur peut également avoir une zone de l'image dont la taille correspond à celle nécessaire pour le traitement plutôt qu'à une partition stricte.
Réutilisation d'algorithmes par plongements[modifier]
Un
plongement permet à ce qu'un réseau soit simulé par un autre : aux sommets du réseau d'origine sont associés des sommets dans le réseau simulant, et deux sommets voisins sont séparés par un chemin. Ainsi, un algorithme conçu spécialement pour un réseau peut être réutilisé dans un autre grâce à un plongement. On s'intéresse donc à deux cas : réutiliser des algorithmes sur des hypercubes (1), ou utiliser des algorithmes pour l'hypercube dans d'autres réseaux (2). Autrement dit, l'hypercube est soit un réseau simulant (1), soit un réseau simulé (2). La qualité d'un plongement permet de savoir quelles sont les différentes pertes en performance de l'algorithme. Pour cela, on considère plusieurs facteurs
C 2 :
- Congestion. Elle donne le ralentissement si plusieurs arrêtes du réseau simulé sont utilisées simultanément : elle mesure le nombre d'arêtes du réseau simulé qui sont associées à une seule arête dans le réseau simulant, et ainsi une congestion de 2 indique que le réseau simulant aura besoin de 2 étapes pour transporter les messages que le réseau simulé pouvait avoir en une étape.
- Dilatation. Elle peut-être considérée comme le ralentissement des communications : elle mesure l'augmentation de la distance entre deux sommets dans le réseau simulant par rapport au simulé, et ainsi une dilatation de 2 signifie que toute communication qui se faisait en une étape en prendra maintenant 2.
- Charge. Elle indique le ralentissement pour le calcul sur un processeur : elle donne le nombre de sommets du réseau simulé associés à un seul sommet dans le réseau simulant
Pour l'hypercube comme réseau simulant, toute grille à deux dimensions a un plongement
C 1 avec une dilatation d'au plus 2 et une
expansion minimale, une grille à trois dimensions a une dilatation entre 2 et 5, et l'arbre binaire complet à
nœuds a un plongement de dilatation 1 sur
.
Parallélisme automatique[modifier]
Si un programme utilise plusieurs
tâches et que l'on a des informations sur la façon dont ces tâches communiquent, alors il peut être possible de faire bénéficier le programme d'une machine parallèle. En effet, la structure de la communication des tâches définit un graphe, et celui-ci peut être simulé entre autres par un hypercube en cherchant un plongement, tel qu'étudié dans la section précédente. Dans l'autre cas extrême, si toute tâche communique fréquemment avec toutes les autres, alors les communications sont données par un graphe complet et la simulation par une machine parallèle est peu performante. Des solutions intermédiaires ont été développées s'il n'y a pas d'informations sur la communication des tâches mais qu'elle se fait à fréquence modérée
D 15.
L'hypercube était très utilisé pour les architectures de machines parallèles, et certaines de ses propriétés étaient jugées perfectibles dans ce cadre. Le principal problème est la croissance d'un hypercube, où le nombre de sommets doit doubler d'une dimension à l'autre : dans une machine, plus de flexibilité est désirable afin de pouvoir ajouter
quelques processeurs. Plusieurs aspects sont aussi liés à sa réalisation par des circuits électroniques. Premièrement, l'hypercube n'est pas planaire et aura donc des chevauchements dans le circuit : en réduire le nombre simplifie le circuit. Deuxièmement, l'hypercube est défini comme un graphe non-orienté, mais « un réseau basé sur une orientation
de
utilise la moitié du nombre de broches et câbles par rapport à
»
D 16 : il est donc intéressant de trouver une orientation conservant des performances similaires. Enfin, il peut être désirable de réduire les distances dans l'hypercube pour les performances en termes de communications.
L'hypercube comme bloc de base[modifier]
formé de
hypercubes
, chacun constituant un cluster dont le numéro est encadré.
Un
hierarchical cubic networkD 17 
est formé de
-cubes, où chaque cube est désigné comme un
cluster. Chacun de ces clusters est utilisé comme un bloc de base, et chaque nœud d'un cluster a un lien supplémentaire le reliant à un autre cluster ; ces liens sont déterminés par l'algorithme suivante pour le graphe
composé de
-cubes, où
désigne le sommet
du cluster
et
est le
complément bit à bit de
:
Les auteurs montrèrent que, à tailles égales, ce graphe a un diamètre d'un quart plus faible que celui de l'hypercube, et la moitié du nombre de liens. Cependant, dans certaines situations la diffusion est plus lente que sur un hypercube, et avoir un graphe moins dense revient à être plus exposé lorsque des pannes surviennent sur les liens.
Cubes de Fibonacci[modifier]
Une autre variante ayant été depuis particulièrement étudiée est le
Cube de FibonacciD 18. Les conditions fondamentales du cube de Fibonacci de dimension
, noté
, sont les mêmes que celles de l'hypercube : chaque sommet porte une étiquette de longueur
sur un alphabet
, et deux sommets sont adjacents si leurs étiquettes ne différent que d'un symbole. Cependant, on rajoute une contrainte : une étiquette valide ne peut avoir deux
consécutif. Ainsi, ci-dessous, on voit que les cubes de Fibonacci
peuvent se retrouver comme sous-graphes des hypercubes
en éliminant les étiquettes contenant deux
consécutifs.
La construction par récurrence
D 19 peut-être définie par une
grammaire formelle en énonçant les étiquettes valides pour les sommets, puis en considérant le graphe
comme le sous-graphe de l'hypercube
induit par les sommets valides
:
Hypercubes recâblés[modifier]
Dans le cas où réduire la distance soit le principal objectif, il est courant d'utiliser des procédures de recâblage comme on le voit encore dans le cas de l'effet
petit monde. De nombreuses procédures ont été proposées, et les plus significatives sont résumées dans le tableau ci-dessous avec leurs performances sur la distance maximale (
i.e. le diamètre) et moyenne ainsi que le nombre de recâblages nécessaire. Le nom de chacune des procédures est conservé à partir des articles d'origines, où
twisted signifie recâblé, et suivi de l'année à laquelle la procédure fut publiée.
Listes de variantes de l'hypercube par recâblageD 1. Le temps de routage est toujours en O(n).
| Nom | Diamètre | Distance moyenne | Nombre d'arêtes recâblées |
|---|
| Hypercube | |  | 0 |
|---|
| Twisted cube (1987) |  |  |  |
|---|
| Twisted hypercube (1991) | |  |  |
|---|
| Twisted N-cube (1991) | |  | |
|---|
| Generalized twisted cube (1993) |  |  |  |
|---|
| 0-Möbius Cube (1995) |  |  |  |
|---|
Graphe libre d'échelle par contraction[modifier]
L'hypercube
a été contracté dans
et deux coordonnées remplacées par « _ ».
Dans les années 2000, de nombreux modèles furent proposés pour prendre en compte des caractéristiques communes à de nombreux réseaux. Deux des principales caractéristiques sont l'effet
petit monde et l'effet
libre d'échelle. Il est possible de modifier un hypercube afin d'obtenir l'effet libre d'échelle, tout en continuant à bénéficier de sa propriété de routage local
C 3. Pour cela, des sommets sont
contractés à la condition qu'ils ne diffèrent que sur une coordonnée qui sera remplacé par un joker « _ ». Après une séquence de contractions, c'est-à-dire plusieurs contractions successives, il est toujours possible de trouver un chemin d'un sommet
à un sommet
en utilisant leurs coordonnés et en remplaçant les jokers « _ » par les coordonnées de
.
La condition de ne différer que sur une coordonnée tout en opérant une séquence de contractions conduit à ce qu'un sous-hypercube soit contracté, et le degré du sommet
résultant de la contraction d'un hypercube
dans
,
est :
En résumé, l'effet libre d'échelle est obtenu par contraction de sous-hypercubes de grande taille et les algorithmes de navigation n'ont pas besoin d'être modifiés.
Références
En musique, le nombre d'or est recherché à la fois dans l'
harmonie et dans le
rythme.
Le terme d'harmonie désigne ici une technique permettant de choisir les différentes notes jouées simultanément. Durant une période qui s'étend du
xvie siècle au début du
xxe siècle, elle est essentiellement
tonale, à l'image de la musique de
Bach ou
Mozart. Aucune série de deux notes ne définit une
proportion d'or. L'approximation la plus proche étant la
sixte mineure obtenue par deux sons dont les
fréquences définissent un rapport de 8/5 = 1,6 (la sixte majeure correspondant à un rapport de fréquence de 5/3 = 1,66 est une approximation moins bonne). Pour cette raison, le nombre d'or est souvent recherché dans la musique du
xxe siècle. De nouvelles
gammes sont explorées, comme la gamme décatonique ou 10-TET
104 (
ten-ton equal temperament). Dans celle-ci, l'
octave est partagée en 10 parties égales. Chaque
degré représente alors un écart de 2
1/10. Pour cette gamme, le nombre d'or est proche du rapport défini par deux notes séparées de 7 degrés. La présence du nombre d'or ici est néanmoins un peu fortuite. Un écart entre 7 degrés donne une proportion de 2
7/10 approximativement égal à 1,624.
À l'exception de compositeurs comme Xenakis où l'usage du nombre d'or est explicité par l'auteur
56, l'absence de preuve définitive empêche le consensus
112. La polémique est néanmoins de nature différente de celle qui sévit, par exemple en archéologie. Ici la position favorable à l'existence d'un usage large du nombre d'or est défendue par des institutions professionnelles comme l'
Ircam110 ou une thèse d'université comme
celle de Montréal105.
Esthétique mathématique[modifier]
Une question récurrente est celle de l'existence ou non d'une réalité scientifique de l'idée de beauté associée au nombre d'or. Elle s'inscrit dans le cadre général d'une théorie scientifique de l'esthétique. Certains artistes, comme Xenakis en sont persuadés :
« Or, les durées musicales sont créées par des décharges musculaires qui actionnent les membres humains. Il est évident que les mouvements de ces membres ont tendance à se produire en des temps proportionnels aux dimensions de ces nombres. D’où la conséquence : les durées qui sont en rapport du nombre d’or sont plus naturelles pour les mouvements du corps humain56 ». Charles Henry, dans le domaine des arts picturaux, inscrit le nombre d'or dans une vaste théorie de cette nature, traitant non seulement des proportions, mais aussi de la couleur et des contrastes
44.
Préfigurant une démarche de nature
sociologique comme celle d'
Émile Durkheim, le philosophe allemand
Gustav Fechner tente des expériences statistiques pour
valider scientifiquement une association humaine entre le beau et le rectangle d'or
113. Des formes sont présentées à un public qui évalue les proportions les plus esthétiques. Si les résultats vont dans le sens de l'existence d'un canon de beauté construit à l'aide de la divine proportion, le protocole choisi ne correspond pas aux critères actuels de rigueur
114. Une deuxième expérience, plus objective
114 met en évidence une préférence pour un format proche du
16/9 de la télévision. Une fois encore, et malgré son caractère plus rigoureux, le caractère universel d'un tel format n'est pas établi.
Si l'intuition d'artistes comme Xenakis, Valéry ou Le Corbusier laisse présager l'existence d'une transcendance esthétique du nombre d'or, aucune approche scientifique ne permet aujourd'hui de confirmer cette hypothèse.
- Marguerite Neveux et H. E. Huntley, Nombre d'or - radiographie d'un mythe, Seuil, coll. « Points / Sciences » (no 108), 1995 (ISBN 978-2-02025916-3).
Ce livre est la référence sur l'analyse critique de l'usage du nombre d'or dans les différents domaines artistiques.
- Matila Ghyka, Le nombre d’or : Rites et rythmes pythagoriciens dans le développement de la civilisation occidentale, Gallimard, 1976 (1re éd. 1931), 456 p. + hors texte 65 p.(ISBN 978-2-07029298-1).
Cet ouvrage est à l'origine du mythe moderne du nombre d'or. Ce livre a séduit de nombreux penseurs comme Paul Valéry ou Le Corbusier.
- Le Corbusier, Le Modulor : Essai sur une mesure harmonique à l'échelle humaine applicable universellement à l'architecture et à la mécanique, L'Architecture d'aujourd'hui, coll. « Ascoral », 1983 (1re éd. 1949) (ISBN 978-2-90483301-4).
Ce livre est le premier d'une série de deux avec Modulor 2 – 1955 (La parole est aux usagers). Il explicite et théorise les raisons qui amènent Le Corbusier à utiliser le nombre d'or en architecture.
- Guy Marchand, Bach ou la Passion selon Jean-Sébastien : De Luther au nombre d'or, L'Harmattan, 2003 (ISBN 978-2-7475-4651-5).
- (en) Roger Herz-Fischler, A Mathematical History of the Golden Number, Dover, 1998 (ISBN 978-0-48640007-5)
La
théorie des graphes est une théorie
informatique et
mathématique. Les
algorithmes élaborés pour résoudre des problèmes concernant les
objets de cette théorie ont de nombreuses applications dans tous les domaines liés à la notion de réseau (
réseau social,
réseau informatique,
télécommunications, etc.) et dans bien d'autres domaines (par exemple
génétique) tant le concept de graphe, à peu près équivalent à celui de
relation binaire (à ne pas confondre donc avec
graphe d'une fonction), est général. De grands théorèmes difficiles, comme le
théorème des quatre couleurs et le
théorème des graphes parfaits, ont contribué à asseoir cette matière auprès des mathématiciens, et les questions qu'elle laisse ouvertes, comme la
conjecture d'Hadwiger, en font une branche vivace des
mathématiques discrètes.
Définition de graphe et vocabulaire[modifier]
Un graphe est un ensemble de points, dont certaines paires sont directement reliées par un (ou plusieurs) lien(s). Ces liens peuvent être orientés, c'est-à-dire qu'un lien entre deux points
et
relie soit
vers
, soit
vers
: dans ce cas, le graphe est dit
orienté. Sinon, les liens sont symétriques, et le graphe est
non orienté.
Dans la littérature récente de la théorie des graphes, les points sont appelés les
sommets (en référence aux
polyèdres) ou les
nœuds (en références à la
loi des nœuds). Les liens sont appelés
arêtes dans les graphes non orientés et
arcs dans un graphe orienté.
L'
ensemble des sommets est le plus souvent noté
, tandis que
désigne l'ensemble des arêtes. Dans le cas général, un graphe peut avoir des
arêtes multiples, c'est-à-dire que plusieurs arêtes différentes relient la même paire de points. De plus, un lien peut être une
boucle, c'est-à-dire ne relier qu'un point à lui-même. Un graphe est
simple s'il n'a ni liens multiples ni boucles, il peut alors être défini simplement par un couple
, où
est un ensemble de
paires d'éléments de
. Dans le cas d'un graphe simple orienté,
est un ensemble de
couplesd'éléments de
. Notons qu'un graphe sans arête multiple peut être représenté par une
relation binaire, qui est symétrique si le graphe est non orienté.
Pour définir un graphe général, il faut une
fonction d'incidence
qui associe à chaque arête une paire de sommets (ou un couple en cas orienté). Ainsi, un graphe est un triplet
avec
. Toutefois l'usage veut que l'on note simplement
, sachant que ce n'est parfaitement rigoureux que pour les graphes simples.
Un article du mathématicien suisse
Leonhard Euler, présenté à l'Académie de
Saint Pétersbourg en 1735 puis publié en 1741, traitait du
problème des sept ponts de KönigsbergO 1, ainsi que schématisé ci-dessous. 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. Un chemin passant par toute arête exactement une fois fut nommé
chemin eulérien, ou circuit eulérien s'il finit là où il a commencé. Par extension, un graphe admettant un circuit eulérien est dit
graphe eulérien, ce qui constitue donc le premier cas de propriété d'un graphe. Euler avait formulé
1 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 HierholzerO 2. 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 et perdu depuis
O 3. Ce problème du cavalier fut étudié plus en détails au
xviiie siècle par les mathématiciens français
Alexandre-Théophile VandermondeO 4,
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
O 5. On accorde donc à Euler l'origine de la théorie des graphes parce qu'il fut le premier à proposer un traitement mathématique de la question, suivi par Vandermonde.
Liste des
arbres à 2, 3 et 4 sommets.
Au milieu du
xixe siècle, le mathématicien britannique
Arthur Cayley s'intéressa aux
arbres, qui sont un type particulier de graphe n'ayant pas de cycle,
i.e. dans lequel il est impossible de revenir à un point de départ sans faire le chemin inverse. En particulier, il étudia le nombre d'arbres à
n sommets
O 6et
montra qu'il en existe
. Ceci constitua « une des plus belles formules en
combinatoire énumérative »
O 7, domaine consistant à compter le nombre d'éléments dans un ensemble fini, et ouvrit aussi la voie à l'énumération de graphes ayant certaines propriétés. Ce champ de recherche fut véritablement initié par le mathématicien hongrois
George Pólya, qui publia en 1937
le théorème de dénombrement qui porte son nom, et le mathématicien hollandais
Nicolaas Govert de Bruijn. Les travaux de Cayley, tout comme ceux de Polya, présentaient des applications à la chimie et le mathématicien anglais
James Joseph Sylvester, co-auteur de Cayley, introduisit en 1878 le terme de "graphe" basé sur la chimie :
« Il peut ne pas être entièrement sans intérêt pour les lecteurs de Nature d'être au courant d'une analogie qui m'a récemment fortement impressionné entre des branches de la connaissance humaine apparemment aussi dissemblables que la chimie et l'algèbre moderne. […] Chaque invariant et covariant devient donc exprimable par un graphe précisément identique à un diagramme Kékuléan ou chemicograph
O 8. »
Un des problèmes les plus connus de théorie des graphes vient de la
coloration de graphe, où le but est de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon qu'aucun sommet n'ait la même couleur que ses voisins. En 1852, le mathématicien sud-africain
Francis Guthrie énonça le
problème des quatre couleurs par une discussion à son frère, qui demandera à son professeur
Auguste De Morgan si toute carte peut être coloriée avec quatre couleurs de façon à ce que des pays voisins aient des couleurs différentes. De Morgan envoya d'abord une lettre au mathématicien irlandais
William Rowan Hamilton, qui n'était pas intéressé, puis le mathématicien anglais
Alfred Kempe publia une preuve erronée
O 9 dans l’
American Journal of Mathematics, qui venait d'être fondé par Sylvester. L'étude de ce problème entraîna de nombreux développements en théorie des graphes, par
Peter Guthrie Tait,
Percy John Heawood,
Frank Ramsey et
Hugo Hadwiger.
Les problèmes de
factorisation de graphe émergèrent ainsi à la fin du
xixe siècle en s'intéressant aux sous-graphes couvrants, c'est-à-dire aux graphes contenant tous les sommets mais seulement une partie des arêtes. Un sous-graphe couvrant est appelé un
k-facteur si chacun de ses sommets a
karêtes et les premiers théorèmes furent donnés par
Julius PetersenO 10 ; par exemple, il montra qu'un graphe peut être séparé en 2-facteurs si et seulement si tous les sommets ont un nombre pair d'arêtes (mais il fallut attendre 50 ans pour que Bäbler traite le cas impair
O 11). Les travaux de Ramsey sur la coloration, et en particulier les résultats du mathématicien hongrois
Pal Turan, permirent le développement de la
théorie des graphes extrémaux s'intéressant aux graphes atteignant le maximum d'une quantité particulière (par exemple le nombre d'arêtes) avec des contraintes données
O 12, telles que l'absence de certains sous-graphes.
Dans la seconde moitié du
xxe siècle, le mathématicien français
Claude Berge contribue au développement de la théorie des graphes par ses contributions sur les
graphes parfaitsO 13 et l'introduction du terme d’
hypergraphe (suite à la remarque de Jean-Marie Pla l'ayant utilisé dans un séminaire) avec un monographe
O 14 sur le sujet. Son ouvrage d'introduction à la théorie des graphes
O 15 proposa également une alternative originale, consistant plus en une promenade personnelle qu'une description complète. Il marquera également la recherche française en ce domaine, par la création conjointe avec
Marcel-Paul Schützenberger d'un séminaire hebdomadaire à l'Institut Henri Poincaré, des réunions le lundi à la Maison des Sciences de l'Homme, et la direction de l'équipe Combinatoire de Paris.
Flots dans les réseaux[modifier]
Représentation du flot dans un graphe, indiquant pour chaque arête le flot
a qui la traverse et sa capacité maximale
b, sous la forme
a/b.
Coupe dans un graphe, avec la source
set le puits
t'.
Les Allemands
Franz Ernst Neumann et
Jacobi, respectivement physicien et mathématicien, fondèrent en 1834 une série de séminaires. Le physicien allemand
Gustav Kirchhoff était un des étudiants participant au séminaire entre 1843 et 1846, et il étendit le travail de
Georg Ohm pour établir en 1845 les
Lois de Kirchhoff exprimant la
conservation de l'énergie et de la charge dans un
circuit électrique. En particulier, sa loi des nœuds stipule que la somme des intensités des courants entrant dans un nœud est égale à celle qui en sort. Un circuit électrique peut se voir comme un graphe, dans lequel les sommets sont les nœuds du circuit, et les arêtes correspondent aux connexions physiques entre ces nœuds. Pour modéliser les courants traversant le circuit, on considère que chaque arête peut être traversée par un
flot. Ceci offre de nombreuses analogies, par exemple à l'écoulement d'un liquide comme l'eau à travers un réseau de canaux
Flot 1, ou la circulation dans un réseau routier. Comme stipulé par la loi des nœuds, le flot à un sommet est conservé, ou identique à l'entrée comme à la sortie ; par exemple, l'eau qui entre dans un canal ne disparaît pas et le canal n'en fabrique pas, donc il y a autant d'eau en sortie qu'en entrée. De plus, une arête a une limite de capacité, tout comme un canal peut transporter une certaine quantité maximale d'eau. Si l'on ajoute que le flot démarre à un certain sommet (la
source) et qu'il se termine à un autre (le
puits), on obtient alors les principes fondamentaux de l'étude des flots dans un graphe.
Si on considère que la source est un champ pétrolifère et que le puits est la raffinerie où on l'écoule, alors on souhaite régler les vannes de façon à avoir le meilleur débit possible de la source vers le puits. En d'autres mots, on cherche à avoir une utilisation aussi efficace que possible de la capacité de chacune des arêtes, ce qui est le
problème de flot maximum. Supposons que l'on « coupe » le graphe en deux parties, telle que la source est dans l'une et le puits est dans l'autre. Chaque flot doit passer entre les deux parties, et est donc limité par la capacité maximale qu'une partie peut envoyer à l'autre. Trouver la coupe avec la plus petite capacité indique donc l'endroit où le réseau est le plus limité, ce qui revient à établir le flot maximal qui peut le traverser
Flot 2. Ce théorème est appelé
flot-max/coupe-min et fut établi en 1956.
L’étude des flots réseaux se généralise de plusieurs façons. La recherche d'un maximum, ici dans le cas du flot, est un problème d'
optimisation, qui est la branche des mathématiques consistant à optimiser (
i.e. trouver un minimum ou maximum) une fonction sous certaines contraintes. Un flot réseau est soumis à trois contraintes
Flot 3 : la limite de capacité sur chaque arête, la création d'un flot non nul entre la source et le puits (
i.e. la source crée un flot), et l'égalité du flot en entrée/sortie pour tout sommet autre que la source et les puits (
i.e. ils ne consomment ni ne génèrent une partie du flot). Ces contraintes étant
linéaires, le problème d'un flot réseau fait partie de l'
optimisation linéaire. Il est également possible de rajouter d'autres variables au problème pour prendre en compte davantage de situations : on peut ainsi avoir
plusieurs sources et puits (en), une
capacité minimale (en) sur chaque arête, un
coût lorsqu'on utilise une arête (en), ou une
amplification du flot (en) passant par une arête.
Introduction de probabilités[modifier]
Schéma d'une transition de phase, ayant l'allure typique rencontrée dans le cas d'un graphe aléatoire.
Jusqu'au milieu du
xxe siècle, l'algorithme construisant un graphe n'avait rien d'aléatoire : tant que les paramètres fournis à l'algorithme ne changeaient pas, alors le graphe qu'il construisait était toujours le même. Une certaine dose d'
aléatoire fut alors introduite, et les algorithmes devinrent ainsi
probabilistes. Le mathématicien d'origine russe
Anatol Rapoport eut d'abord cette idée en 1957
Proba 1 mais elle fut proposée indépendamment deux ans après, de façon plus formelle, par les mathématiciens hongrois
Paul Erdős et
Alfréd RényiProba 2. Ceux-ci se demandèrent à quoi ressemble un graphe « typique » avec
n sommets et
m arêtes. Ils souhaitaient ainsi savoir quelles propriétés pouvaient être trouvées avec
n sommets, et
m arêtes créées au hasard. Une quantité fixe
m n'étant pas pratique pour répondre à cette question
Proba 3, il fut décidé que chaque arête existerait avec une probabilité
p. Ceci fut le début de la
théorie des graphes aléatoires, où l'on considère un nombre de sommets
n assez grand, et l'on s'intéresse à la probabilité
psuffisante pour que le graphe ait une certaine propriété.
Abstraction d'une pierre par une grille de 50 x 50. Seuls les canaux sont représentés.
Exemples de graphes aléatoires
20 sommets et probabilité 0.1
La
distribution du degré donne la quantité de sommets par nombre de connexions (par exemple, il y a 30 sommets ayant 25 voisins, où
30 est en ordonnée et
25 en abscisse). Le graphe aléatoire d'Erdős et Rényi engendre une
distribution normale.
Erdős et Rényi découvrirent que le graphe n'évoluait pas de façon linéaire mais qu'il y avait au contraire une probabilité critique
p après laquelle il changeait de façon radicale. Ce comportement est bien connu en physique : si l'on observe un verre d'eau que l'on met dans un
congélateur, il ne se change pas progressivement en glace mais plutôt brutalement lorsque la température passe en dessous de
0 °C. L'eau avait deux phases (liquide et glace) et passe de l'une à l'autre par un phénomène nommé
transition de phase, la transition étant rapide autour d'un
point critique qui est dans ce cas la température de
0 °C. Pour nombre de propriétés observées, les graphes aléatoires fonctionnent de la même manière
Proba 4 : il existe une probabilité critique
en dessous de laquelle ils se trouvent dans une phase sous-critique, et au-dessus de laquelle ils passent en phase sur-critique. Dans le cas d'un graphe aléatoire, la probabilité que l'on observe la propriété nous intéressant est faible en phase sous-critique mais devient très forte (
i. e.quasi-certitude) en phase sur-critique ; le tracé de la probabilité d'avoir la propriété en fonction de
p a donc une allure bien particulière, simplifiée dans le schéma à droite.
Au-delà du vocabulaire commun des phases, la
théorie des graphes aléatoires se retrouve en
physique statistique sous la forme de la
théorie de la percolationProba 5. Cette dernière visait à l'origine à étudier l'écoulement d'un fluide à travers un matériau
poreux. Par exemple, si l'on immerge une
pierre ponce dans un seau rempli d'eau
Proba 6, on s'intéresse à la façon dont l'eau va s'écouler dans la pierre. Pour modéliser ce problème, on se concentre sur les paramètres importants : l'âge ou la couleur de la pierre n'importe pas, tandis que les ouvertures ou 'canaux' dans lesquels peut circuler l'eau sont primordiaux. L'abstraction la plus simple est de voir une pierre comme une grille, où chaque canal existe avec une probabilité
p. On retrouve ainsi le modèle du graphe aléatoire, mais avec une contrainte
spatiale : un arc ne peut exister entre deux sommets que s'ils sont voisins dans la grille. Cependant, cette contrainte peut être levée pour établir une équivalence entre la théorie des graphes et celle de la percolation. Tout d'abord, un graphe de
n sommets peut être représenté par une grille avec
n dimensions ; puisqu'on s'intéresse au cas où
n est assez grand, c'est-à-dire
, ceci établit une équivalence avec la percolation en dimension infinie. De plus, il existe une dimension critique
telle que le résultat ne dépend plus de la dimension dès que celle-ci atteint
; on pense que cette dimension critique est 6, mais elle n'a pu être prouvée
Proba 7 que pour 19.
De nombreux modèles ont été proposés depuis le début des années 2000 pour retrouver des phénomènes observés dans des graphes tels que celui représentant les connexions entre des acteurs de Hollywood (obtenu par
IMDb) ou des parties du
Web. En 1999,
Albert-László Barabási et Réka Albert expliquèrent qu'un de ces phénomènes « est une conséquence de deux mécanismes : le réseau grandit continuellement avec l'ajout de nouveaux sommets, et les nouveaux sommets s'attachent avec certaines préférences à d'autres qui sont déjà bien en place »
Proba 8. Une certaine confusion s'installa autour de leur modèle : s'il permet effectivement d'obtenir le phénomène souhaité, il n'est pas le seul modèle arrivant à ce résultat et on ne peut donc pas conclure en voyant le phénomène qu'il résulte d'un processus d'attachement préférentiel. Les phénomènes de
petit monde et de
liberté d'échelle (en), pour lesquels de très nombreux modèles ont été proposés, peuvent être réalisés simplement par des graphes aléatoires
Proba 9 : la technique de Michael Molloy et
Bruce Reed (en)Proba 10 permet d'obtenir l'effet de libre d'échelle, tandis que celle de Li, Leonard et Loguinov conduit au petit-monde
Proba 11.
Représentations et invariants[modifier]
Étiquetage et morphismes[modifier]
Formellement un graphe est
étiqueté : chaque sommet ou arête appartient à un ensemble, donc porte une
étiquette. Typiquement, les graphes sont étiquetés par des nombres entiers, mais une étiquette peut en fait appartenir à n'importe quel ensemble : ensemble de couleurs, ensemble de mots, ensemble des réels. Les exemples ci-contre montrent des graphes étiquetés par des entiers et par des lettres. L'étiquetage d'un graphe peut être conçu de façon à donner des informations utiles pour des problèmes comme le
routage : partant d'un sommet
, on veut arriver à un sommet
, c'est-à-dire que l'on souhaite acheminer une information de
à
. Selon la façon dont les sommets sont étiquetés, les étiquettes que portent
et
peuvent nous permettre de trouver facilement un chemin. Par exemple, dans le
graphe de Kautz (en) où la distance maximale entre deux sommets est
, imaginons que l'on soit à un sommet étiqueté
et que l'on souhaite aller à
: il suffit de décaler l'étiquette en introduisant la destination
R 1, ce qui donne le chemin
Ce chemin se lit de la façon suivante : si on se trouve au sommet étiqueté
alors on va vers le voisin portant l'étiquette
, et ainsi de suite.
On se retrouve cependant face à un problème : si on regarde plus haut l'illustration de la liste des arbres à 2, 3 et 4 sommets, beaucoup d'entre eux ont exactement la même
structure mais un étiquetage différent (donné ici par des couleurs). Pour étudier uniquement la structure, il faut donc un outil permettant d'ignorer l'étiquetage, c'est-à-dire de donner une équivalence structurelle. Pour cela, on introduit la notion de morphisme. Un
morphisme de graphesR 2, ou
homomorphisme de graphe, est une
application entre deux graphes qui respecte la structure des graphes. Autrement dit l'image du graphe
dans
doit respecter les relations d'adjacences présentes dans
. Plus précisément, si
et
sont deux graphes, une application
est un morphisme de graphe si
où
transforme les sommets de G en ceux de H, et
les arêtes de G en celles de H en respectant la contrainte suivante : s'il existe une arête
entre deux sommets de
alors il doit y avoir une arête
entre les deux sommets correspondants de
. On dit de l'homomorphisme
qu'il est une
injection (respectivement
surjection) si ses deux fonctions
et
sont injectives (respectivement surjectives); si elles sont à la fois injectives et surjectives, c'est-à-dire
bijectives, alors
est un
isomorphisme de graphes. Si deux graphes sont isomorphes, alors ils ont la même structure : peu importe la façon dont ils sont dessinés ou étiquetés, il est possible de déplacer les sommets ou de changer les étiquettes pour que l'un soit la copie conforme de l'autre, ainsi qu'illustré ci-dessous. On désigne alors par graphe
non étiqueté la
classe d'équivalence d'un graphe pour la relation d'isomorphisme. Deux graphes isomorphes seront alors considérés comme égaux si on les considère en tant que graphes non étiquetés.
| Graphe G | Graphe H | Isomorphisme
entre G et H |
|---|
 |  | ƒ(a) = 1
ƒ(b) = 6
ƒ(c) = 8
ƒ(d) = 3
ƒ(g) = 5
ƒ(h) = 2
ƒ(i) = 4
ƒ(j) = 7
|
Le mot graphe peut désigner, selon les contextes, un graphe étiqueté ou non étiqueté. Quand on parle du graphe du web, les étiquettes sont des URL et ont un sens. Le mot est utilisé pour désigner un graphe étiqueté. À l'opposé le
graphe de Petersen est toujours considéré à isomorphisme près, donc non étiqueté, seules ses propriétés structurelles étant intéressantes.
-
Graphe étiqueté par des entiers
Graphe étiqueté par des lettres
Tout graphe
peut être représenté par une
matrice. Les relations entre arêtes et sommets, appelées les relations d'incidence, sont toutes représentées par la
matrice d'incidencedu graphe. Les relations d'adjacences (si deux sommets sont reliés par une arête ils sont adjacents) sont représentés par sa
matrice d'adjacence. Elle est définie par
De nombreuses informations d'un graphe peuvent être représentées par une matrice. Par exemple, la
matrice des degrés est une
matrice diagonale où les éléments
correspondent au nombre de connexions du sommet
, c'est-à-dire à son
degré. En utilisant cette matrice et la précédente, on peut également définir la
matrice laplacienne 
; on obtient sa forme normalisée
par
, où
dénote la
matrice identité, ou on peut aussi l'obtenir directement par chacun de ses éléments :
Ces représentations dépendent de la façon dont les sommets du graphe sont étiquetés. Imaginons que l'on garde la même structure que dans l'exemple ci-dessus et que l'on inverse les étiquettes
1 et
6 : on inverse alors les colonnes
1 et
6 de la matrice d'adjacence. Il existe en revanche des quantités qui ne dépendent pas de la façon dont on étiquette les sommets, tels que le degré minimal/maximal/moyen du graphe. Ces quantités sont des
invariants du graphe : elles ne changent pas selon la numérotation. Tandis qu'une matrice d'adjacence ou laplacienne varie, son
spectre, c'est-à-dire l'ensemble de ses
valeurs propres 
, est un invariant. L'étude du rapport entre les spectres et les propriétés d'un graphe est le sujet de la
théorie spectrale des graphesR 3 ; parmi les rapports intéressants, le spectre donne des renseignements sur le
nombre chromatique, le nombre de composantes connexes et les cycles du graphe.
Décompositions arborescentes et en branches[modifier]
Décomposition arborescente à 6 sommets d'un graphe à 8 sommets. Chaque nœud de la décomposition contient au plus trois sommets du graphe original, et la profondeur de cette décomposition est donc 2.
Les graphes permettant de représenter de nombreuses situations, il existe de nombreux algorithmes (
i.e. programmes) les utilisant. La
complexité d'un algorithme consiste essentiellement à savoir, pour un problème donné, combien de temps est nécessaire pour le résoudre et quel est l'espace machine que cela va utiliser. Certaines représentations de graphes permettent d'obtenir de meilleures performances, c'est-à-dire que le problème est résolu plus rapidement ou en occupant moins d'espace. Dans certains cas, un problème
NP-complet (classe la plus ardue) sur une représentation d'un graphe peut être résolu en temps polynomial (classe simple) avec une autre représentation; l'idée n'est pas qu'il suffit de regarder le graphe différemment pour résoudre le problème plus vite, mais que l'on « paye » pour le transformer et que l'on « économise » alors pour résoudre le problème. Une telle transformation est la
décomposition arborescente proposée par les mathématiciens
Robertson et
Seymour dans leur série
Graph MinorsR 4. Intuitivement, une décomposition arborescente représente le graphe d'origine
par un arbre, où chaque sommet correspond à un sous-ensemble des sommets de G, avec quelques contraintes. Formellement, pour un graphe donné
, sa décomposition arborescente est
où
est un arbre et
une fonction associant à chaque sommet
un ensemble de sommets
. Trois contraintes doivent être satisfaites :
. La décomposition n'oublie aucun sommet du graphe d'origine.
tel que 
.
si 
est sur le chemin de à 
alors 
. Si l'on prend l'intersection des sommets abstraits par deux nœuds de l'arbre, alors cette intersection doit être contenue dans un sommet intermédiaire. Sur l'exemple ci-contre, l'intersection de {A,B,C} et {C,D,E} est {C} qui est bien contenue dans le sommet intermédiaire {C,B,E}.
La
largeur arborescente 
d'une décomposition
d'un graphe
est
, c'est-à-dire la taille du plus grand ensemble représenté par un sommet moins 1 ; on peut la voir comme l'abstraction maximale : pour un sommet de l'arbre, jusqu'à combien de sommets du graphe représente-t-on ? Construire la décomposition arborescente d'un graphe quelconque avec la plus petite largeur arborescente est un problème NP-dur
R 5. Cependant, cela peut être fait rapidement pour certains graphes
R 6, ou approximée
R 7 pour d'autres tels les graphes planaires (
i. e. pouvant être dessinés sans croiser deux arêtes).
Exemple d'un arbre, ayant
1 comme racine,
{2,4,5,7} comme nœuds internes et
{3,6,8,9,10,11,12} comme feuilles.
Robertson et Seymour développèrent également le concept de
décomposition en branches. Pour la comprendre, il faut introduire davantage de vocabulaire sur un arbre. Dans les graphes, un arbre est dessiné "à l'envers" : on démarre de la racine en haut, et on descend jusqu'à atteindre les feuilles en bas ; tout sommet n'étant pas une feuille est appelé un 'nœud interne'. La décomposition en branches résulte en un arbre dans lequel tout nœud interne a exactement trois voisins (comme sur l'exemple ci-contre), et où chaque feuille représente une arête du graphe d'origine. La profondeur minimale de la décomposition d'un graphe
est notée
, et on a la relation
. De même que pour la décomposition arborescente, il est NP-dur de construire une décomposition en branches avec
minimal pour un graphe quelconque ; dans ce cas, cette construction est réalisable pour un
graphe planaireR 8.
Ces représentations sont utilisées sur des problèmes NP-complets par des techniques de
programmation dynamique, qui prennent généralement un temps exponentiel en
ou
. Un tel problème est par exemple l'
ensemble dominant : on veut savoir s'il y a un sous-ensemble
de sommets de taille au plus
tel qu'un sommet n'étant pas dans
y soit relié par une arête. Si le graphe est planaire, cette technique permet de résoudre le problème
R 9 en temps
.
Aspect algorithmique[modifier]
Structures de données[modifier]
La façon dont le graphe est représenté en tant qu'objet mathématique a été exposée dans la section précédente. Dans l'aspect algorithmique de la théorie des graphes, on cherche à concevoir un processus efficace pour traiter un problème faisant intervenir un graphe. Les principaux critères d'efficacités d'un processus sont le temps nécessaire avant d'obtenir la réponse, et l'espace que le processus consomme dans son travail. La façon dont on représente le graphe influence la performance en temps et en espace : par exemple, si l'on veut connaître l'existence d'une arête entre deux sommets, la matrice d'adjacence permettra d'obtenir un résultat immédiatement, ce que l'on appelle en
. En revanche, une opération de base telle que trouver le voisin d'un sommet est en
sur une matrice d'adjacence : dans le pire des cas, il faudra scanner la totalité de la colonne pour s'apercevoir qu'il n'y a pas de voisin. Une autre structure de données est la liste d'adjacences, consistant en un tableau dont l'entrée
donne la liste des voisins du sommet
: sur une telle structure, trouver un voisin se fait en
tandis que l'existence d'une arête est en
. Ainsi, au niveau du temps, le choix de la structure dépend des opérations de base que l'on souhaite optimiser.
Un graphe étiqueté et sa représentation par liste d'adjacence ci-contre
| Représentation par liste d'adjacence du graphe ci-contre: |
| 0 | adjacent à | 0,1,2,3 |
| 1 | adjacent à | 0 |
| 2 | adjacent à | 0,3,4 |
| 3 | adjacent à | 0,2 |
| 4 | adjacent à | 2 |
De même, l'espace qu'une structure consomme dépend du type de graphe considéré : un raccourci abusif consiste à dire qu'une liste d'adjacences consomme moins d'espace qu'une matrice car celle-ci sera
creuse, mais cela prend par exemple plus d'espace pour stocker un graphe aléatoire avec les listes qu'avec une matrice ; dans le cas général, une matrice utilise un espace
et les listes utilisent
donc
si le graphe est
dense alors
peut être suffisamment grand pour qu'une matrice consomme moins d'espace, et
si le graphe est peu dense alors les listes consommeront moins d'espace. Des modifications simples d'une structure de données peuvent permettre d'avoir un gain appréciable : par exemple, dans une représentation
partiellement complémentée d'une liste, un bit spécial indique si la liste est celle des voisins présents
ou manquants ; cette technique permet d'avoir des algorithmes linéaires sur le complément d'un graphe
Algo 1.
Tandis que ces structures sont locales, il existe aussi des structures de données
distribuées. Le principe de ces structures est de concevoir un
schéma d'étiquetage tel que, pour deux sommets
et
, on puisse répondre à une question comme « quelle est la distance entre
et
»
uniquement en utilisant les étiquettes de ces nœuds ; une telle utilisation des étiquettes a été vue en section «
Étiquetage et morphismes » avec le graphe de Kautz où l'on peut déduire le chemin entre deux sommets uniquement grâce à leur étiquette, et la longueur de ce chemin nous donne la distance. Un étiquetage est
efficace s'il permet de répondre à une question donnée uniquement en utilisant deux étiquettes, tout en minimisant le nombre maximum de bits d'une étiquette
Algo 2. Outre la distance, une question type peut être de tester l'adjacence, c'est-à-dire de savoir si deux sommets sont voisins ; notons que cela se ramène également au cas particulier d'une distance 1. Le premier exemple d'étiquetage efficace pour tester l'adjacence fut proposé dans le cas des arbres, et chaque étiquette est constituée de deux parties de
bits : la première partie identifie le sommet, et un nombre allant jusqu'à
nécessite
bits pour être
codé, tandis que la seconde partie identifie le parent de ce sommet ; pour tester l'adjacence, on utilise le fait que deux sommets sont voisins dans un arbre si et seulement si l'un est le parent de l'autre
Algo 3.
Sous-graphes utiles : séparateurs, spanners et arbres de Steiner[modifier]
Cette section est vide, insuffisamment détaillée ou incomplète.
Votre aide est la bienvenue !
L'efficacité d'un schéma d'étiquetage est lié à la taille des séparateurs du graphe.
Définition — un séparateur
est un sous-ensemble de sommet qui « sépare » les sommets du graphe en deux composants
et
tel que
et il n'y a pas d'arêtes entre des sommets de
et
.
Illustration d'un séparateur
Étant donné un graphe avec un ensemble de sommets
, ...
Si un graphe a des séparateurs de taille
, alors on peut par exemple concevoir des étiquettes de
bits pour la distance ; ceci permet directement d'en déduire l'étiquetage pour des graphes dont on connaît la taille des séparateurs, tels un graphe planaire où le séparateur est de taille
Algo 4. Enfin, il ne faut pas considérer que la taille de l'étiquetage mais également le temps nécessaire, étant donnés deux étiquettes, pour effectuer le
décodage répondant à la question (
i.e. quelle est la distance ? sont-ils voisins ?).
Réduction de données[modifier]
Cette section est vide, insuffisamment détaillée ou incomplète.
Votre aide est la bienvenue !
De nombreux problèmes sur les graphes sont NP-complets, c'est-à-dire durs à résoudre. Cependant, cette dureté est inégale : certaines parties du problème pe
.
. Il vaut exactement :
