第２章 関係 駆け足で読む『離散数学〜コンピュータサイエンスの基礎数学』

本駆け足シリーズの全体の目次はこちら

• 関係 relation

集合の要素は順序関係なし。関係を扱う第２章では順序対 ordered pairs (a,b) を扱う。aは第１成分、bは第２成分

• 直積集合 product, cartesian product

集合Aと集合Bの要素が作るすべての順序対の集合をAとBの直積と呼ぶ。。AとAの直積はとも表す。実数集合の直積集合は２次元座標平面上の点の集合であり、をデカルト平面 cartesian planeと呼ぶ。直積は交換律が成り立たない。結合律は成立つ

• 関係

２項関係 binary relation。AからBへの２項関係RとはAとBの直積集合の部分集合である。であるとき、とはR-関係 R-related にあると言い、と表す。R-関係にないときはと表す。一般的に用いられる２項関係のtex表現はこちら。

関係Rとがの部分集合ならば、RはA上 R is on A であるという。Rは順序対の集合であるが、そのすべての順序対の第１成分の集合を定義域 domain、第２成分の集合を値域 range と言う。

A上の関係のひとつ、相当性 equality は同等関係とも呼ばれ、のことであり、このような関係をで表す。ももの部分集合であるから、A上の関係であり、それぞれ全体関係 universal relation、空関係 empty relation と呼ばれる

• 関係の幾何学表現

関係は、部分集合であるので、普遍集合の要素のうち、関係Rの要素が区別して表示することによって、関係Rを図示することができる。このように関係Rを図示したものをグラフ graph と呼ぶ。実数平面上に２軸x,yを置き、なる関数のグラフを描くことは、このような関係のグラフ表現の１型である。以下に代表的な関係の幾何学表現 ４法を挙げる

• 座標図 cordinate diagram
  
  • AとBとの要素を水平・垂直２軸に対応させて描いた図
• 行列 matrix of the relation
  
  • Aの要素を行にBの要素を列にした２次元配列で、の場合に1を、それ以外に0を与えたもの
• 矢線図 arrow diagram
  
  • A,Bを重なりのない２円で表し、それぞれの中にそれぞれの要素を列挙し、の成りたつ場合にからに矢印を記したもの
• 有向グラフ directed graph
  
  • における関係の表現方法で、Aの要素を書き並べ、である場合に、からへの矢印を記したもの
• 逆関係

なる関係をRの逆 inverse という

である。また、Rを表す行列の転置行列である

• 関係の合成

RはAからBへの関係、SはBからCへの関係とする。今AからCへの関係はあるが存在して かつとして表され、をRとSの合成 composition と呼ぶ

RとSを表す行列,からとしての関係行列表現は得られる

• 関係の性質

RをA上の関係とする

反射的 reflexive, がAの各要素に成り立つとき

対称的 symmetric, ならばが成り立つとき

反対称的 anti-symmetric, かつならばであるとき

推移的 trasitive, かつならばであるとき

これらの関係の基礎的な性質を用いて、いくつかの特徴的な関係に名称がある

同値関係 equivalent 反射的、対称的かつ推移的である関係

半順序関係 partial ordering relation 反射的、反対称的かつ推移的である関係

A上の同値関係Rは、Aの要素のうち、ある要素を基準として同値関係にあるものとそうでないものとに分類する性質がある。たとえば、平面上の直線は、その中の1本を選びそれと並行な関係(同値関係)にある直線とそうでない直線とに分類できる

• 分割

Sを任意の空でない集合としたときにSを互いに重複しない、空でない部分集合(族)へわけたとき、をSの分割 partition と呼ぶ

このようなとき、Sの各要素はのいずれかに属し、は互いに素である

分割の各部分集合は細胞 cell と呼ばれる

• 同値関係と分割

A上の同値関係Rがあって、Aの要素aを含み、互いに関係Rで結ばれる要素の集合をAの同値類 equivalence class と呼び、と書く。である

