系统核与核度基本理论.ppt

报告内容 图论中的有关概念 系统核与核度的基本理论 系统核与核度的应用 2.1 系统核与核度概念的提出 仔细观察和思考现实世界中所存在的系统，无论是自然界还是现实社会，不难发现，几乎每一个系统，总有一个或者几个要素占有非常重要的位置，如果去掉他们或者破坏他们，这个系统在诸如结构、稳定性，甚至在生存性上都将受到很大的影响。 自然现象： (1) 小麦花的雄蕊和雌蕊 (2) 人的大脑(对人而言) (3) 一箱蜜蜂中的蜂王 社会现象： (1) 电话网络系统中的总机和分机 (2) 现实生活中的疑难问题 因此，无论是自然界，还是现实社会，只要是一个系统，必然存在 关键的主要因素，一旦这些主要因素遭到破坏，或者从系统中去掉 这些因素，那么这个系统的行为将会受到很大的影响。我们把系统 中起关键作用的主要元素叫做系统的核。 系统与网络图的转化 设X是一个系统，其元素为x1, x2,?,xp，如果在X中, xi与 xj之间有结构关系，就用xixj表示。由此可构造一个无向网络图G，其节点集为V(G)={x1,x2,?,xp}，E(G)={xixj|其中xi与xj在X中有结构关系} 核与核度的概念在网络图和系统上是统一的 2.2 几类特殊图的核度 星图：记作K1,p-1，是一种特殊的完全2-部图 完全k-部图：记作 ,它的节点集是k个两两互不相交的子集V1,V2,…,Vk(均非空，k ≥2),其中|Vi|=ai (i=1,2,…,k),每个Vi都是　　　　的独立集，且对于 　?u,v? , 如果u,v 不属于同一个Vi ，那么u,v 必相邻。　　　　　　　 联图：设G1,G2是两个简单图，G1和G2的联图，记作G1+G2，节点集V(G1+G2)=V(G1)∪V(G2), 边集E(G1+G2)=E(G1)∪E(G2)∪{uv|u?V(G1),v?V(G2)} 2.2 几类特殊图的核度 联图（推广）：设G1,G2,…,Gn皆为连通图，它们的联图，记作G1+G2+…+ Gn 或　　，用递归法可得： 2.2 几类特殊图的核度（续） 结论2.1： (1) (2) (3) 证明思路： (1) ① Cp中任一对不相邻的节点u，v构成Cp的点割集S*={u,v},均有?(Cp-S*)=2。由核度的定义： 　　　　　　 h(Cp)??(Cp-S*)-|S*|=2-2=0 ② 又因为Cp是2-连通的，所以|S*|?2 (S*?C(Cp))。 任取Cp中|S*|个不相邻的节点，必有 　　　　　　　　　?(Cp-S*) ≤|S*| 2.2 几类特殊图的核度（续） 因此，?(Cp -S*)-|S*|≤0, 注意到S*的任意性， h(Cp) ≤ 0 综上可得： h(Cp) = 0 (2) 对于完全图Ｋp (p ? 2),由完全图的对称性，并且只有去掉p-1个节点剩余部分才能得到一个平凡节点 (K1), 所以 　　　　　　　h(Kp)=1- (p-1)= - (p-2) (3) 显然 2.2 几类特殊图的核度（续） 结论2.2 ：设　　　　是一个完全k-部图，k ? 2 (ai ?1),则有 　　　　　 　其中　　　　　　　　　 证明思路： ① 设　　　　　=V1∪V2∪…∪Vk,其中Vi|=ai (1 ?i ? k)。 若S? C(G), S必由V1, V2,…,Vk中k -1个组成，要使 ?(G-S)-|S|达到最大值，则必使|S|尽可能地小，?(G-S)尽可能地大。令 是V1, V2,…,Vk中节点数目最多的子集，则只要取 因此 其中 结论2.3：设G1和G2分别表示n1和n2阶的非平凡连通图,则联图G1 + G2的核度是 h(G1 + G2)=max{h(G1)-n2,h(G2)-n1} 证明思路：分三种情况讨论： 2.2 几类特殊图的核度（续） 2.2 几类特殊图的核度（续） (1) 当G1和G2都是完全图时，G1+G2是n1+n2阶完全图,结论成立。 (2)当G1和G2都不是完全图时，设 是G1的核，则 h(G1)=?(G1 - )-| | = ?(G1+G2-( ∪V(G2)))-| ∪V(G2)|+|V(G2)| ≤ h(G1+G2)+n2 即：h(G1+G2)≥ h(G1)-n2，同理：h(G1+G2) ≥ h(G2)- n1 故有：h(G1+G2) ≥max{h(G1)-n2, h(G2)-n1} 2.2 几类特殊图的核度（续）