Théorie des graphes

Bonjour, j’ai un quelques questions sur la théorie des graphes.

Graphes non-orientés

Boucles

Si je considère le graphe $G$ tel que $V(G) = \{A, B\}$ et $E(G) = \{ \{A, A\}, \{A, B\} \}$ alors $\deg(A) = 3$. Pourquoi pas $2$? On compte la boucle deux fois?

Lemme de la poignée de main

Je vois comment faire une preuve de ce lemme par double dénombrement. En revanche, mon prof nous a donné une preuve par récurrence sur le nombre de sommets que je ne comprend pas, la voici :

Graphes orientés

Un graphe orienté spécifique dont je ne connais pas le nom

Notre prof défini un graphe $G$ de la sorte :

$V(G) = \{u_{k, p} \space | \space k \geq 0, p \geq 0, p + k \leq 0 \}$ et $A(G) = \{(u_{k, p}, u_{k+1, p}), (u_{k, p}, u_{k, p+1}) \space | \space k \geq 0, p \geq 0, p + k + 1 \leq n)$.

Puis il écrit que le nombre de chemins allant de $u_{0, 0}$ à $u_{k, p}$ est égal à $\mathcal C^{p}_{p + k}$.

Je ne comprend pas ce résultat, quelqu’un peut-il m’expliquer?

Je pense que c’est tout. Merci.

Si je considère le graphe $G$ tel que $V(G) = \{A, B\}$ et $E(G) = \{ \{A, A\}, \{A, B\} \}$ alors $\deg(A) = 3$. Pourquoi pas $2$? On compte la boucle deux fois?

Ce genre de trucs ça dépend pas mal des définitions. A priori, là, effectivement, on compte deux fois les boucles dans le degré (c’est logique en un certain sens, on est d’accord ? même si le choix inverse se justifie aussi).

Ici je ne vois pas comment cela conclut dans le cas sans boucle.

Avec boucle, il est écrit que c’est un raisonnement similaire. Déjà il faut que je comprenne le cas sans boucle pour comprendre celui-ci.

C’est quoi son hypothèse de récurrence ?

$V(G) = \{u_{k, p} \space | \space k \geq 0, p \geq 0, p + k \leq 0 \}$ et $A(G) = \{(u_{k, p}, u_{k+1, p}), (u_{k, p}, u_{k, p+1}) \space | \space k \geq 0, p \geq 0, p + k + 1 \leq n)$.

Puis il écrit que le nombre de chemins allant de $u_{0, 0}$ à $u_{k, p}$ est égal à $\mathcal C^{p}_{p + k}$.

Je ne comprend pas ce résultat, quelqu’un peut-il m’expliquer?

J’espère que t’as essayé de faire un dessin. Comment tu décrirais un chemin dans ce graphe en termes graphiques ?

Il n’y pas une erreur ici ? Si $p + k \leq 0$ avec $p$ et $k$ positifs… ça donne juste $p = k = 0$.

@Lucas-84, son hypothèse de récurrence c’est juste : pour $\mid V(G) \mid = n$, le nombre de sommets de degré impair est pair.

@Ozmox : On suppose la propriété vraie au rang $n$. Considérons un graphe $V(G)$ tels que $\mid V(G) \mid =n$, et notons $B$ l’ensembles des sommets de degré impair et $C$ l’ensemble des sommets de degré pair. On a par HP : $\mid B \mid = z \in 2 \mathbb{N}$. Rajoutons maintenant un sommet $A$ à notre graphe $V(G)$. Et notons $\deg(A) = p +k$ avec $p$ le nombre d’arrêtes reliant un sommet dans $B$ et $k$ le nombre d’arrêtes reliant un sommet dans $C$. On a donc maintenant $ \mid B \mid \geq z-p+k$ (car on ne sait pas si $A$ est dedans ou non). Si $p+k$ est impair alors : $\mid B \mid = z-p+k+1$ qui est pair et on a finit. Si $p+k$ est pair alors on a : $\mid B \mid = z-p+k$, qui est pair et on a finit. $\square$

Si je considère le graphe $G$ tel que $V(G) = \{A, B\}$ et $E(G) = \{ \{A, A\}, \{A, B\} \}$ alors $\deg(A) = 3$. Pourquoi pas $2$? On compte la boucle deux fois?

Ce genre de trucs ça dépend pas mal des définitions. A priori, là, effectivement, on compte deux fois les boucles dans le degré (c’est logique en un certain sens, on est d’accord ? même si le choix inverse se justifie aussi).