関係RはAを分割する。分割された同値類の集合をRによるAの商と呼び、と表す。RによるAの商は互いに素であり、RによるAのすべての商の和はAに一致する

• 半順序関係 partial ordering relation

代表例を示すと、実数の大小関係は半順序関係である。

• n項関係

集合Aにおいて、A上の関係Rについて、の部分集合として取り扱ってきたが、A上の関係Rをの部分集合において扱うと、n項関係となる

• プログラミング問題
  
  • 整数集合における関係Rの定義域、値域を表示するプログラムを作成->PrintDomain,PrintRange
  • 合成関数を書き出すプログラムを作成->CompositRelation
  • Rの関数としての特性を判断し書き出すプログラムを作成->CharRelation
  • Rの行列表現を書き出すプログラムを作成->CreateMatrix, PrintMatrix
  • Equivalentな関係について同値類を書き出すプログラムを作成->EquivClass, PrintEquivClass

public class Relation {

	/*

	 * relation is int[][]=r on int[]=S

	 * int[*][0] is for the first element of relation

	 * and int[*][1] for the second element

	 */

	public static void main(String[] args) {

		String sep = ",";//separator for print-out

		String sep2 = "\t";

		String sep3 = "\n";

		//r test samples 

		//int[][] r ={{1,1},{1,2},{1,3},{2,2},{2,3},{4,4}};

		//int[][] r ={{1,1},{2,1},{2,2},{3,4},{3,3},{4,3},{4,4}};

		//int[][] r ={{1,4},{2,3},{4,3},{2,4},{3,1},{3,2}};

		//int[][] r ={{2,1},{1,3},{2,3},{4,4}};

		int[][] r ={{1,1},{2,2},{2,4},{3,3},{4,2},{4,4}};

		int[] S = {};

		S=AddElem(S,r);

		

		PrintS(S,sep2);

		System.out.println("r");

		PrintDomain(r,sep2);

		PrintRange(r,sep2);

		

		

		int[][] comprr2 = CompositRelation(r,r);

		System.out.println("r^2");

		PrintR(comprr2,sep,sep2);

		int reflexive = CharRelation(S,r,"r");

		int symmetric = CharRelation(S,r,"s");

		int transitive = CharRelation(S,r,"t");

		int equivalent = CharRelation(S,r,"e");

		System.out.println("Characterization of r in S");

		int antisymmetric = CharRelation(S,r,"a");

		System.out.println("ref " + reflexive +

				" sym " + symmetric +

				" trans " + transitive +

				" anti-sym " + antisymmetric +

				" equivalent " + equivalent);

		int[][] rmat = CreateMatrix(r,S);

		PrintMatrix(rmat,sep2,sep3);

		

		//In case of equivalent relation

		if(equivalent ==1){

			int[][] equivClass = EquivClass(S,r);

			PrintEquivClass(equivClass,sep2,sep3);

		}

	}

	/*

	 * Add elem of r to S

	 */

	public static int[] AddElem(int[] s, int[][] r){

		int[] tmp = new int[s.length+r.length*2];

		int[] ret;

		int counter=0;

		for(int i=0;i<s.length;i++){

			tmp[counter]=s[i];

			counter++;

		}

		for(int i=0;i<r.length;i++){

			boolean zero = false;

			boolean one = false;

			for(int j=0;j<tmp.length;j++){

				if(r[i][0]==tmp[j]){

					zero=true;

				}

				if(r[i][1]==tmp[j]){

					one = true;

				}

				if(zero && one){

					break;

				}

			}

			if(!zero){

				tmp[counter]=r[i][0];

				counter++;

			}

			if(!one){

				if(r[i][0]!=r[i][1]){

					tmp[counter]=r[i][1];

					counter++;

				}

			}

		}

		ret = new int[counter];

		for(int i=0;i<counter;i++){

			ret[i]=tmp[i];

		}

		return ret;

	}

	/*

	 * Print element of S

	 */

