Graphe dirigé, DAG, graphe non dirigé
Un graphe dirigé $G=(V,E)$ a pour arêtes des couples $(x,y)$. Il est acyclique (DAG) s’il ne contient aucun cycle orienté. Dans un graphe non dirigé, les arêtes sont symétriques.
Notification
Mode actif : Poset
Dimension : –
Aucun dessin. Utilisez le bouton « Importer » pour charger un poset ou un graphe (JSON ou dictionnaire Python) dont les sommets sont des tuples de coordonnées, ou une liste de points dont on calculera l'enveloppe convexe.
• Projection : le dessin est projeté orthogonalement sur les axes x₁ (horizontal) et x₂ (vertical) ; la vue reste centrée sur le barycentre des points.
• Tourner (plans x₁ – xᵢ et x₂ – xᵢ) : glisser horizontalement / verticalement (souris ou doigt), ou deux doigts sur le pavé tactile. L'axe xᵢ se choisit dans la barre du haut ou avec les flèches ↑ ↓.
• Tourner la projection (plan x₁ – x₂) : maintenir Alt et glisser, ou tourner deux doigts sur le trackpad / l'écran tactile.
• Zoom : maintenir Espace et glisser vers le haut / le bas ; ou Ctrl/Cmd + molette, pincement, molette de souris.
• Déplacer la vue : Maj + glisser, ou glisser avec le clic droit.
• Nom d'un sommet : cliquer dessus (il affiche sa valeur et ses coordonnées actuelles) ; cliquer à nouveau, ou dans le vide, pour le masquer.
• Couleurs : après avoir activé leur affichage dans les options, double-cliquer sur un sommet ou une arête pour changer sa couleur.
• Annuler / rétablir : Ctrl/Cmd + Z ; Ctrl/Cmd + Maj + Z ou Ctrl/Cmd + Y.
• Calculs exacts : les coordonnées (entières, décimales ou rationnelles 1/3) sont lues exactement ; sous-espace affine, enveloppe convexe et faces s'appuient toujours sur les valeurs d'origine du premier dessin (même après des projections ou des restrictions à une face successives), jamais sur les flottants du dessin.
• Sélection multiple : Ctrl / Cmd + clic sur des sommets et des arêtes ; un double-clic sur l'un d'eux change la couleur de toute la sélection.
• Intersection de demi-espaces : à l'import d'une liste de vecteurs, choisir « intersection des demi-espaces v·x ≤ 1 » ; les arêtes infinies s'estompent. Le menu « Faces… » en donne les faces et le treillis des faces.
• Export JSON : la dernière projection utilisée est enregistrée (attributs « projection » et « view ») et retrouvée à la réimportation.
• Accès direct : ajouter #poly à l'adresse de la page ouvre directement cette vue.
Collez un dictionnaire Python ou un JSON (même format que l'éditeur) dont les sommets sont des tuples de coordonnées, par exemple (1, 0, 2). Un tuple plus court est complété par des zéros. Les coordonnées peuvent être entières, décimales ou rationnelles (1/3) : elles sont lues exactement. En JSON, un sommet peut porter un autre nom (« value ») s'il a un attribut « coordinates ». Une liste de points ([(0,0,0), (1,0,0), …]) est remplacée par son enveloppe convexe. Le format est détecté automatiquement.
Le calcul est exact (rationnels) et se fait toujours sur les coordonnées d'origine du tout premier dessin, avant toute rotation ou projection : il n'est donc pas affecté par les erreurs d'arrondi. Les coordonnées flottantes ne servent qu'au dessin (la projection est orthogonale, donc sans déformation).
• Mode Tracer : Glisser d'une zone vide pour créer 2 sommets reliés, ou entre deux sommets pour relier.
• Modifier l'aspect : Double-cliquer sur une sélection de sommets/arêtes pour éditer leurs options graphiques.
• Redimensionner : Maintenir Espace, cliquer sur un élément déjà sélectionné (le curseur devient une croix fléchée) et glisser pour changer la taille de la sélection par rapport à son barycentre, en conservant son orientation mais pas ses proportions.
• Pivoter : Maintenir Alt (ou Option), cliquer sur un élément déjà sélectionné et glisser pour faire pivoter la sélection autour de son barycentre, en conservant ses proportions.
• Agrandir/Rétrécir : Maintenir Maj, cliquer sur un élément déjà sélectionné et glisser pour agrandir/rétrécir la sélection autour de son barycentre, en conservant son orientation et ses proportions.
• Annuler : Bouton Annuler ou Ctrl + Z. Rétablir : Cmd/Ctrl + Maj + Z (ou Ctrl + Y).
• Copier / Couper / Coller : Ctrl + C, Ctrl + X, Ctrl + V sur une sélection de sommets/arêtes (⌘ Cmd ou Ctrl). En mode poset, ajouter Alt (Option) à Copier, Couper ou Suppr. conserve l'ordre induit (pas seulement les relations de couverture). Ctrl + A pour tout sélectionner.
• Zone de sélection : Glisser avec le Clic Droit, ou maintenir Espace, Maj ou Alt + Clic Gauche et glisser depuis une zone vide (ou en dehors de la sélection).
• Ajouter / retirer : Ajouter Ctrl pendant le glissement (ou le clic) pour ajouter à la sélection les éléments non sélectionnés de la zone et retirer ceux qui l'étaient déjà. En mode Déplacer, Ctrl + glisser depuis une zone vide fonctionne aussi.
• Intervalle (poset) : Sélectionner deux sommets comparables puis appuyer sur I ; ou sommet x sélectionné, maintenir I et cliquer sur y : sélectionne l\'intervalle [x, y].
• Filtre / idéal (poset) : Sélectionner un ensemble de sommets puis appuyer sur D (idéal engendré) ou U (filtre engendré) ; ou maintenir D / U et cliquer sur un sommet.
• Couper une arête : Maintenir M et cliquer sur une arête x→y (ou x—y) crée un sommet z au milieu : x→z→y.
• Boucles : Un sommet ne peut pas être relié à lui-même ; les boucles présentes dans un import sont supprimées.
• Polytopes : bouton cube à droite du titre (ou ajouter #poly à l'adresse de la page). Son propre guide d'utilisation y est disponible.
• Page Dessin : bouton crayon à gauche du titre (ou ajouter #draw à l'adresse de la page) ; le bouton « Ouvrir ce dessin dans la page Dessin » du menu Exporter y transmet le dessin actuel.
• Masquer le texte d'un sommet : Options graphiques › « Afficher le texte » (le texte est conservé).
Les actions grisées ne sont pas disponibles pour le type de structure actuel (voir le menu Options).
Collez un JSON (export précédent : structure, positions et styles) ou un dictionnaire d'adjacence Python. Le format est détecté automatiquement.
Plusieurs sommets peuvent porter le même nom : ils restent distingués en interne.
Code SVG minimal représentant le graphe/poset actuel.
Outil actif : Sélectionner
Graphes, posets, treillis, polytopes
Un graphe est un ensemble de sommets muni d’arêtes ; elles sont orientées dans un graphe dirigé.
Un graphe dirigé $G=(V,E)$ a pour arêtes des couples $(x,y)$. Il est acyclique (DAG) s’il ne contient aucun cycle orienté. Dans un graphe non dirigé, les arêtes sont symétriques.
La fermeture transitive de $G$ relie $x$ à $y$ dès qu’il existe un chemin de $x$ vers $y$. Pour un DAG, c’est la relation d’ordre engendrée.
Contracter chaque composante fortement connexe en un seul sommet transforme un graphe dirigé en DAG, donc en poset après fermeture transitive.
Les arêtes d’un graphe dirigé se répartissent en arêtes surjectives et injectives selon leur comportement vis-à-vis de l’ordre de forçage (voir le menu « Propriétés »). À compléter.
Teste si les arêtes surjectives et injectives forment un système de factorisation ; la factorisation colorie les arêtes en rouge, bleu et vert. À compléter.
L’ordre de forçage compare les arêtes d’un graphe ; le graphe est congruence-uniforme si cet ordre vérifie la propriété d’uniformité. À compléter.
Les paires orthogonales maximales d’un graphe forment un treillis (menu « Propriétés »). À compléter.
Un ensemble partiellement ordonné (poset) est un ensemble muni d’une relation réflexive, antisymétrique et transitive.
On dit que $y$ couvre $x$ si $x<y$ et s’il n’existe pas de $z$ avec $x<z<y$. Le diagramme de Hasse dessine uniquement ces relations (réduction transitive).
Pour $x\le y$, l’intervalle $[x,y]=\{z : x\le z\le y\}$. Dans l’éditeur : sélectionner deux sommets puis appuyer sur I.
Une chaîne est une partie totalement ordonnée, une antichaîne une partie d’éléments deux à deux incomparables. Le menu « Propriétés » dénombre intervalles, intervalles linéaires, chaînes et chaînes maximales.
Un idéal (ordre inférieur) est une partie $I$ telle que $y\in I$ et $x\le y$ impliquent $x\in I$ ; un filtre est la notion duale. Dans l’éditeur : D + clic sur un sommet pour son idéal, U + clic pour son filtre.
La complétion d’un poset est le plus petit treillis qui le contient ; ses éléments sont étiquetés par des antichaînes ou par des idéaux (menu « Propriétés »). À compléter.
Un treillis est un poset dans lequel toute paire d’éléments admet une borne supérieure ($\vee$) et une borne inférieure ($\wedge$).
Un poset fini est un treillis s’il possède un minimum et si toute paire d’éléments a un join (ou, de façon équivalente, un meet).
Un élément est join-irréductible s’il couvre exactement un élément, meet-irréductible s’il est couvert par exactement un élément. Ils engendrent le treillis (menu « Propriétés »).
À compléter : définition des join- et meet-dissecteurs et lien avec les irréductibles.
À compléter : construction de ces objets associés à un treillis, calculés depuis le menu « Propriétés ».
Un treillis est gradué s’il existe une fonction de rang compatible avec la relation de couverture.
Un polytope est l’enveloppe convexe d’un nombre fini de points de $\mathbb{R}^d$.
L’enveloppe convexe d’un ensemble de points est le plus petit convexe qui les contient ; ses sommets sont les points extrémaux. La page « Polytopes » la calcule de façon exacte.
La dimension d’un polytope est celle du plus petit sous-espace affine qui le contient ; on peut s’y projeter orthogonalement.
Une face est l’intersection du polytope avec un hyperplan d’appui. Sommets, arêtes, ..., facettes sont les faces de dimension $0,1,\dots,d-1$ ; leur treillis est le treillis des faces.