资源描述:
《《管理精英宣言》PPT课件(I)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、AsimpleTestFortheConsecutiveOnesPropertyWithoutPC-trees!Consecutive1’sPropertyofmatricesGivena(0,1)-matrixM,doesthereexistaPERMUTATIONoftheCOLUMINSofMsuchthatthe1’sintheROWSareconsecutive?12341100100101103214011000111100ConsecutiverequirementontherowsEachrowiofMcanbeview
2、edasarequirementthatthosecolumnswitha1inrowjmustbeconsecutive.BoothandLueker﹝1976﹞showedthattheconsecutiveonespropertycanbetestedusingP-Qtreesinlineartime.Theyprocesstheconsecutiverequirementinarowbyrowfashion.P-QTreesTwotypesofinternalnodes:P-nodes&Q-nodesChildrenofaP-nodecanb
3、e“permutedarbitrarily”ChildrenofaQ-nodecanonlybe“reversed”QP1234L(T)={allpermutationsgeneratedbyT}Intheexample,L(T)={1234,1243,4321,3421}IntermediateOn-LineOperations…………………………StrictlyOverlappingRelationshipsTwocolumnsaresay,tooverlapstrictlyiftheyoverlapbutnoneiscontainedinthe
4、other.Suchapairofrowsimpliesthefollowingcolumnpartition:1------11---11----1uvVuV∩uuVIdealSituationIfthereisavertexorderingv1,v2,…,vmsuchthateachvistrictlyoverlapswithsomevjwithj<i,thenitistrivialtotesttheconsecutiveonespropertyPartitionBefore1------11---11----1After1---11-
5、-11--11---11----1TheGeneralCase(I)DefinethegraphGonthesetofrowswhoseedgesetconsistsofthosestrictlyoverlappingpairsofcolumns.EachconnectedcomponentofGsatisfiestheabove“idealsituation”.ThecorrespondingsubmatricesarecalledprimeThematrixsatisfiestheCOPiffeachofitsprimesubmatricesdoe
6、sAnexampleoftheGraphG1234567891016437981052TheGeneralCase(II)However,wecannotaffordtocomputealltheedgesinG,whichcouldtakeO(r2)time.Weshallcomputeasubsetofedgesthatcontainaspanningtreeofeachconnectedcomponent.Notethattheprocessofobtainingthecomponentactuallydecomposethematrixinto
7、primesubmatricesAnEfficiencyNoteThe#ofstrictlyadjacentpairsis
8、A
9、
10、B
11、.Leta,bbetheleastindexedrowsinA,B,respectively.ToconnectA,B,itsufficestomakeaadjacenttoallrowsinBandbadjacenttoallrowsinA.ABabAnEfficiencyNoteThe#ofstrictlyadjacentpairsis
12、A
13、
14、B
15、.Leta,bbetheleastindexedrowsinA,B
16、,respectively.ToconnectA,B,itsufficestomakeaadj