Inscription / Connexion Nouveau Sujet
Niveau LicenceMaths 2e/3e a
Partager :

Digraphe

Posté par
dugdug13
01-04-21 à 15:33

Bonjour à tous,

1) Montrer que tout digraphe symétrique sans boucle admet au moins un noyau.
2)  On suppose que N1 et N2 sont deux noyaux distincts d'un même digraphe G. Montrer qu'il existe un sommet s dans N1 qui n'est pas dans N2. En déduire que G possède un arc (s,t) où t est un sommet de N2 qui n'est pas dans N1.
3) Montrer que si G est un graphe sans circuit élémentaire de longueur paire alors G a au plus un noyau.

Voici les questions de mon devoir d'algorithme des graphes. J'ai réussi à montrer dans la première question qu'un digraphe symétrique admettait au moins un noyau, mais je n'arrive pas à montrer qu'un digraphie symétrique "sans boucle" l'est...
Pour la question deux j'ai montré par l'absurde qu'il existait un sommet s dans N1 qui n'est pas dans N2. Cependant pour l'arc (s,t) je ne vois pas comment faire car normalement entre les sommets de deux noyaux il ne doit pas y avoir d'arrête...
Pour la dernière question je ne vois pas par où commencer...
Sauriez-vous m'aider ?
Merci beaucoup !



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !