第1章 预备知识点.pptx

任课教师:陈六新chenliux@cqupt.edu.cn;1.图论问题的起源;七桥问题的分析;欧拉的结论;4.图的作用;5.图的广泛应用;可化为最短路问题的多阶段决策问题;6.基本的网络优化问题; 例如,在1978年,美国财政部的税务分析部门在对卡特尔税制改革做评估的过程中,就有一个100,000个约束以上，25,000,000个变量的问题,若用普通的线性规划求解,预计要花7个月的时间.他们利用网络分析的方法,将其分解成6个子问题,利用特殊的网络计算机程序,花了大约7个小时问题就得到了解决. ;第一部分 预备知识关系、函数、复杂度;二元关系和函数;1.2 集合的笛卡尔积与二元关系;一个有序n元组 (n≥3)是一个有序对，其中第一个元素是一个有序n-1元组，一个有序n元组记作x1, x2, …,xn,即 x1, x2, …,xn= x1, x2, …,xn-1, xn 例：空间直角坐标系中点的坐标 1, -1, 3 , 2, 4.5 , 0 等都是有序3元组。 n维空间中点的坐标或n维向量都是有序n元组。 形式上也可以把x看成有序1元组。; 设A，B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作A×B。 笛卡儿积的符号化表示为： A×B={x,y|x ∈A∧ y∈B} 例：若A={1,2}, B={a,b,c},则 A×B={1,a, 1,b, 1,c, 2,a, 2,b, 2,c} B×A={a,1, a,2, b,1, b,2, c,1, c,2} 易知：若|A|=m,(即集合A的元素的个数),|B|=n,则 | A×B|= |B×A|= m n; 有序对就是有顺序的数组，如x,y，x,y 的位置是确定的，不能随意改变。 注意：有序对a，b?b,a，以a,b为元素的集合{a,b}={b,a}；有序对(a,a)有意义，而集合{a,a}不成立。 笛卡儿积是一种集合合成的方法，把集合A，B合成集合A×B，规定A×B＝{x,y?x?A, y?B}。 由于有序对x,y中x,y的位置是确定的，因此A×B的记法也是确定的，不能写成B×A。 ?笛卡儿积也可以多个集合合成 A1×A2×…×An。 ?笛卡儿积的运算性质。;笛卡儿积的性质： 1、对任意集合A，根据定义有 A × φ = φ × A= φ 2、一般来说，笛卡儿积不满足交换律，即 A×B≠B×A （当A ≠ B B ≠ φ、A ≠ φ 时） 3、笛卡儿积不满足结合律，即 (A×B) ×C≠A×(B ×C) （当A≠φ∧B≠φ∧C≠φ时） 4、笛卡儿积运算对并和交运算满足分配律，即 A×(B∪C)= (A×B)∪(A × C) (B∪C) × A = (B×A)∪(C ×A) A×(B∩C)= (A×B) ∩(A × C) (B∩C) × A = (B×A) ∩(C ×A); 设A1,A2,…,An是集合(n≥2),它们的n阶笛卡儿积，记作A1×A2×…×An ，其中 A1×A2×…×An={x1,x2,…,xn |x1?A1∧x2?A2∧… ∧xn?An }。 当A1=A2=…=An=A时, 将其n阶笛卡儿积记作An，例，A= {a ,b} , 则： A3=A×A×A={a,b}×{a,b}×{a,b} ={a,a,a,a,a,b,a,b,a,a,b,b,b,a,a,b,a,b, b,b,a, b,b,b} 。;例：设集合 A={a,b},B={1,2,3},C={d}, 求A×B×C，B×A。 解： 先计算 A×B＝{a,1,a,2,a,3,b,1,b,2,b,3} A×B×C＝{a,1,a,2,a,3,b,1,b,2,b,3}×{d} ＝{a,1,d,a,2,d,a,3,d,b,1,d,b,2,d, b,3,d} B×A＝{1,a,2,a,3,a,1,b,2,b,3,b}?。; 例： 设集合A＝{1,2},求A×P(A)。 解： P(A)={?,{1},{2},{1,2}} A×P(A)＝{1,2}×{?,{1},}{2},{1,2} ={1,?,2,?,1,{1},2,{1},1,{2},2,{2}, 1,{1,2},2,{1,2}};?;二元关系是两种客体之