置换群与有向图

本文由置换f的有向图G_f的定义得到了G_f的一个本质特征,从而得到了置换的轮换分解定理.定义了无向图(X,T),利用图论中“树”的结论,给出了置换的对换分解的一般定理.我们知道所有的n阶置换组成一个群S_n,称为n次对称群.设f∈S_n,可按下法定义一个有向图G:它的顶点集X={1,2…,n}的对于x,y∈X,当且仅当y=f(x)时,有从x指向y的弧(x,y).G_f称为置换的有向图.由于f是置换,所以在每一顶点i处,恰有一条出弧和入弧.反之任何一个n阶有向图G,如果每个顶点都恰有一条出弧和入弧也一定表示一个置换f:f(x)=y的充要条件是有x指向y的弧(x,y).