In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation (up to permutation symmetry) if it is prime with respect to the modular decomposition.
If is any permutation of the numbers from to , then one may define a permutation graph from in which there are vertices , and in which there is an edge for any two indices for which appears before in . That is, two indices and determine an edge in the permutation graph exactly when they determine an inversion in the permutation.
Given a permutation , one may also determine a set of line segments with endpoints and , such that . The endpoints of these segments lie on the two parallel lines and , and two segments have a non-empty intersection if and only if they correspond to an inversion in the permutation. Thus, the permutation graph of coincides with the intersection graph of the segments. For every two parallel lines, and every finite set of line segments with endpoints on both lines, the intersection graph of the segments is a permutation graph; in the case that the segment endpoints are all distinct, a permutation for which it is the permutation graph may be given by numbering the segments on one of the two lines in consecutive order, and reading off these numbers in the order that the segment endpoints appear on the other line.
Permutation graphs have several other equivalent characterizations:
A graph is a permutation graph if and only if is a circle graph that admits an equator, i.e., an additional chord that intersects every other chord.
A graph is a permutation graph if and only if both and its complement are comparability graphs.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
vignette|upright=2| Construction d'un graphe trivialement parfait à partir d'intervalles imbriqués et de la relation d'accessibilité dans un arbre. En théorie des graphes, un graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S.
vignette|240x240px| Un graphe scindé, partitionné en une clique et un ensemble stable. En théorie des graphes, un graphe scindé ou graphe séparé (en anglais : split graph) est un graphe dont les sommets peuvent être partitionnés deux parties : une clique et un ensemble stable. Les graphes scindés ont été étudiés pour la première fois par Földes et Marteau en 1977, et introduit indépendamment par Tyshkevich et Tchernyak en 1979 .
En théorie des graphes, un graphe d'intersection est un graphe représentant les intersections d'une famille d'ensembles. Plus précisément, pour une famille d'ensembles finie donnée, on associe à chaque ensemble un sommet, et deux sommets sont reliés par une arête si les ensembles ont une intersection non nulle. Beaucoup de familles de graphe sont définies par l'intersection d'ensembles géométriques, par exemple des sphères dans le plan, ou des intervalles sur une droite.
Natural language processing has experienced significant improvements with the development of Transformer-based models, which employ self-attention mechanism and pre-training strategies. However, these models still present several obstacles. A notable issue ...
EPFL2023
, , ,
Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph dis ...
ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2022
In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. An important property common for both of them is well-quasi-orderability, implying, in a non-constructive ...