Pour moi c’est le seul choix sensé, je ne vois pas comment on pourrait justifier l’inverse… Mais je ne connais pas bien la théorie des graphes donc peut-être qu’il y a des situations dans lesquelles il est mieux de prendre l’autre définition ?

Est-ce que c’est logique de mettre un 2 sur la diagonale de la matrice d’adjacence ? C’est pas clair pour moi que c’est mieux dans tous les cas (et puis ça rend la définition du degré moche).

M’enfin je pense évidemment que la vraie réponse c’est « les graphes n’ont jamais de boucles ». Et si par malheur ils en ont, elles finissent aux oubliettes du « sans perte de généralité » ligne 1.

PS : cette démonstration par récurrence est vraiment horrible, je trouve.

Ah bon ? Au moins elle a le mérite d’être clair

Haha désolé, c’était pas dirigé contre ta démonstration en particulier ; c’est que juste j’aime pas les récurrences du genre parce qu’on (je ?) comprend rien à ce qui se passe. Par rapport à juste dire que la somme des degrés c’est deux fois le nombre d’arêtes, on perd en visibilité (bon même si y a probablement une récurrence cachée là-dedans si on veut tout écrire proprement). M’enfin je suppose que c’est ce qu’Ozmox appelle l’argument de double comptage, donc c’était juste une remarque comme ça.

Oui je suis d’accord, disons qu’avec la récurrence on comprend le raisonnement mais ça donne rarement l’intuition (comme ici). Et oui, double comptage c’est en utilisant cet argument (à moins d’avoir mal compris)

@Lucas84

Est-ce que c’est logique de mettre un 2 sur la diagonale de la matrice d’adjacence ? C’est pas clair pour moi que c’est mieux dans tous les cas (et puis ça rend la définition du degré moche).

Ah oui en effet, il faut mettre des $1$ si on veut considérer qu’il n’y a qu’une manière de parcourir une boucle (au contraire des autres arêtes pour lesquelles il y a deux manières de les parcourir).

Ça me fait penser aux formes quadratiques, il faut mettre un coefficient $1/2$ hors de la diagonale. Au début je doutais qu’il y ait vraiment un lien mais apparemment la forme quadratique correspondante est étudiée. Il doit bien y avoir une raison de pourquoi c’est la matrice d’adjacence avec des $2$ qui est étudiée (spectral graph theory)… ?

Pour la mocheté de la définition, ça dépend de la définition de « graphe non orienté » qu’on prend. Si on voit une arête comme un « sous-multiensemble » (ou multisous-ensemble ??) de cardinal $2$ de l’ensemble $V$ des nœuds, ie comme une fonction $e : V→ℕ$ telle que $∑_{v∈V} e(v) = 2$, alors la définition de la fonction degré $d : V→ℕ$ devient que c’est la somme de toutes les arêtes. La preuve du lemme des poignées de main devient le calcul

Si on veut plutôt définir un graphe non orienté comme un graphe orienté muni d’une involution des arcs inversant la source et le but, alors cette notion de degré coïncide avec celle de degré sortant (ou entrant) dans le cas où on fait correspondre deux arcs à une boucle (allant dans un sens et l’autre). On peut aussi ne faire correspondre qu’un arc à une boucle. Les deux correspondent à des adjonctions suivant ce qu’on prend comme catégories.

Et d’un point de vue « graphe topologique » (CW-complexe de dimension $1$), le degré d’un nœud devient une donnée locale (on peut connaître le degré d’un nœud à partir de n’importe lequel de ses voisinages, sans forcément savoir que les deux « bouts » qui partent font partie d’une même arête).

M’enfin je pense évidemment que la vraie réponse c’est « les graphes n’ont jamais de boucles ». Et si par malheur ils en ont, elles finissent aux oubliettes du « sans perte de généralité » ligne 1.

Ça dépend probablement de ce qu’on veut en faire… j’ai commencé à réfléchir à ce qu’il vaut mieux prendre comme définitions et c’est un peu sans intérêt dans le vide comme ça sans savoir où on va, c’est peine perdue sans connaître les théorèmes intéressants. Ça me rappelle une citation : « One will not get anywhere in graph theory by sitting in an armchair and trying to understand graphs better. » (source). Comme j’avais en tête des multigraphes plutôt que des graphes simples, ça me semblait plus naturel d’autoriser les boucles.

PS : cette démonstration par récurrence est vraiment horrible, je trouve.

