Théorie des graphes

[inviteeb15d3eb]

C'est une question assez simple, mais je me demande comment on fait pour le trouver :

Combien y'a-t-il d'arêtes dans les graphes simples C8, D8, R8, F8, et T8, des mouvements des pièces aux échecs?

C8 (étant le mouvement du cavalier dans un échéquier de 8X8)
D8 (la dame)
R8 (Le roi)
F8 (le fou)
T8 (La tour)

J'ai la réponse, mais je cherchais la démarche, merci!


-----

[invite9cf21bce]

C'est une question assez simple, mais je me demande comment on fait pour le trouver

Bonsoir.

Je ferais comme dans la plupart des cas quand on compte les arêtes d'un graphe simple non orienté : on compte, pour chaque sommet, le nombre d'arêtes qui en partent (= y arrivent) ; on additionne le tout, et on divise par deux.

Ici tu peux jouer sur les symétries pour avoir moins d'arêtes à compter.

Pour le cavalier (case de départ, nombre d'arêtes) :

a1 : 2
b1 et a2 : 3
c1 et a3 : 4
d1 et a4 : 4
b2 : 4
c2 et b3 : 6
d2 et b4 : 6
c3, d3, c4, b4 : 8

Ce qui fait 2+6+8+8+4+12+12+32 = 84 arêtes partant des sommets correspondant aux cases du quartier inférieur gauche.

Par symétrie, les arêtes comptées pour l'échiquier complet sont au nombre de 4*84.

En divisant par deux, chaque arête ayant été comptée deux fois : 2 * 84 = 168 arêtes au total.

Taar.

PS : c'est pour le graphe non orienté. Pour le graphe orienté, 4*84 = 336.

PPS : Ça se généralise à un échiquier plus grand : tu comptes les situations à 2, 4, 6, 8 arêtes.