补充资料：经典组合问题

经典组合问题
classical combinatorial problems

　　问题可以表述为洲，图1所示的图i二，是否能完成一次从一点出发经过份边恰好一次而回到起点的环游(见图的回路(脚ph olreuit，). a 口 图l 如果在个图土可作此环游，则称该图有一个Euler圈.Euler证明一J一个图上有这种圈当且仅当该图连通，以及与每一顶点关联的边数是偶数.因图l所示之图不满足这个要求，故K6山乡berg桥问题的解答是这种环游不可能.即使不要求回到出发点，也不可能有这种巡游.这时所解决的问题是在图土Eu】er链(Euler chain)的存在性.一个图具有Euler链当且仅当它连通，以及所关联的边数为奇数的顶点数是O或2.图I所示的图满足这个条件见【3p W，Hamilton在1 859年发明了一种“环球旅行”游戏它要求在图2所示的图上经过每个顶点(城市)恰好一次并回到出发点的路.图中具有这种性质的路称为Hamilton回路(Hamiltonian Cyde).现在(1 978)还不知道在一个图中存在Ham讨ton回路的充分必要条件(见【3〕). 协 图2 关于图中Hamilton回路的问题有多种推广，旅行堆节早ltl琴(‘raVelling salesman problem)是其中之一，它在运筹学特别是解某些运输问题中有不少应用.这个问题的内容如下二设有若干城市，它们之间的距离已知，要求找出经过所有城市恰一次并回到出发处的最短路. T.P，儿rkn飞an在1850年提出了巧名女生问题(Problem of the 1 5 schoolgirls)，并于1 851年给出该问题的一个解，女教师要为她的学生安排一个下午散步的日程表:侮天把这15名女生分成5组，每组3人，使得每两个女生在7天中有且仅有一天分在同一组.这个问题与构作Steiner三元系(K此rnan，1847，J.Steiner，1 853)有关.一个砂阶Steiner三元系(S如-ner trip更es”tem)，记为sTS(v)或S(v)，是。元集的一组3元子集，使得其中每一对元素恰含于一个3元集中.对犷蕊巧的Sle加cr三兀系已完成分类:对砂二3，7，9，三元系在(对v个元素的置换及由此导出的3元子集的置换所定义的)等价关系下只有唯--一类;对。二13和巧，则分别有2个和劝个不同等价类.当v>1:5时，等价类的个数还不知道(1978).当v>3时一个凡tei-ner泛元系是一种特殊的平衡不完全区组设计(论，k陀kd。卿) 经典的匹配问题(matching problem)是这样的:设有两付相同的牌，每付n张，各张互不相同.要求确定数D。;，。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。