	public static void PrintS(int[] s,String sep){

		String ret = StringS(s,sep);

		System.out.println("S " + ret);

	}

	/*

	 * Print element of S

	 */

	public static void PrintR(int[][] r,String sep,String sep2){

		String ret = StringR(r,sep,sep2);

		System.out.println("R " + ret);

	}

	public static String StringS(int[] s, String sep){

		String ret = "";

		for(int i=0;i<s.length;i++){

			ret += s[i] + sep;

		}

		return ret;

	}

	public static String StringR(int[][] r, String sep,String sep2){

		String ret = "";

		for(int i=0;i<r.length;i++){

			ret += r[i][0] + sep + r[i][1] + sep2;

		}

		return ret;

	}

	/*

	 * Print out domain and range of binary relation R 

	 */

	public static String StringDomain(int[][] r, String sep){

		String ret = "";

		int[] tmp = new int[r.length];

		int counter = 0;

		

		for(int i=0;i<r.length;i++){

			boolean notok=true;

			for(int j=0;j<counter;j++){

				if(tmp[j]==r[i][0]){

					notok=false;

					break;

				}

			}

			if(notok){

				tmp[counter]=r[i][0];

				counter++;

				ret += r[i][0] +sep;

			}

			

			

		}

		return ret;

	}

	public static String StringRange(int[][] r, String sep){

		String ret = "";

		int[] tmp = new int[r.length];

		int counter = 0;

		for(int i=0;i<r.length;i++){

			boolean notok=true;

			for(int j=0;j<counter;j++){

				if(tmp[j]==r[i][1]){

					notok=false;

					break;

				}

			}

			if(notok){

				tmp[counter]=r[i][1];

				counter++;

				ret += r[i][1] +sep;

			}

			

			

		}

		return ret;

	}

	public static void PrintDomain(int[][] r,String sep){

		String ret="";

		ret += StringDomain(r,sep);

		System.out.println("domain " + ret);

	}

	public static void PrintRange(int[][] r,String sep){

		String ret="";

		ret += StringRange(r,sep);

		System.out.println("range " + ret);

	}

	/*

	 * Return r^r as int[][]

	 */

	public static int[][] CompositRelation(int[][] r1, int[][] r2){

		int[][] ret;

		

		String[] tmppair = new String[r1.length*r2.length];

		int counter=0;

		for(int i=0;i<r1.length;i++){

			for(int j=0;j<r2.length;j++){

				if(r1[i][1]==r2[j][0]){

					boolean skip =false;

					String tmp ="" + r1[i][0] + "\t" + r2[j][1];

					for(int k=0;k<counter;k++){

						if(tmp.equals(tmppair[k])){

							skip = true;

							break;

						}

					}

					if(!skip){

						tmppair[counter]=tmp;

						counter++;

					}

				}

				

				

			}

		}

		ret = new int[counter][2];

		for(int i=0;i<ret.length;i++){

			String[] separate = tmppair[i].split("\t");

			ret[i][0]=Integer.parseInt(separate[0]);

			ret[i][1]=Integer.parseInt(separate[1]);

		}

		return ret;

		

	}

	/*

	 * Return 1 if yes, -1 

	 * if no whether r is reflexive, symmetric, transitive, or anti-symmetric

	 * arg[1]:r-reflexive,s-symmetric,t-transitive,a-anti-symmetric, e-equivalence

	 */

