Words near each other
 ・ Permoșeni River ・ Permsky ・ Permsky (inhabited locality) ・ Permsky District ・ Permsky Uyezd ・ Permutable prime ・ Permutation ・ Permutation (album) ・ Permutation (Bill Laswell album) ・ Permutation (disambiguation) ・ Permutation (music) ・ Permutation (policy debate) ・ Permutation automaton ・ Permutation box ・ Permutation City ・ Permutation graph ・ Permutation group ・ Permutation matrix ・ Permutation model ・ Permutation pattern ・ Permutation polynomial ・ Permutation representation (disambiguation) ・ Permutatude theory ・ Permutohedron ・ Permutotetraviridae ・ Permyak Salty Ears ・ Pern ・ PERN Przyjazn SA ・ Pern, Lot ・ Perna
 Dictionary Lists
 mini英和辞書
 mini和英辞書
 Webster 1913
 Latin-English
 FOLDOC
 Wikipedia English
 ウィキペディア
 翻訳と辞書　辞書検索 [ 開発暫定版 ]
 スポンサード リンク
 Permutation graph ： ウィキペディア英語版
Permutation graph

In mathematics, 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.〔, p.191.〕
==Definition and characterization==
If σ = (σ12, ..., σ''n'') is any permutation of the numbers from 1 to ''n'', then one may define a permutation graph from σ in which there are ''n'' vertices ''v''1, ''v''2, ..., ''v''''n'', and in which there is an edge ''v''''i''''v''''j'' for any two indices ''i'' and ''j'' for which ''i'' < ''j'' and σ''i'' > σ''j''. That is, two indices ''i'' and ''j'' 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 ''s''''i'' with endpoints (''i'',0) and (σ''i'',1). The endpoints of these segments lie on the two parallel lines ''y'' = 0 and ''y'' = 1, 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 ''G'' is a permutation graph if and only if ''G'' is a circle graph that admits an ''equator,'' i.e., an additional chord that intersects every other chord.〔, Proposition 4.7.1, p.57.〕
*A graph ''G'' is a permutation graph if and only if both ''G'' and its complement $\overline$ are comparability graphs.〔.〕
*A graph ''G'' is a permutation graph if and only if it is the comparability graph of a partially ordered set that has order dimension at most two.〔.〕
*If a graph ''G'' is a permutation graph, so is its complement. A permutation that represents the complement of ''G'' may be obtained by reversing the permutation representing ''G''.

ウィキペディアで「Permutation graph」の詳細全文を読む

スポンサード リンク
 翻訳と辞書 : 翻訳のためのインターネットリソース