图与网络 定义 一个图(Graph ) G是由一个非空有限集合V(G)和V(G)中某些元素的无序对集合A(G)构成的二元组，记为图G=(V(G)，A(G)). 其中V(G) 称为图G的结点集，V(G)中的每一个元素称为该图的一个结点或顶点； A(G)称为图G的边集，A(G)中的每一个元素称为该图的一条边.

Presentation on theme: "图与网络 定义 一个图(Graph ) G是由一个非空有限集合V(G)和V(G)中某些元素的无序对集合A(G)构成的二元组，记为图G=(V(G)，A(G)). 其中V(G) 称为图G的结点集，V(G)中的每一个元素称为该图的一个结点或顶点； A(G)称为图G的边集，A(G)中的每一个元素称为该图的一条边."— Presentation transcript:

1 图与网络 定义 一个图(Graph ) G是由一个非空有限集合V(G)和V(G)中某些元素的无序对集合A(G)构成的二元组，记为图G=(V(G)，A(G)). 其中V(G) 称为图G的结点集，V(G)中的每一个元素称为该图的一个结点或顶点； A(G)称为图G的边集，A(G)中的每一个元素称为该图的一条边. 记号V(G)和A(G)简记为V和A，而记图G=（V，A）. 有向图:对图G中的每条边赋予一个方向. (有序对; 边称弧） 赋权图: 对图G中的每条边赋予一个或多个实数，得到的图称为或网络(Network).

2 例 有向图G=(V，A)，顶点集V= 边集A= 边

3 基本概念 图的阶(Order) :顶点的个数. 顶点的度（Degree）:与顶点相连的边数. (出度,入度). 相邻点、相邻边、环、多重边.
简单图(Simple Graph): 没有环、且没有多重边的图. 链(chain)：由两两相邻的点及其相关联的边构成的点边序列. 如：v0 , e1 , v1 , … , vn－1,en , vn ； v0 , vn 分别称为链的起点和终点 . 路 (Path): 图的不包含重复顶点的链. 圈(Cycle): 起点和终点重合的路. 连通图(Connected Graph) ： 图中任意两点之间均至少有一 条路，否则称作不连通图。 树(tree): 无圈连通图称为树,无圈图称为森林.

4 图与网络中的几个重要问题 完全图(Complete Graph) ：
若图G的任意两个顶点间有且只有一条边相连，则称其为完全图. n阶完全图记为Kn. Kn的边的数量为 n(n-1)/2 子图(Subgraph): G=（V，A） 称为G的子图(Subgraph) 图的支撑子图 (又称生成子图): 包含G 的所有顶点的子图. 图与网络中的几个重要问题 最短路径问题 最小生成树问题 最小费用最大流问题

5 相识问题（拉姆齐问题）  在6人的聚会中，假设认识是相互的，则必可找出这样的3人，他们或者彼此均认识或者彼此均不认识 。请问这个结论正确吗？ 证明： 利用图的方法来描述该问题。将人看成顶点，两人彼此都认识用实线连，否则虚线。 请大家一起画图证明 问题转化为在一个6阶图中必存在实线三角形或虚线三角形。

6 任取一顶点，不妨υ1 不妨取υ1 υ2 、 υ1 υ3 、 υ1 υ4 实线 与υ1相连的边必然有： 实线条数不小于3或虚线条数不小于3 拉姆齐问题也可这样叙述： 6阶2色完全图中必含有3阶单色完全图。 考察υ2υ3、υ2υ4和υ3υ4 υ2υ3、υ2υ4和υ3υ4只能是虚线 ，否则得证 υ2 υ1 υ3 υ4 υ6 υ5 υ2 υ1 但这样三角形υ2υ3υ4的三边均为虚线 ， 得证。 υ3 υ4

7 其他类似可推出的结果 ： 命题1 任一6阶2色完全图中至少含有两个3阶单色完全图。 证明：前面证明必存在3阶单色完全图，不妨设υ1υ2υ3
命题1 任一6阶2色完全图中至少含有两个3阶单色完全图。 证明：前面证明必存在3阶单色完全图，不妨设υ1υ2υ3 为红色完全图 若υ4υ5υ6也是红色三角形，命题已得证 。反之， 至少一边与υ1υ2υ3的边异色，不妨设υ4υ5黑色 υ1υ4、υ2υ4、υ3υ4至少应有两条黑色，不妨设 υ1υ4 、υ2υ4 黑色 υ1υ5、υ2υ5、υ3υ5中至少有两条黑色、故υ1υ5 与υ2υ5中至少有一条是黑色 υ2 υ1 υ3 υ4 υ6 υ5 所以存在第二个3阶单色完全图。 直接推广：以上结论对于人数大于6人仍成立！

8 命题2 7阶2色完全图至少含有4个3阶单色安全图。 命题3 18阶2色完全图中必含有4阶单色完全图。 对拉姆齐问题的认识不能仅仅停留在本例的水平上。利用逻辑推理方法，实际上还可获得一大批结果。命题2和命题3的证明留给大家自己去完成。

9 最短路径问题 B A 设有一个半径为 r 的圆形湖，圆心为 O。A、 B 位于湖的两侧，AB连线过O，见图。
制下，问怎样的路径最近? A B O r

10 B A 将湖想象成凸出地面的木桩，在AB间拉一根软线，当线被拉紧时将得到最短路径。根据这样的想象，猜测可以如下得到最短路径：
过A作圆的切线切圆于E，过B作圆的切线切圆 于F。最短路径为由线 段AE、弧EF和线段FB连接而成的连续曲线（根据对称性，AE′，弧E′F′，F′B连接而成的连续曲线也是）。 E F E′ F′ A B O r

11 以上只是一种猜测，现在来证明这一猜测是正确的。为此，先介绍一下凸集与凸集的性质。
定义1（凸集）称集合 R为凸集，若x1、x2∈R及λ∈[0，1]，总有λx1+（1+λ）x2∈R。即若x1、x2∈R，则x1、x2的连线必整个地落 在R中。 定理1（分离定理）对平面中的凸 集R与R外的一点K，存在直线l ,l分离R与K，即R与K分别位于l 的两侧（注：对一般的凸集R与R外的一点K，则存在超平面分离R与K）,见图。 下面证明猜想 k l R

12 猜测证明如下： （方法一）显然， 由AE、EF、FB及AE′，E′F′，F′B围成的区域 R是一凸集。利用分离定理易证最短径不可能经过R外的点，若不然，设 Γ为最短路径，Γ过R外的一点M，则必存在直 线l分离M与R，由于路径Γ是连续曲线，由A沿Γ到M，必交l于M1，由M沿Γ到B又必交l于M2。这样，直线 段M1M2的长度必小于路 径M1MM2的长度，与Γ是A到B的最短路径矛盾，至此，我们已证明最短路径必在凸集R内。不妨设路径经湖的上方到达B点，则弧EF必在此最短路径之上，又直线段AE是由A至E的最短路径，直线FB是由F到B的最短路径，猜测得证。 A B O r E F E′ F′ M1 M2 M Γ l

13 若可行区域的边界是光滑曲面。则最短路径必由下列弧组成，它们或者是空间中的自然最短曲线，或者是可行区域的边界弧。而且，组成最短路径的各段弧在连接点处必定相切。
还可用微积分方法求弧长，根据计算证明满足限止条件的其他连续曲线必具有更大的长度；此外，本猜测也可用平面几何知识加以证明等。 根据猜测不难看出， 本例中的条件可以大大放松，可以不必 设AB过圆心，甚至可不必设湖是圆形的。例如对 下图，我们可断定由A至B的最短路径必 为l1与l2之一，其证明也不难类似给出。 A B l1 l2 D 到此为止，我们的研讨还只局限于平面之中，其实上述猜测可十分自然地推广到一般空间中去。1973年，J.W.Craggs证明了以上结果：

14 人、狼、羊、菜 渡河问题　 一个摆渡人F希望用一条小船把一只狼 W,一头羊 G 和一篮白菜 C 从一条河的左岸渡到右岸去,而船小只能容纳 F、W、G、C　中的两个,且决不能在无人看守的情况下,留下狼和羊在一起,羊和白菜在一起,应怎样渡河才能将狼、羊、白菜都运过去?　

15 将人、狼、羊、菜依次用一个四维向量表示: 当一物在左岸时,记相应的分量为1,否则记为0,
智力游戏􀃎 状态转移􀃎 模型􀃎 算法 将人、狼、羊、菜依次用一个四维向量表示: 当一物在左岸时,记相应的分量为1,否则记为0, 如A(1,0,1,0)表示人和羊在左岸,称为一个状态。 可取状态： (1,1,1,1)，(0,0,0,0)， (1,1,1,0)，(0,0,0,1)， (1,1,0,1)，(0,0,1,0)， (1,0,1,1)，(0,1,0,0)， (1,0,1,0)，(0,1,0,1)。 船： 可取运载B共4个 (1,1,0,0), (1,0,1,0), (1,0,0,1), (1,0,0,0)。

16 渡河过程：运算 可取状态向量与一个可取运载向量相加，相加时每一分量按二进制法则进行计算。例如 (1,1,1,1)+ (1,0,1,0)= (0,1,0,1) ?从(1,1,1,1)经过若干次运算化为(0,0,0,0) (1,1,0,0) (0,0,1,1) N (1,1,1,1) + (1,0,1,0) = (0,1,0,1) Y (1,0,0,1) (0,1,1,0) N (1,0,0,0) (0,1,1,1) N 第一次渡河 第二次渡河 (1,1,0,0) (1,0,1,1) U (0,1,0,1) + (1,0,1,0) = (1,1,1,1) R (1,0,0,1) (1,1,0,0) U (1,0,0,0) (1,1,0,1) Y 不合题意

17 计算机编程计算，从(1,1,1,1)转化为(0,0,0,0)，最后将整个运算过程“翻译”回去，就可以得到结果。
第三次渡河 (1, 1, 0, 0) (0, 0, 0, 1) Y (1, 1, 0, 1) + (1 , 0, 1, 0) = (0, 1, 1, 1) N (1, 0, 0, 1) (0, 1, 0, 0) Y (1, 0, 0, 0) (0, 1, 0, 1) R ……. 计算机编程计算，从(1,1,1,1)转化为(0,0,0,0)，最后将整个运算过程“翻译”回去，就可以得到结果。

18 编程步骤： 1）记录可取状态A和运载向量B; 2）将(1,1,1,1)与运载向量B相加（1-4循环）；
4）对可行的相加结果继续循环进行加法运算，直到出现(0,0,0,0)为止； 5）显示每次的运载向量和运算结果（翻译） 注意： 1）要用一个数组记录每一步可行的运算结果； 2）当偶数次的运算时要判断运算向量是否可取。

19

20 这一问题的状态和运算与前一问题有所不同，根据题意，状态应能反映出两岸的男女人数，过河也同 样要反映出性别
夫妻过河问题 这是一个古老的阿拉伯数学问题。有三对夫妻要过河，船最多可载两人，约束条件是根据阿拉伯法律，任一女子不得在其丈夫不场的情况下与其他男子在一起，问此时这三对夫妻能否过河？ 这一问题的状态和运算与前一问题有所不同，根据题意，状态应能反映出两岸的男女人数，过河也同 样要反映出性别

21 可如下定义： （i）可取状态： 用H和W分别表示此岸的男子和女子数，状态可用矢量 （H，W）表示，其中0≤H、W≤3。可取状态为（0,i），(i,i)，(3,i)，0≤i≤3。(i,i)为可取状态，这是因为总可以适当安排而使他们是 i对夫妻。 （ii）可取运算：过河方式可以是一对夫妻、两个男人或两个女人，当然也可以是一人过河。转移向量可取成 ((－1)im,(－1)in)，其中m、n可取0、1、2，但必须满足1≤m+n≤2。当j为奇数时表示过河。 当j为偶数时表示由对岸回来，运算规则同普通向量的加法。

22 问题归结为由状态 (3,3)经奇数次可取运算，即由可取状态到可取状态的转移，转化 为(0,0)的转移问题。和上题一样，我们既可以用计算机求解，也可以分析求解，此外，本题还可用作图方法来求解。
在H~W平面坐标中，以 “·”表示可取状态， 从A(3,3)经奇数次转移到 达O(0,0)。奇数次转移时向左或下移 动1-2格而落在一个可取状态上，偶数次转移时向右或上移 动1-2格而落在一个可取状态上。为了区分起见 ,用红箭线表示奇数次转移，用蓝箭线表示第偶数 次转移,下图给出了一种可实现的方案 。 故这三对夫妻是可以过河的 。假如按这样的方案过 河,共需经过十一次摆渡。 不难看出 ,在上述规则下,4对夫妻就无法过河了,读者可以自行证明之.类似可以讨论船每次可载三人的情况,其结果 是5对夫妻是可以过河的,而六对以上时就 无法过河了。 A(3,3) O(0,0) H W

23 商人们怎样安全过河 问题(智力游戏) 问题分析 类似问题: 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.
   3名商人    3名随从 河 小船(至多2人) 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货. 但是乘船渡河的方案由商人决定.商人们怎样才能安全过河? 问题分析 多步决策过程 决策~ 每一步(此岸到彼岸或彼岸到此岸)船上的人员 要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河

24 模型构成 多步决策问题 xk, yk=0,1,2,3; k=1,2, xk~第k次渡河前此岸的商人数 yk~第k次渡河前此岸的随从数
sk=(xk , yk)~过程的状态 S ~ 允许状态集合 S={(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2} uk, vk=0,1,2; k=1,2, uk~第k次渡船上的商人数 vk~第k次渡船上的随从数 dk=(uk , vk)~决策 D={(u , v) u+v=1, 2} ~允许决策集合 sk+1=sk dk +(-1)k ~状态转移律 多步决策问题 求dkD(k=1,2, n), 使skS按转移律 由s1=(3,3)到达sn+1=(0,0).

25 模型求解 评注和思考 S={(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2}
D={(u , v) u+v=1, 2} 模型求解 穷举法 ~ 编程上机 x y 3 2 1 图解法 s1 状态s=(x,y) ~ 16个格点 d1 允许状态S ~ 10个 点 允许决策D ~ 移动1或2格; k奇,左下移; k偶,右上移. d11 d1, d11给出安全渡河方案 评注和思考 sn+1 规格化方法, 易于推广 考虑4名商人各带一随从的情况

26 席位分配问题 在n个单位组成的团体中,经常涉及到一些代表名额分配问题,每个单位都希望自己的代表名额多一些,以便在委员会中能更好地反应自己单位的意图.试设计一种公平的代表名额分配方案. 

27 实例 系别 学生 比例 20席的分配 人数 （%） 比例 结果 甲 103 51.5 10.3 10 乙 63 31.5 6.3 6
三个系学生共200名（甲系100，乙系60，丙系40），代表会议共20席，按比例分配，三个系分别为10，6，4席。 实例 现因学生转系，三系人数为103, 63, 34, 问20席如何分配。 若增加为21席，又如何分配。 系别 学生 比例 席的分配 人数 （%） 比例 结果 甲 乙 丙 总和 系别 学生 比例 席的分配 人数 （%） 比例 结果 甲 乙 丙 总和 系别 学生 比例 席的分配 人数 （%） 比例 结果 甲 乙 丙 总和 21席的分配 比例 结果 21席的分配 比例 结果 10.815 6.615 3.570 对丙系公平吗 比例加惯例

28 “公平”分配方法 衡量公平分配的数量指标 当p1/n1= p2/n2 时，分配公平 若 p1/n1> p2/n2 ，对 不公平 A
人数 席位 A方 p n1 B方 p n2 当p1/n1= p2/n2 时，分配公平 若 p1/n1> p2/n2 ，对 不公平 A p1/n1– p2/n2 ~ 对A的绝对不公平度 p1=150, n1=10, p1/n1=15 p2=100, n2=10, p2/n2=10 p1=1050, n1=10, p1/n1=105 p2=1000, n2=10, p2/n2=100 p1/n1– p2/n2=5 p1/n1– p2/n2=5 虽二者的绝对不公平度相同 但后者对A的不公平程度已大大降低!

29 “公平”分配方法 将绝对度量改为相对度量 若 p1/n1> p2/n2 ，定义 ~ 对A的相对不公平度
公平分配方案应使 rA , rB 尽量小 类似地定义 rB(n1,n2) 将一次性的席位分配转化为动态的席位分配, 即 设A, B已分别有n1, n2 席，若增加1席，问应分给A, 还是B 不妨设分配开始时 p1/n1> p2/n2 ，即对A不公平

30 应讨论以下几种情况 初始 p1/n1> p2/n2 1）若 p1/(n1+1)≥p2/n2 ， 则这席应给 A 2）若 p1/(n1+1)< p2/n2 ， 应计算rB(n1+1, n2) 以及 rA(n1, n2+1) 问： p1/n1<p2/(n2+1) 是否会出现？ 否! 若rB(n1+1, n2) < rA(n1, n2+1), 则这席应给 A 若rB(n1+1, n2) >rA(n1, n2+1), 则这席应给 B

31 Q 值方法 当 rB(n1+1, n2) < rA(n1, n2+1), 该席给A 由rA, rB的定义 该席给A 否则, 该席给B
计算 ， 推广到m方分配席位 Q 值方法 该席给Q值最大的一方

32 三系用Q值方法重新分配 21个席位 按人数比例的整数部分已将19席分配完毕 用Q值方法分配第20席和第21席 第20席
甲系：p1=103, n1=10 乙系：p2= 63, n2= 6 丙系：p3= 34, n3= 3 用Q值方法分配第20席和第21席 第20席 Q1最大，第20席给甲系 同上 Q3最大，第21席给丙系 第21席 Q值方法分配结果 甲系11席，乙系6席，丙系4席 公平吗？

33 进一步的讨论 Q值方法比“比例加惯例”方法更公平吗？ 席位分配的理想化准则
已知: m方人数分别为 p1, p2,… , pm, 记总人数为 P= p1+p2+…+pm, 待分配的总席位为N。 设理想情况下m方分配的席位分别为n1,n2,… , nm (自然应有n1+n2+…+nm=N)， ni 应是 N和 p1, … , pm 的函数，即ni = ni (N, p1, … , pm ) 记qi=Npi /P, i=1,2, … , m, 若qi 均为整数，显然应有 ni=qi

34 记 [qi]– =floor(qi) ~ 向  qi方向取整； [qi]+ =ceil(qi) ~ 向  qi方向取整.
qi=Npi /P不全为整数时，ni 应满足的准则： 记 [qi]– =floor(qi) ~ 向  qi方向取整； [qi]+ =ceil(qi) ~ 向  qi方向取整. 1) [qi]–  ni  [qi]+ (i=1,2, … , m), 即ni 必取[qi]– , [qi]+ 之一 2) ni (N, p1, … , pm )  ni (N+1, p1, … , pm) (i=1,2, … , m) 即当总席位增加时， ni不应减少 “比例加惯例”方法满足 1），但不满足 2） Q值方法满足2）, 但不满足1）。令人遗憾！