	public static int CharRelation(int[] s, int[][] r, String type){

		int ret=-1;

		if(type.equals("r")){

			int counter=0;

			

			for(int i=0;i<r.length;i++){

				if(r[i][0]==r[i][1]){

					counter++;

					

				}

				

			}

			if(counter==s.length){

				ret=1;

			}

			

		}else if(type.equals("s")){

			

			for(int i=0;i<r.length;i++){

				boolean notok = true;

				for(int j=0;j<r.length;j++){

					

					if(r[i][1]==r[j][0]){

						if(r[j][1]==r[i][0]){

							notok = false;

						}

					}

					

				}

				if(notok){

					return ret;

				}

			}

			ret = 1;

			

		}else if(type.equals("t")){

			ret=-1;

			int[][] r2 = CompositRelation(r,r);

			

			int check=0;

			for(int i=0;i<r2.length;i++){

				boolean notok =true;

				for(int j=0;j<r.length;j++){

					if(r2[i][0]==r[j][0] && 

							r2[i][1]==r[j][1]){

						check ++;

						notok = false;

						break;

					}

					

				}

				if(notok){

					return ret;

				}

			}

			if(check==r2.length){

				ret=1;

			}

		}else if(type.equals("a")){

			int[][] r2 = CompositRelation(r,r);

			

			boolean nosame = true;

			int check=0;//fake value

			for(int i=0;i<r2.length;i++){

				

				if(r2[i][0]==r2[i][1]){

					for(int j=0;j<r.length;j++){

						if(r[j][0]==r2[i][0]){

							if(r[j][0]!=r[j][1]){

								return ret;

							}

						}

					}

					

				}

			}

			ret =1;

		}else if(type.equals("e")){

			int ref = CharRelation(s,r,"r");

			int sym = CharRelation(s,r,"s");

			int tra = CharRelation(s,r,"t");

			if(ref==1 && sym==1 && tra==1){

				ret=1;

			}

			

		}

		

		

		return ret;

	}

	/*

	 * Return relation matrix

	 *

	 */

	public static int[][] CreateMatrix(int[][] r,int[] s){

		int[][] ret = new int[s.length][s.length];

		for(int i=0;i<s.length;i++){

			for(int j=0;j<s.length;j++){

				ret[i][j]=0;

			}

		}

		for(int i=0;i<r.length;i++){

			ret[r[i][0]-1][r[i][1]-1]=1;

		}

		

		return ret;

	}

	public static String StringMatrix(int[][] r,String sep,String sep2){

		String ret="";

		for(int i=0;i<r.length;i++){

			for(int j=0;j<r[0].length;j++){

				ret += r[i][j] + sep;

			}

			ret += sep2;

		}

		return ret;

	}

	public static void PrintMatrix(int[][] r, String sep, String sep2){

		String ret = StringMatrix(r,sep,sep2);

		System.out.println("Matrix\n" + ret);

	}

	/*

	 * Class elements of S into equivalent classes by r 

	 *

	 */

	public static int[][] EquivClass(int[] s, int[][] r){

		int[][] ret = new int[s.length][0];

		for(int i=0;i<s.length;i++){

			int[] tmp = new int[s.length];

			tmp[0]=s[i];

			int counter=1;

			for(int j=0;j<r.length;j++){

				if(r[j][0]==s[i]){

					boolean flag1=true;

					for(int k=0;k<counter;k++){
						if(tmp[k]==r[j][1]){

							flag1 = false;

							break;

						}

					}

					if(flag1){

						tmp[counter]=r[j][1];

						counter++;

					}

				}

			}

			ret[i] = new int[2+counter];//1st-s[i],2nd-number of elements,3rd&after element

			ret[i][0]=s[i];

			ret[i][1]=counter;

			for(int j=0;j<counter;j++){

				ret[i][j+2]=tmp[j];

			}

		}

		

		

		return ret;

	}

	

	public static String StringEquivClass(int[][] eq, String sep1,String sep2){

		String ret ="";

		for(int i=0;i<eq.length;i++){

			for(int j=0;j<eq[i].length;j++){

				ret += eq[i][j] + sep1;

			}

			ret += sep2;

		}

		return ret;

	}

	public static void PrintEquivClass(int[][] eq, String sep1, String sep2){

		String ret = StringEquivClass(eq,sep1,sep2);

		System.out.println("Equivalent Classes\nElemid\tNo.classElem\telemInClass...\n" + ret);

		

	}

	

}

• 第２章終了