下载文档原格式
22页码问题页码问题顾名思义，页码问题与图书的页码有密切联系。
编⼀本书的页码，⼀共需要多少个数码呢？反过来，知道编⼀本书的页码所需的数码数量，求这本书的页数。
这是页码问题中的两个基本内容。
为了顺利地解答页码问题，我们先看⼀下“数”与“ 组成它的数码个数”之间的关系。
⼀位数共有9个，组成所有的⼀位数需要9个数码；两位数共有90个，组成所有的两位数需要2×90＝180个数码；三位数共有900个，组成所有的三位数需要3×900＝2700个数码……为了清楚起见，我们将n位数的个数、组成所有n位数需要的数码个数、组成所有不⼤于n位的数需要的数码个数之间的关系列表如下由上表看出，如果⼀本书不⾜100页，那么排这本书的页码所需的数码个数不会超过189个；如果某本书排的页码⽤了10000个数码，因为2889＜10000＜38889，所以这本书肯定是上千页。
下⾯，我们看⼏道例题。
例1⼀本书共204页，需多少个数码来编排页码？分析与解：1～9页每页上的页码是⼀位数，共需数码1×9=9（个）；10～99页每页上的页码是两位数，共需数码2×90＝180（个）； 100～204页每页上的页码是三位数，共需数码（204-100＋1）×3＝105×3＝315（个）。
综上所述，这本书共需数码9＋180＋315＝504（个）。
例2⼀本⼩说的页码，在排版时必须⽤2211个数码。
问：这本书共有多少页？分析：因为189＜2211＜2889，所以这本书有⼏百页。
由前⾯的分析知道，这本书在排三位数的页码时⽤了数码（2211-189）个，所以三位数的页数有（2211-189）÷3＝674（页）。
因为不到三位的页数有99页，所以这本书共有99＋674＝773（页）。
解：99＋（2211——189）÷3＝773（页）。
答：这本书共有773页。
例3⼀本书的页码从1⾄62即共有62页。
图和子图 图和简单图图 G = (V, E)V ---顶点集，ν---顶点数12ε E ---边集， ε---边数例。
左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G 的几何实现（代表）， 它们有无穷多个。
真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。
不过今后对两者将经常不加以区别。
称 边 ad 与顶点 a (及d) 相关联。
也称 顶点 b(及 f) 与边 bf 相关联。
称顶点a 与e 相邻。
称有公共端点的一些边彼此相邻，例如p 与af 。
环（loop ，selfloop ）：如边 l 。
棱（link ）：如边ae 。
重边：如边p 及边q 。
简单图：（simple graph ）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。
一条边的端点：它的两个顶点。
记号：νε()(),()().G V G G E G ==。
习题1.1.1 若G 为简单图，则εν≤⎛⎝ ⎫⎭⎪2 。
1.1.2 n ( ≥ 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。
同构在下图中， 图G 恒等于图H , 记为 G = H ⇔ VG)=V(H), E(G)=E(H)。
图G 同构于图F ⇔ V(G)与V(F), E(G)与E(F)之间 各 存在一一对应关系，且这二对应关系保持关联关系。
记为 G ≅F。
注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。
de f G = (V , E )yz w cG =(V , E )w cyz H =(V ’, E ’)’a ’c ’y ’e ’z ’F =(V ’’, E ’’)注 判定两个图是否同构是NP-hard 问题。
完全图(complete graph) Kn空图（empty g.） ⇔ E = ∅ 。
V’ ( ⊆ V) 为独立集 ⇔ V’中任二顶点都互不相邻。
山东科学ＳＨＡＮＤＯＮＧＳＣＩＥＮＣＥ第２６卷 第３期 ２０１３年６月出版Ｖｏｌ．２６Ｎｏ．３Ｊｕｎ．２０１３收稿日期：２０１２ １２ １５基金项目：国家自然科学基金（６１０７０２２９）；教育部博士点基金（博导类）（２０１１１４０１１１０００５）作者简介：张雪飞（１９８９－），女，硕士研究生，研究方向为图论及其应用。
通讯作者，王世英（１９６１－），男，博士，教授，博士生导师。
Ｅｍａｉｌ：ｓｈｉｙｉｎｇ＠ｓｘｕ．ｅｄｕ．ｃｎＤＯＩ：１０．３９７６／ｊ．ｉｓｓｎ．１００２－４０２６．２０１３．０３．００１完全偶图的定向图张雪飞，王世英（山西大学数学科学学院，山西太原０３０００６）摘要：完全偶图是具有二分类（Ｘ，Ｙ）的简单偶图，其中Ｘ的每个顶点与Ｙ的每个顶点相连，若｜Ｘ｜＝ｍ，｜Ｙ｜＝ｎ，则这样的图记为Ｋｍ，ｎ。
本文主要研究了Ｋｎ，ｎ的定向图。
证明了如下结论：对于非负整数ａ和ｂ，若存在满足每个顶点的入度是ａ或者是ｂ的一个Ｋｎ，ｎ的定向图，则存在非负整数ｓ和ｔ满足方程ｓ＋ｔ＝２ｎ和ａｓ＋ｂｔ＝ｎ２。
进一步，对于满足特定条件的非负整数ａ，ｂ和ｎ，存在Ｋｎ，ｎ的定向图使得每个顶点的入度非ａ即ｂ。
关键词：二部图；定向；入度中图分类号：Ｏ１５７．６ 文献标识码：Ａ 文章编号：１００２ ４０２６（２０１３）０３ ０００１ ０４ＡｎｏｒｉｅｎｔｅｄｇｒａｐｈｏｆａｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈＺＨＡＮＧＸｕｅ ｆｅｉ，ＷＡＮＧＳｈｉ ｙｉｎｇ（ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｈａｎｘｉＵｎｉｖｅｒｓｉｔｙ，Ｔａｉｙｕａｎ０３０００６，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ∶Ａｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈｉｓａｓｉｍｐｌｅｂｉｐａｒｔｉｔｅｗｉｔｈｂｉｐａｒｔｉｔｉｏｎ（Ｘ，Ｙ）ｉｆｅａｃｈｖｅｒｔｅｘｉｎＸｉｓｃｏｎｎｅｃｔｅｄｗｉｔｈｅａｃｈｖｅｒｔｅｘｉｎＹ．ＡｃｏｍｐｌｅｔｅｂｉｐａｒｔｉｔｅｇｒａｐｈｉｓｄｅｎｏｔｅｄａｓＫｍ，ｎｉｆ｜Ｘ｜＝ｍａｎｄ｜Ｙ｜＝ｎ．ＴｈｉｓｐａｐｅｒａｄｄｒｅｓｓｅｓｔｈｅｏｒｉｅｎｔｅｄｇｒａｐｈｓｏｆＫｍ，ｎ，ａｎｄｐｒｏｖｅｓｔｈａｔｔｈｅｒｅｅｘｉｓｔｔｗｏｎｏｎ ｎｅｇａｔｉｖｅｉｎｔｅｇｅｒｓｓａｎｄｔｓａｔｉｓｆｙｉｎｇｔｈｅｅｑｕａｔｉｏｎｓｓ＋ｔ＝２ｎａｎｄａｓ＋ｂｔ＝ｎ２ｉｆｔｈｅｉｎ ｄｅｇｒｅｅｏｆｅａｃｈｖｅｒｔｅｘｉｎａｎｏｒｉｅｎｔｅｄｇｒａｐｈｏｆＫｎ，ｎｉｓａｏｒｂ（ａａｎｄｂａｒｅｔｗｏｎｏｎ ｎｅｇａｔｉｖｅｉｎｔｅｇｅｒｓ）．Ｍｏｒｅｏｖｅｒ，ｔｈｅｒｅｅｘｉｓｔｓａｎｏｒｉｅｎｔｅｄｇｒａｐｈｏｆＫｎ，ｎｔｈａｔｍａｋｅｓｔｈｅｉｎ ｄｅｇｒｅｅｏｆｅａｃｈｖｅｒｔｅｘｔｏｂｅｅｉｔｈｅｒａｏｒｂｆｏｒｔｈｅｎｏｎ ｎｅｇａｔｉｖｅｉｎｔｅｇｅｒｓａ，ｂａｎｄｎｓａｔｉｓｆｙｉｎｇｓｏｍｅｓｐｅｃｉａｌｃｏｎｄｉｔｉｏｎｓ．Ｋｅｙｗｏｒｄｓ∶ｂｉｐａｒｔｉｔｅｇｒａｐｈ；ｏｒｉｅｎｔａｔｉｏｎ；ｉｎ ｄｅｇｒｅｅ１ 引言给定任意图Ｇ，对于它的每条边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图。
