👤

FRstudy.me vous connecte avec des experts prêts à répondre à vos questions. Notre communauté fournit des réponses précises et rapides pour vous aider à comprendre et résoudre n'importe quel problème.

Bonjour, pourriez-vous m'aider à répondre à la question suivante : Ce graphe peut-il être un graphe d'intervalle ?
Merci d'avance !


Bonjour Pourriezvous Maider À Répondre À La Question Suivante Ce Graphe Peutil Être Un Graphe Dintervalle Merci Davance class=

Sagot :

Bonjour,

dans de lointains souvenirs, je dirais non :

Il ne doit pas exister de cycle avec plus de 3 arêtes et sans raccourci(s).

Or, ABDHECA est un cycle de 6 arêtes mais il y a des raccourcis : par exp on peut aller de C à B en passant par F.

Ce qui doit suffire à affirmer qu'il ne peut pas s'agir d'un graphe d'intervalles.