Bonjour j'ai un exercice que j'ai du mal à comprendre

Soit un graphe non orienté G dont les degrés sont tous au moins 2.

Je dois montrer qu'il existe un graphe connexe possédant la même suite de degré que G.

Mais je ne voit pas comment faire.

Merci.

Déjà, pour s'aider à réfléchir, on va écrire les définitions propre à ton exercice.


Graphe (là je troll)

https://fr.wikipedia.org/wiki/Lexique_de_la_théorie_des_graphes

On voit rapidement que : le degré est le nombre d'arrête passant par un sommet.
On est pas dans un hypergraphe.

un graphe connexe est un graphe où il existe toujours un chemin reliant 2 couple de sommet.

Ensuite un exemple

Soit G : (J'en prend un non connexe pour le fun)
A{B,C}
B{A,B,C}
C{A,B}
D{D,E}
E{D,E}
suite de degré : 2,3,2,2,2

Je construit G' connexe
Je relis les point deux à deux.

suite de degré pour le moment : {A,B,C,D,E} => (2,2,2,2,2)
Et je relis B avec lui même {A,B,C,D,E} => 2,3,2,2,2

Est-ce bien cela le problème à prouver ?

Essaye d'en construire quelques-uns , tu verra qu'il y a une manière de faire qui fonctionne bien ;) 

Mais G est un graphe non orienté on ne peut pas relié un sommet à lui-même.

Est-ce que il faut utiliser le fait que chaque composante connexe de G contient au moins un cycle??

-
Edité par camilla8 15 novembre 2017 à 17:54:49

Exact !
une arête doit être définit par deux sommets distincts !

pour reprendre un exemple non connexe :

A -> B,E
B -> A,E
C -> F,D
D -> C,F,G
E -> A,B
F -> C,D,G
G -> F,D

Je les place par ordre de degré
DGABCEF
3322222 <- degré restant à tracer

Si on considère qu'au départ tous les point sont isolé ( sans arête pas trop dur)
Je relis le nombre d'arête à D au point ayant le plus de degré par ordre décroissant.

Je viens de créer un sous-ensemble connexe (whoohoo)
Une question intéressante est de savoir, est-il possible de rajouter de nouveaux points dans le graphe en gardant le même idée.
(tri par ordre de degré, ajout des arêtes pour les sommets de degré les plus élevé), etc..
Mais en gardant toujours un ensemble connexe.

Remarque, à chaque tour, on pose le bon nombre d'arête pour un sommet, on pourra l'ignorer pour la suite ;) 

Si on considère qu'au départ tous les point sont isolé ( sans arête pas trop dur)
Je relis le nombre d'arête à D au point ayant le plus de degré par ordre décroissant.

Je viens de créer un sous-ensemble connexe (whoohoo)

-
Edité par camilla8 15 novembre 2017 à 19:55:33

Pour réfléchir au problème, j'ai commencé par me faire plein d'exemple, et qu'avec des graphes non connexe (sinon c'est triviale)
Le seul cas intéressant est le cas où G est non connexe.

Mon premier reflexe est de bidouiller puis de voir si avec une seul manière de faire, je peux "résoudre" le problème.
Et on peut sans trop de difficulté trouver l'algorithme.

I Créer un ensemble connexe sans dépasser les degré de chaque sommets.
II) Relier les points de l'ensemble connexe crée pour terminer la "résolution"

Pour expliquer rapidement l'algo :

Etape I.
Tant que des points ne sont pas utilisé :
Je prend un point pas encore utilisé ayant le plus grand degré restant.
Je le relis si possible à un unique point déjà utilisé (de plus grand degré restant) et le reste à des points non utilisés (par ordre décroissant de degré restant).

Etape 2
Tous les points ont été utilisé.
Je prend un pont de plus grand degré et je le relis avec les point par ordre décroissant de degré.
Jusqu'à ce que il n'y ait plus rien à faire (tout à 0)
AI FINI

Dans mon exemple au dessus
-Je relis D à E,F,G
-je relis A à C,F
-Je relis B à F,G
J'ai un ensemble connexe
-Je relis E à F

Terminé, j'ai crée un graphe G' ayant la même suite de degré que G

Mais pourquoi suis-je certain de toujours trouver une solution ?

Astuce : si je fais la somme du "reste à faire" c'est à dire la somme des degré manquante, cette somme DOIT être pair.
En effet, Si j'ajoute un point de degré N, alors je luis ajoute N voisins. La somme du reste à faire diminue de 2N.

Astuce 2
La graphe minimum possible pour G est avec 3 points par ensemble connexe, chaque sommets ayant chacun 2 arêtes (minimum selon les contraintes sur G)
Et il y a un nombre pair d'arêtes.
Je rajoute Un nouveau points (à au minimum deux autre points), j'ajoute 1 degré par arête rajouter à mon souveau sommet ... et à chaque point relié.
La somme des degrés reste pair.

Cette démonstration n'est pas complète, il faut Encore montrer que j'arrive toujours à terminer.

Par exemple en montrant que si le plus grand reste à faire est toujours < au nombre de sommet avec un reste à faire, alors il est toujours possible de terminer.

Exemple (5,5,0,3,3,2,4,0,0,0,0,0), max reste à faire = 5, nombre de sommet avec RAF = 6 alors je peux terminer
Mais sinon (5,5,0,3,3,0,4) est impossible

Par exemple en montrant que l'algorithme préserve toujours cette contrainte. et réduit le nombre de point.

-
Edité par neuneutrinos 16 novembre 2017 à 15:05:45