Tout à fait d’accord. À part si c’est pour donner un exemple de démonstration par récurrence, je n’en vois pas l’utilité.

Du coup, je n’ai pas compris les deux dernières lignes de ta démonstration InaDeepThink.

Sinon, quelqu’un peut-il m’expliquer la démonstration de mon prof?

Je comprends que ce n’est pas la meilleure, mais soit, j’aimerai tout de même comprendre.

Sinon j’ai représenté le graphe non-orienté de mon cours, et ça donne un triangle de Pascal… J’aurai dû y réfléchir avant.

Je ne comprends pas la preuve de InaDeepThink non plus… Je pense qu’il y a un problème entre la notation pour le $B$ de $G\setminus \{A\}$ et le $B$ de $G$ tout entier, il faudrait deux notations différentes. Ça m’a aussi perturbé d’avoir noté $A$, $B$ et $C$ des objets de types différents.
On pourrait aussi faire une rédaction en faisant une récurrence sur les sommets et les arcs. L’ajout d’un sommet ne pose pas de problème (lorsqu’on l’ajoute, il est de degré pair). Et pour l’ajout d’un arc, on inverse la parité de deux sommets, donc la somme modulo $2$ des parités ne change pas. (Un peu comme si on montrait que $2n$ est pair par récurrence.)

Décidément j’ai des problèmes de rédactions. Le problème c’est que je ne comprends pas ce que vous ne comprenez pas.

$B$ représente en général l’ensemble des sommets de degré pair d’un graphe $G$. C’est vrai que j’aurai du mettre $B_n$ et $B_{n+1}$… Aussi c’est vrai que la notation peut porter à confusion, mais bon pour une démonstration de trois lignes…

J’ai relu et ok en fait c’était clair pour la notation $B$. C’est juste que j’ai lu un peu trop rapidement en lisant surtout les formules. J’ai regardé l’inégalité et ne l’ai pas comprise… Désolé. Par contre j’aurais juste dit au moins que $-p+k$ est congru à $p+k$ modulo $2$ pour justifier la fin (car c’est fondamentalement le fait que ça a le même effet d’enlever un nœud impair ou d’en ajouter un qui donne la propriété, autrement dit que $-1 \equiv 1 \mod 2$).

Pour le coup ça c’est moi, en l’écrivant je me suis aussi dit que c’était un peu rapide.

Au début on considère notre graphe $G$, et on note $B$ l’ensemble des sommets de degré pair de $G$ et $C$ l’ensemble des sommets de degré impair de $G$. Ensuite on essaie de savoir comment le cardinal de $B$ varie si on rajoute un sommet au graphe. Si on note $A$ le nouveau sommet qu’on rajoute et que l’on note $\deg(A) = p+k$, avec $p$ le nombre d’arrête reliant un sommet dans $B$ et $k$ le nombre d’arrêtes reliant un sommet dans $C$. Puisqu’on peut relier deux sommets entre eux que par une seule arrête, alors cela veut dire que dans $B$, le degré de $p$ sommets vont augmenter de $1$ et donc vont changer de parité. Ainsi après ça on a : $\mid B \mid = z-p$. Or après, dans $C$ on a $k$ sommet qui vont changer aussi de parité ($k$ sommet vont se voir relier à $A$), ainsi ces sommets sont alors de degré pair. Donc, ces $k$ sommets sont maintenant dans $B$. Ainsi on a bien : $\mid B \mid \geq z-p+k$ (c’est une inégalité car on ne sait pas encore si $A$ est dans $B$ ou non).

@blo yhg : Tu soulèves effectivement pas mal de points intéressants, la difficulté étant que la « théorie des graphes » c’est vachement large. Je reconnais que pour moi, les graphes c’est surtout un outil, et du coup on crée pas des singularités comme des boucles dans la vie réelle.

Ah ouais j’avoue, j’y avais pas pensé mais en fait c’est le triangle de Pascal qui a subi la transformation géométrique $(x,y)\mapsto (x,x+y)$. Bien vu !

À vrai dire, je m’attendais plus à un argument combinatoire de type « l’espace des chemins de $(0,0)$ à $(k,p)$ vit dans l’espace des choix (bas, droite) partant de $(0,0)$ de longueur $k+p$, et finir en $(k,p)$ est équivalent à faire $k$ choix « aller vers le droite » (en termes pompeux, exhiber une bijection avec les parties de $\{0,1\}^{p+k}$ de cardinal $k$).