第10章 順序集合と束 駆け足で読む『離散数学〜コンピュータサイエンスの基礎数学』
本駆け足シリーズの全体の目次はこちら
- 順序とは
- 順序 order は、普通の順序 usual order が備えた特徴を抽象化したものである
- 順序がある関係というのは、ある２つの要素があって、それらの間に上下関係が定まっていることを言う。これは次のようにまとめられる
- 反射的である。
- 反対称的である。
かつ
ならば
である
- 推移的である。
ならば
である
- 反射的である。
- 数の大小関係記号を援用して a< b
と表す
- 順序である関係には、逆順序 inverse order が存在する
- 集合の要素のペアには、順序によって、上下関係が定められたペアと定められていないペアとがある。上下関係が定められたペア同士は比較可能である comparable と言われ、上下関係が定められていないペアは比較不可能である noncomparable と言われる。
- 半順序
- 順序のこと。より厳しい決まりを要求する「全順序」と区別して「半順序」と言う。
- ある集合の要素について、そのいずれの間に、どっちが上でどっちが下かが決まっているもの
- 集合の要素を点で、前後関係を有向辺で現した、有向グラフで言えば、「全点が連結」であり、「点のペアについて、片方から到達可能ならば、もう片方からは到達不能である。ただし、相互に到達不可能な点のペアがあってもよい。
- この状態のグラフは、
の要素で見た場合、対角要素以外の要素について、その対称要素のうち、どちらかはゼロである
- 順序のこと。より厳しい決まりを要求する「全順序」と区別して「半順序」と言う。
- 全順序 totally ordered、線形順序 linearly ordered、鎖 chain とも言う
- 半順序で、かつ、相互にどちらからも到達できない点のペアはない。これは１本線でかつ、一端からもう一端への一方通行のもの
- この状態のグラフは、
- 順序に関する用語・定義
- 順序においては、ある要素はある要素に対して、直下にある immediate predecessor 、直上にある immediate successor なる特別な関係が存在する。aがbの直下にあり、bがaの直上にあるとき、
と表し、a<x<bなるxが存在しないことを意味する</li>
- すべての
がわかれば、順序関係のすべてがわかる
- 順序を図に表すとき、それを図式 diagram と呼ぶ。
- これは、
なる関係を→として要素を点として表したグラフである。
- このグラフには有向閉路はない
- このグラフにおいて、(半)順序であるとき、すべての点を上下軸に適当に配置することによって、より上の要素は図式において、上に配置することができる。
- これは、
- 一致数え上げ consistent enumeration
- 順序の上下関係を守りながら、すべての要素に序数を割り当てることができる。
- 図式を描いたとき、比較不可能な要素の位置は、どちらが図式上で高い位置におくべきかは定まっていないが、図式にすると、便宜的に上下関係が発生する。この図式に与えられた高さに応じて、序数を割り当てることができることからも、順序のある集合には、一致数え上げが取れることがわかる。また、一致数え上げが一通りとは限らないこともわかる。
- 極大 maximal と極小 minimal
- 順序のある要素集合において、直上に要素を持たない要素を極大という。直下に要素を持たない要素を極小という。この場合、極大が１つしかないことになる。
- 上限 supremum と下限 infimum
- 順序のある要素集合を考える。この要素集合の部分集合にも順序があるが、この部分集合の中のある要素が、その部分集合のすべての要素に対して上にあるとき、その要素を、部分集合の上限という。この場合、その部分集合には極大が１つしかないことになる。
- 同じく、順序のある要素集合を考える。この要素集合の部分集合にも順序があるが、この部分集合の中のある要素が、その部分集合のすべての要素に対して下にあるとき、その要素を、部分集合の下限という。この場合、その部分集合には極小が１つしかないことになる。
- 順序においては、ある要素はある要素に対して、直下にある immediate predecessor 、直上にある immediate successor なる特別な関係が存在する。aがbの直下にあり、bがaの直上にあるとき、
- 順序の特別なもの、束 lattice
- 任意の要素対について、上限と下限が存在する順序集合を束という。
- 束には、２つの関係、交わり meet と結び joinとがあり、それぞれ
、
で表す。このような束を
と書く。
- ある集合のべき集合 power setは束である
- 束の基本的特徴
- 交換律。
、
- 結合律。
、
- 吸収律。
、
- 交換律。
- その他の束の特徴
- べき等律。
、
- べき等律。
- 部分束
- 束の部分集合で、束であるものを部分束という。
- 順序集合はいくつかの束の和集合である(たぶん)
- 束の同形 isomorphic
- 束
、
があったとき、
と
の要素の間にある１対１対応
がとれて、それが
かつ、
を満足するとする。このような
- 束
- 束の全要素に上限と下限があるとき、それぞれ上界 upper bound
、下界 lower bound
と言い、束が有界であるという(多分)
- 分配束 distributive lattice
- 分配律を満たす束を言う。ただし、分配律は
、とその双対である、
を満たすことである
- 分配律を満たさない束は非分配的 nondistributive
- 分配律を満たす束を言う。ただし、分配律は
- 結び既約 join irreducible と原子 atom、余分のない要素 irredundant の結び表現
- 相補束
- 順序、順序付け、その順序インデックス数などに絡んで、順序に関する諸定義が存在するが、本駆け足シリーズのテキストでは触れられていないので、ひとまず割愛することとする。Wikipediaの関連記事は次に示すものなど
- プログラミング問題
- 半順序の判定->CheckPartialOrder
- 全順序の判定->CheckOrder
- 一致数え上げの作成->CreateConsistEnum
- 最大公約数・最小公倍数のプログラムについては、上限と下限を見つける、ということの課題なのだと思うが、順序を取り入れてこの問題をプログラムにすることのメリットを生かす方法がわからないので保留する。
public class Order {
Graph orderGraph;
int[] maxiMinimal;//maximal=1,minimal=-1,otherwise=0
int[] ConsistEnum;//consistent Enumeration
public static void main(String[] args) {
//Set
//int[] n= {1,2,3,4,5,6};
//int[][] e= {{1,2},{2,3},{4,5},{5,6},{2,5},{1,6},{3,4}};
int[][] e= {{1,2},{1,3},{4,5},{5,6},{2,5},{1,7},{1,8},{7,8},{8,9},{8,5}};
Graph ordG = new Graph(e);
Graph.CreateDataGraph(ordG);
Order ord = new Order(ordG);
int partialCheck = CheckPartialOrder(ord);
System.out.println("Parital order ? " + partialCheck);
int orderCheck = CheckOrder(ord);
System.out.println("Order ? " + orderCheck);
MaximalMinimal(ord);
CreateConsistEnum(ord);
PrintOrder(ord,"\t","\n");
}
public Order(Graph g_){
orderGraph=g_;
}
public static int CheckOrder(Order ord){
int ret=Graph.Connection(ord.orderGraph);
if(ret == 0){
return ret;
}
for(int i=0;i<ord.orderGraph.numV;i++){
for(int j=i+1;j<ord.orderGraph.numV;j++){
int[] ilist = {i,j};
int[] jlist = {j,i};
int ei = Tensor.ChoiceElem(ord.orderGraph.connectionMatrixDirected, ilist);
int ej = Tensor.ChoiceElem(ord.orderGraph.connectionMatrixDirected, jlist);
if(ord.orderGraph.connectionMatrixDirected.data[ei]>0 &&
ord.orderGraph.connectionMatrixDirected.data[ej]>0){
ret = 0;
return ret;
}
if(ord.orderGraph.connectionMatrixDirected.data[ei]==0 &&
ord.orderGraph.connectionMatrixDirected.data[ej]==0){
ret = 0;
return ret;
}
}
}
return ret;
}
public static int CheckPartialOrder(Order ord){
int ret=Graph.Connection(ord.orderGraph);
if(ret == 0){
return ret;
}
//int ret=1;
//Graph should be connected as undirected graph
//any pair of vertexs shoud have one way or no way.
//Only one vertex should have way to all the vertexs
//int supnum=0;
for(int i=0;i<ord.orderGraph.numV;i++){
//int cango=0;
for(int j=0;j<ord.orderGraph.numV;j++){
if(i!=j){
int[] ilist = {i,j};
int[] jlist = {j,i};
int ei = Tensor.ChoiceElem(ord.orderGraph.connectionMatrixDirected, ilist);
int ej = Tensor.ChoiceElem(ord.orderGraph.connectionMatrixDirected, jlist);
if(ord.orderGraph.connectionMatrixDirected.data[ei]>0 &&
ord.orderGraph.connectionMatrixDirected.data[ej]>0){
ret = 0;
return ret;
}
}
}
}
return ret;
}
public static void MaximalMinimal(Order ord){
int[] ret=new int[ord.orderGraph.numV];
for(int i=0;i<ret.length;i++){
ret[i]=0;//maximal=1,minimal=-1,otherwise=0
int togo=0;
int tocome=0;
for(int j=0;j<ret.length;j++){
if(i!=j){
int[] ilist = {i,j};
int[] jlist = {j,i};
int ei = Tensor.ChoiceElem(ord.orderGraph.connectionMatrixDirected, ilist);
int ej = Tensor.ChoiceElem(ord.orderGraph.connectionMatrixDirected, jlist);
if(ord.orderGraph.connectionMatrixDirected.data[ei]>0){
togo++;
}
if(ord.orderGraph.connectionMatrixDirected.data[ej]>0){
tocome++;
}
}
}
if(togo==0){
ret[i]=1;
}
if(tocome==0){
ret[i]=-1;
}
}
ord.maxiMinimal = ret;
}
public static void PrintOrder(Order ord,String sep1,String sep2){
String st = StringOrder(ord,sep1,sep2);
System.out.println(st);
}
public static String StringOrder(Order ord,String sep1,String sep2){
String ret="";
ret += Graph.StringGraph(ord.orderGraph,sep1,sep2);
String maxi ="";
String mini ="";
for(int i=0;i<ord.maxiMinimal.length;i++){
if(ord.maxiMinimal[i]==1){
maxi+=ord.orderGraph.vertex[i][0]+sep1;
}
if(ord.maxiMinimal[i]==-1){
mini+=ord.orderGraph.vertex[i][0]+sep1;
}
}
ret += "Maximal:"+sep2 + maxi + sep2;
ret += "Minimal"+sep2 + mini +sep2;
ret += "ConsistEnumeration" + sep2;
String s = "";
for(int k=0;k<ord.ConsistEnum.length;k++){
s += ord.ConsistEnum[k] + " ";
}
for(int i=0;i<ord.ConsistEnum.length;i++){
ret+=ord.orderGraph.vertex[ord.ConsistEnum[i]][0] + sep1;
}
return ret;
}
public static void CreateConsistEnum(Order ord){
ord.ConsistEnum = new int[ord.orderGraph.numV];
for(int i=0;i<ord.ConsistEnum.length;i++){
ord.ConsistEnum[i]=i;
}
for(int i=0;i<ord.ConsistEnum.length;i++){
for(int j=0;j<ord.ConsistEnum.length;j++){
if(i!=j){
int[] ilist = {i,j};
int[] jlist = {j,i};
int ei = Tensor.ChoiceElem(ord.orderGraph.connectionMatrixDirected, ilist);
int ej = Tensor.ChoiceElem(ord.orderGraph.connectionMatrixDirected, jlist);
if(ord.orderGraph.connectionMatrixDirected.data[ei]>0){
System.out.println("i j " + ord.orderGraph.vertex[i][0] + " " + ord.orderGraph.vertex[j][0]);
if(ord.ConsistEnum[i]<ord.ConsistEnum[j]){
int tmm = ord.ConsistEnum[i];
ord.ConsistEnum[i]=ord.ConsistEnum[j];
ord.ConsistEnum[j]=tmm;
}
}
if(ord.orderGraph.connectionMatrixDirected.data[ej]>0){
if(ord.ConsistEnum[i]>ord.ConsistEnum[j]){
int tmm = ord.ConsistEnum[i];
ord.ConsistEnum[i]=ord.ConsistEnum[j];
ord.ConsistEnum[j]=tmm;
}
}
}
}
}
int[] tmp = new int[ord.ConsistEnum.length];
for(int i=0;i<tmp.length;i++){
tmp[i]=ord.ConsistEnum[i];
}
ord.ConsistEnum=new int[tmp.length];
for(int i=0;i<tmp.length;i++){
ord.ConsistEnum[tmp[i]]=i;
}
}
}
