资源描述：
《《管理精英宣言》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、AsimpleTestFortheConsecutiveOnesPropertyWithoutPC-trees!Consecutive1’sPropertyofmatricesGivena(0,1)-matrixM,doesthereexistaPERMUTATIONoftheCOLUMINSofMsuchthatthe1’sintheROWSareconsecutive? 1234 1100 1001 01103214 0110 0011 1100ConsecutiverequirementontherowsEachrowiofMc
2、anbeviewedasarequirementthatthosecolumnswitha1inrowjmustbeconsecutive.BoothandLueker﹝1976﹞showedthattheconsecutiveonespropertycanbetestedusingP-Qtreesinlineartime.Theyprocesstheconsecutiverequirementinarowbyrowfashion.P-QTreesTwotypesofinternalnodes:P-nodes&Q-nodes Child
3、renofaP-nodecanbe“permutedarbitrarily” ChildrenofaQ-nodecanonlybe“reversed”QP1234L(T)={allpermutationsgeneratedbyT}Intheexample,L(T)={1234,1243,4321,3421}IntermediateOn-LineOperations…………………………StrictlyOverlappingRelationshipsTwocolumnsaresay,tooverlapstrictlyiftheyoverla
4、pbutnoneiscontainedintheother. Suchapairofrowsimpliesthefollowingcolumnpartition:1------11---11----1uvＶｕＶ∩ｕｕＶIdealSituationIfthereisavertexorderingv1,v2,…,vmsuchthateachvistrictlyoverlapswithsomevjwithj＜i,thenitistrivialtotesttheconsecutiveonespropertyPartitionBefor
5、e1------11---11----1After1---11--11--11---11----1TheGeneralCase(I)DefinethegraphGonthesetofrowswhoseedgesetconsistsofthosestrictlyoverlappingpairsofcolumns.EachconnectedcomponentofGsatisfiestheabove“idealsituation”.ThecorrespondingsubmatricesarecalledprimeThematrixsatisf
6、iestheCOPiffeachofitsprimesubmatricesdoesAnexampleoftheGraphG1234567891016437981052TheGeneralCase(II)However,wecannotaffordtocomputealltheedgesinG,whichcouldtakeO(r2)time.Weshallcomputeasubsetofedgesthatcontainaspanningtreeofeachconnectedcomponent.Notethattheprocessofobt
7、ainingthecomponentactuallydecomposethematrixintoprimesubmatricesAnEfficiencyNoteThe#ofstrictlyadjacentpairsis
8、A
9、
10、B
11、.Leta,bbe theleastindexedrowsinA,B,respectively.ToconnectA,B,itsufficestomakeaadjacenttoallrowsinBandbadjacenttoallrowsinA.ABabAnEfficiencyNoteThe#ofstrictl
12、yadjacentpairsis
13、A
14、
15、B
16、.Leta,bbe theleastindexedrowsinA,B,respectively.ToconnectA,B,itsufficestomakeaadj
