Inscription / Connexion Nouveau Sujet
graphes, matrices...
Bonjour, je n'arrive pas à résoudre ce problème si quelqu'un pouvait m'aider...
On considère la matrice suivante:
1 0 0 1 1
0 1 1 0 0
1 0 0 1 1
0 0 1 0 1
1 0 0 0 0
1.Existe-il une chaîne eulérienne? un cyle eulérien? Justifier.
2. Donner un encadrement du nombre chromatique du graphe, puis déterminer sa valeur.
3. a) calculer M², puis M^3
b. existe-t-il des chaînes de longueur 2 entre les sommets 1 et 3?
Voilà si quelqu'un pouvait m'aider...merci 
Bonjour
La matrice que tu donnes semble associée à un graphe orienté. Est-ce bien le cas (vérifie ta matrice) ?
Pour un graphe classique, il suffit de dessiner un graphe correspondant à la matrice et d'appliquer les règles suivantes :
- Un graphe (connexe) admet une chaîne eulérienne ssi le nombre de sommets de degré impair est égal à 0 ou 2
- Un graphe (connexe) admet un cycle eulérien ssi tous ses sommets sont de degré pair.
Pour le nombre chromatique, tu extrais un sous-graphe complet, par exemple d'ordre p. Et tu sais alors que le nombre chromatique est compris entre p et r+1 où r est le plus grand degré des sommets.
Annuler
connectez vous