设V=<S,*>,其中S={a,b,c},*的运算表如表9-3所示。
分别对以上每种情况讨论*运算的可交换性,幂等性,是否含有幺元以及S中的元素是否含有逆元。
合成数(composite number)法,是消除图算法岐义性的一种通用方法。首先,在顶点的标识之间约定某一次序。比如,顶点标识为整数或字符时,可直接以整数或字符为序;对于字符串等标识,不妨按字典序排列。于是,若边(v,u)权重为w,则对应的合成数取作向量:(w,min(v,u),max(v,u))。如此,任何两条边总能明确地依照字典序比较出大小。
试在6.11.5节Prim算法和6.12.2节Dijkstra算法中引入这一方法,以消除其中的歧义性。
设A={x|x∈R∧x≠0,1}。在A上定义6个函数如下:
V=<S,°>,其中S={f1,f2,...,f6},°为函数的复合.。
(1)给出V的运算表。
(2)说明V的幺元和所有可逆元素的逆元: