《生物数学中的若干问题——群试理论和图的竞赛数》由会员分享，可在线阅读，更多相关《生物数学中的若干问题——群试理论和图的竞赛数（53页珍藏版）》请在金锄头文库上搜索。
1、上海交通大学 硕士学位论文 生物数学中的若干问题群试理论和图的竞赛数 姓名：仲崇崇 申请学位级别：硕士 专业：应用数学 指导教师：吴耀琨 20081201 ? ? ? ? ? ? ? ? ?Dorfman?1943? ? ? ? ? ? ?1?2? ? ?RID ?3, 4? ? ? ? ?Opsut 24? ?Opsut 24? ? ?d-? d-?d-? ?Las Vegas? i ABSTRACT Some Problems in Biomathematics Group Testing Theory and Competition Number of a Graph ABSTRACT
2、Biomathematics is an interdisciplinary research fi eld between bi- ology and mathematics.For one thing, it can solve many biological problems by using mathematical tools; for the other, it can broaden the mathematical research span. Biomathematics has been proved to be a great boost to both biology
3、and mathematics. In this thesis, we will probe into some problems in group testing theory and competition number problem, which are both belong to biomathematics. Group testing theory has been fl ourishing since the World War Two. In 1943, Dorfman fi rst proposed the group testing problem, that is,
4、how to detect syphilis from the blood samples of millions of draftees effi ciently. Over the past 60 years, group testing theory has been proved to be very useful in many fi elds, such as blood testing, electric shorting detection, multi-access channel communication and computational biol- ogy. Part
5、 one is made up of the fi rst three chapters in this thesis. In chapter one, we will fi rst present the basic properties of separating ma- trices, and then we will present the error-tolerant version of separating matrices, including our correction of one theorem in Du and Hwang 1 and some extention
6、work2. In chapter two, we will give a brief survey on the construction of separating matrices, using tools from combinatorics, linear space over fi nite fi elds and so on. In chapter three, we will devote to random group testing, in this chapter we will fi rst do some compu- tational work on RID-mod
7、el, then we will give a survey on the work by Cheng and Du 3, 4 about the great use of probabilistic method in the construction of separating matrices and matrices bound estimation. The competition number problem was fi rst proposed by biologists when they do research into food chain problem in ecos
8、ystem. Those research will be helpful for people to know more about the structure of ecosystem and something others. Part two is the last chapter of this thesis, we will fi rst list some results on competition number problem of Opsut 24, then we will generalize one of his result on line graph to any
9、 graph. ii KEY WORDS:Group testing,dseparable matrix, dseparable matrix,ddisjunct matrix,error-tolerantmatrix,construction of sep- arating matrices,transversal design,probabilistic method,Las Ve- gas algorithm,line graph,competition number. iii ? ? ? S(0,1)? |S|?S? ? U(S)?S? A B?A?B? w(C)(0,1)?C?C?1? vi ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?,? ? ?. ?”X”? ? ? ? ? 1.1? ? ? ? ? ? ? ? ? ?1986? ? ?DNA? ?DNA? ?DNA? ? ?DNA? ?n? ? ? ?d? ? ? ? ? ? ?(n, d)? ?d?(n,d)? ? ? ? 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(0,1)?M = (mij)? M?mij= 1?i ?
