Equation des graphes

Calembour

Petite formule que je trouve intéressante : 
Si on a $G$ un graphe, si on note $\alpha$ son nombre de sommets et $\beta$ son nombre d'arêtes et que l'on note $a_i$ le nombre de sommets "ayant" $i$ arêtes (c'est-à-dire connectés à $i$ autres sommets). Alors on a la formule : 

$$\alpha = 2 \beta +  \sum_{i = 0}^{\infty} a_i (-i + 1) $$ 

(Bien sûr la somme est en réalité finie car on est dans un graphe avec un nombre fini de points et d'arêtes a priori).

Par exemple pour un graphe complet, chaque sommet est relié à tous les autres, donc $a_{\alpha - 1} = \alpha$ (le nombre de sommets étant reliés à $\alpha - 1$ autre sommets est l'ensemble des sommets), tous les autres $a_i$ sont nuls, donc : 

$$ \alpha = 2 \beta - (\alpha - 2) \alpha $$ 

On retrouve la formule bien connue : 

$$ \beta = \frac{\alpha( \alpha - 1)}{2} $$

Si on prend un graphe "carré" de ce type : 

Alors on obtient la formule : 
$$ \alpha^2 - \alpha (1 + \beta) + \frac{\beta^2}{4} = 0 $$ 
(fonctionne pour n'importe quelle longueur de la base du carré)

A partir du moment où l'on sait déterminer les $a_i$, on a la formule. Par exemple pour le graphe carré, la détermination des $a_i$ est assez claire : il y a $4$ sommets connectés à $2$ autres sommets (les $4$ coins du carrés), donc $a_2 = 4$. Les sommets connectés à $3$ autres sommets sont sur les côtés du carrés sauf les $4$ coins, donc $a_3 = 4( \sqrt{\alpha} - 2 )$ etc.

Ce que je trouve intéressant, c'est ce lien entre "équation diophantienne", "géométrie des graphes" et combinatoire.

Prenons le problème à l'envers et regardons le problème de résoudre l'équation diophantienne dans $\mathbb{N} \times \mathbb{N}$ : 
$$  4x^2 - 4x(1 + y) + y^2 = 0 $$

Dans ce cas la correspondance que j'ai écrite plus haut permet de trouver des solutions et de les représenter géométriquement sous forme de graphe. Si on a un couple $(x,y)$ solution alors il correspond au graphe carré ayant $x$ sommets et $y$ arêtes. Ainsi pour trouver toutes les solutions, il suffirait de tracer un carré, donc on connait facilement le nombre de sommets (le carré du nombre de sommets sur un côté) et on compterait le nombres d'arêtes et ça nous fournirait un couple solution de l'équation diophantienne.

Si on veut être plus général, on peut dire que "l'équation d'un graphe", est de la forme $f(\alpha, \beta) = 0$ où $f$ est une fonction, et existe toujours d'après la formule que j'ai écrite plus haut.
On pourrait alors par exemple se demander à partir de quel moment une équation diophantienne à deux inconnues entières $f(x, y) = 0$ représente l'équation d'un graphe. Et si elle représente un graphe, est-ce que l'on peut trouver une méthode ou un algorithme qui nous construise ce graphe ? Est-ce qu'une équation diophantienne se réalise systématiquement sous forme de l'équation d'un graphe par exemple ? Est-ce qu'on peut exploiter des symétries géométriques d'un graphe afin d'en tirer des symétries par rapport à l'équation diophantienne correspond à ce graphe par exemple ? Prenons une équation diophantienne qui n'a pas de solution, est-ce qu'on pourrait trouver un argument géométrique/de graphe/combinatoire, qui prouverait géométriquement que cette équation diophantienne n'a pas de solution ?

Cordialement 
Calembour

raoul.S

Alors on a la formule : $\alpha = 2 \beta +  \sum_{i = 0}^{\infty} a_i (-i + 1)$

On a plus simplement la formule $\sum_{i = 0}^{\infty} a_i i=2\beta$ non ?

Calembour

@raoul.S

Effectivement on peut aussi l'écrire sous cette forme

raoul.S

Calembour a dit : 
Si on a un couple $(x,y)$ solution alors il correspond au graphe carré ayant $x$ sommets et $y$ arêtes

Pas forcément, par exemple le couple $(9,24)$ est bien solution mais ne correspond pas à un graphe carré.

Calembour a dit : 
On pourrait alors par exemple se demander à partir de quel moment une équation diophantienne à deux inconnues entières $f(x,y)=0$ représente l'équation d'un graphe. 

La question posée ainsi n'a pas vraiment de sens. En effet au début de ton fil tu n'as pas montré comment associer une équation à un graphe donné, mais à une famille de graphes (tous les graphes "carrés"). Et même pour une famille de graphes ton association n'est pas bien définie.

En fait je ne sais pas si tout ça a vraiment de l'intérêt. En effet à partir d'un couple $(x,y)$ d'entiers positifs solution d'une équation diophantienne donnée et vérifiant $y\leqslant \dfrac{x(x-1)}{2}$, on peut toujours obtenir un graphe (et même plusieurs généralement) à $x$ sommets et $y$ arrêtes.

gebrane

Bonjour, 
Ta formule est le lemme des poignées de main exprimé différemment, n'est-ce pas ?

Calembour

Merci pour ton retour @raoul.S

 @gebrane Il me semble que c'est en effet cette formule (je ne connaissais pas son nom). La seule différence, c'est que je partitionne l'ensemble des sommets en fonction de leur degré

Je m'étais posé la question posé la question pour un hypergraphe. Dans un graphe normal, une seule arête relie deux points, mais dans un hypergraphe une seule arête peut relier un nombre arbitraire de point. Notons $T_i$ le type $i$ d'arêtes, c'est-à-dire que une arêtes de type $i$ peut relier $n_i$ points entre eux.

J'avais trouvé une formule similaire pour un "hypergraphe" complet, dans le sens où c'est un graphe ayant $m$ types d'arêtes et où chaque sommet est relié une seule fois à tous les autres sommets de l'hypergraphe. Si on note $\beta_i$ le nombre d'arêtes de "type" $i$ dans le graphe, j'avais trouvé la formule : 

$$ \sum_{ i = 1}^m \binom{n_i}{2} \beta_i = \binom{\alpha}{2}  $$

Je pense qu'elle est correcte. 

Je pense qu'au final c'est possible de généraliser le lemme des poignées de main à un hypergraphe

Cordialement
Calembour

gebrane

Calembour a dit :

Je pense qu'au final c'est possible de généraliser le lemme des poignées de main à un hypergraphe

Tu peux regarder le lemme 2.7 de ce papier ; Je te laisse démontrer le lemme

Calembour

gebrane a dit :

Calembour a dit :

Je pense qu'au final c'est possible de généraliser le lemme des poignées de main à un hypergraphe

Tu peux regarder le lemme 2.7 de ce papier ; Je te laisse démontrer le lemme

Merci !

Tu es calé en théorie des graphes ?

gebrane

mon coté farceur me contraint  de ne pas donner suite  à ta requête

igrec27

Si on  s'intéresse aux fonctions associées aux divers graphes, il serait intéressant d'étudier les classes d'équivalences
des graphes pour cette fonction commune.