Graphe d'intervalle propre

Graphe d'intervalle propre
Un graphe d'intervalle qui n'est pas un graphe d'intervalle propre.
Un graphe d'intervalle propre.

Un graphe d'intervalle propre est un graphe d'intervalle possédant une représentation d'intervalles dans laquelle aucun intervalle n'est inclus dans l'autre.

Propriétés

Une serre

Un graphe d'intervalle propre est nécessairement un graphe sans serre.

Démonstration

Soit G un graphe possédant une serre comme graphe induit. On appelle A,B,C,D les quatre sommets de la serre d'intervalles respectives Ia = [a1;a2],Ib = [b1;b2],Ic = [c1;c2] et Id = [d1;d2] tels que le sommet D soit celui relié aux trois autres et que a_1\le b_1\le c_1.

Comme la serre est un graphe induit, A, B et C ne sont pas voisins dans G. On a donc a_1 \le a_2 \le b_1 \le b_2 \le c_1 \le c_2.

D est voisin de A et C donc I_a \cap I_d \not = \empty et I_c \cap I_d \not = \empty d'où d_1 \le a_2 et c_1 \le d_2. On a donc d_1 \le a_2 \le b_1 \le b2 \le c_1 \le d_2, d'où I_b \sub I_d. G n'est donc pas un graphe d'intervalle propre.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe d'intervalle propre de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Graphe d'intervalle — Sept intervalles de la droite réelle et le graphe d intervalle associé En théorie des graphes, un graphe d intervalle est le graphe d intersection (en) d …   Wikipédia en Français

  • Base propre — Valeur propre, vecteur propre et espace propre Fig. 1. Cette application linéaire déforme la statue de David. Les vecteurs bleus ont pour images les vecteurs verts. Ils gardent la même direction, ce sont des vecteurs propres. La valeur propre… …   Wikipédia en Français

  • Espace propre — Valeur propre, vecteur propre et espace propre Fig. 1. Cette application linéaire déforme la statue de David. Les vecteurs bleus ont pour images les vecteurs verts. Ils gardent la même direction, ce sont des vecteurs propres. La valeur propre… …   Wikipédia en Français

  • Sous-espace propre — Valeur propre, vecteur propre et espace propre Fig. 1. Cette application linéaire déforme la statue de David. Les vecteurs bleus ont pour images les vecteurs verts. Ils gardent la même direction, ce sont des vecteurs propres. La valeur propre… …   Wikipédia en Français

  • Valeur propre, vecteur propre et espace propre — Fig. 1. A étire le vecteur x sans changer sa direction. x est un vecteur propre pour A, pour la valeur propre λ. En mathématiques, et plus particulièrement en algèbre linéaire, le concept de vecteur propre est une notion algébrique s appliquant à …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • SYSTÈMES DYNAMIQUES DIFFÉRENTIABLES — Sans doute née avec le mémoire que Poincaré écrivit en 1881 «sur les courbes définies par des équations différentielles», où l’étude quantitative (analytique) locale des équations différentielles dans le champ complexe est remplacée par leur… …   Encyclopédie Universelle

  • Sous-différentiel — En mathématiques, et plus précisément en analyse convexe, le sous différentiel est un concept permettant de décrire la variation locale d une fonction convexe (à valeurs réelles donc) non nécessairement différentiable dans un sens classique,… …   Wikipédia en Français

  • Application Réciproque — Pour les articles homonymes, voir Réciproque (homonymie). En mathématiques, une application réciproque est en des termes simples une fonction qui « fait exactement l inverse de ce que fait une application donnée ». L application… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”