一类新的优美树

Rosa 等人于1966年提出了著名的优美树猜想,即任何树都是优美图.该猜想至今没有得到证明或否定,仅有一些特殊树类被证明是优美图.通过构造路Pn=v0v1…vm的平衡标号f使f(v0)=k,其中k为任意不大于n的非负整数,且4k≠n,3n,进而给出一种新的优美树的构造方法,使已知的优美树大大增加.     

基于One-port模式的测试点选取问题

在故障诊断过程中 ,每个测试点检测故障所需的时间可能不同。对于每个测试点一次检测所有可检测故障点的问题已经获得解决。对于每个测试点一次只能检测一个故障点 ,分两种情况加以讨论。若要求检测时间之和最小 ,给出了最优算法 ;若要求最大检测时间最小 ,证明了其是NP完全问题 ,并给出近似算法。最后给出一个实例对算法加以说明     

P3，4m的优美性

设u、v是两个固定顶点,用b条内部互不相交且长度均为a的道路连接u、v所得到的图用Pa,b表示.Kathiresan证实P2r,2m-1(r,m均为任意正整数)是优美的,且猜想除了(a,b)=(2r+1,4s+2)外,所有的Pa,b都是优美的.杨元生已证实P2r+1,2m-1是优美的.本文证明P3,4m是优美图,从而当a=3时Kathiresan猜想成立.