笛卡尔乘积图的一般位置数.pdf

第 卷 第 期集美大学学报（自然科学版）年 月 （）：收稿日期 基金项目 国家自然科学基金项目（）；江苏省科研与创新项目（）；南京航空航天大学引航计划项目（）作者简介 田静（），女，博士生，从事度量图论研究。通信作者：许克祥（），男，教授，博导，从事图论及其应用的研究。：文章编号 （）：笛卡尔乘积图的一般位置数田 静，许克祥（南京航空航天大学数学学院，江苏 南京）摘要 对于图 及子集 （），若 的任意三元子集在图 中均是非测地的，则 是图 的一般位置集。图 的最大一般位置集的基数称为 的一般位置数。给出树与任意图的笛卡尔乘积图的一般位置数的下界，验证下界的紧性，并得到星与圈的笛卡尔乘积图的一般位置数的确切值。此外，还得到含通用点且其不在最大一般位置集中的两个图的笛卡尔乘积的一般位置数的下界。关键词 一般位置集；一般位置数；笛卡尔乘积；星中图分类号 引言设 （），（）表示点集为（）、边集为（）的简单图，其中阶数（）。本文考虑的图都是有限连通简单图。图 的 度点称为叶子点，中叶子点的个数记为（）。（，）表示图 中点、之间的距离（、之间最短路的边数）。图 中的最短，路称作，测地线。年，提出了著名的“三点不共线”问题，即：在 网格中找到可以放置的最大点数，使得其中任意放置的三个点不在同一条线上。虽然“三点不共线”问题至今仍是一个开放性的问题，但由它衍生的问题却推动了其他学科的发展。近几年，基于离散几何中一般位置子集的选取问题，等提出了图论的一般位置集问题，即：在给定图 中找到一个最大的点子集美大学学报（自然科学版）第 卷：集，使得 中任意三点在图 中不位于同一条测地线。设 是（）的一个三元子集，若 中的任意一个点在图 中均不位于连接其余两点的任意一条测地线上，则称 在图 中是非测地的，是（）的非测地集。设集合 （），若 的任意三元子集在图 中都是非测地的，则称 是图 的一般位置集。图 的一个最大一般位置集的基数叫作图 的一般位置数，这个最大的一般位置集叫作图 的 集。图的一般位置数被提出来以后，受到了学者们的广泛研究。等提出了一个与图的一般位置集问题等价的问题，同时给出了完全二部图、毛毛虫树等特殊图类的一般位置数的递推公式，而且刻画了一般位置数为、和 的图结构。等不仅给出了树、块图等特殊图的一般位置数的表达式，而且证明了图的一般位置集问题是 完备的。等一方面确定了余图、二部图及其补图、直径为 的图等的一般位置数的递推公式，另一方面也证明了图的一般位置集的导出子图是完全子图。由于笛卡尔乘积是图论中构造新图的重要方法，因此研究笛卡尔乘积图的一般位置数是非常有意义的。等确定了任意两个连通图的笛卡尔乘积图的一般位置数的下界，且当两个图是完全图时，等号成立。表示 个图 的笛卡尔乘积图，表示一条双向无穷路。文献 分别研究了关于双向无穷路的笛卡尔乘积图的一般位置数问题，特别地，文献 证明了（）。文献 给出了两棵树的笛卡尔乘积图的一般位置数的递推公式，即证明了一般位置数在树的笛卡尔乘积图上是可加的。文献 不仅确定了一些直径较小的图的笛卡尔乘积图的一般位置数，还证明了任意两图的笛卡尔乘积图的一般位置数的上界，并刻画了相应的极图。除此之外，文献 研究了图的强积图、直积图、字典序积图等的一般位置数问题。更多关于图的一般位置数的问题见文献 。本文继续研究笛卡尔乘积图的一般位置数问题。首先，确定了树 与任意图 的笛卡尔乘积图的一般位置数的下界，并给出了达到下界时的图；然后，确定了星 与圈 的笛卡尔乘积图的一般位置数的递推公式；最后，给出了含通用点且其不在最大一般位置集的两个图的笛卡尔乘积的一般位置数的下界。预备知识设图 和 是两个点不交的简单图。图 和图 的笛卡尔乘积图 是一个简单图，其中（）（）（），并对，（）和，（），（，），（，）（）且 （），或者 （）且 。给定点 （），由点集（，）：（）导出的子图称为 的一个 层，记作。同理，层记作，其中（）。因此 层和 层分别同构于图 和图。对正整数 和 ，表示由完全图 去掉固定点邻接的 条边得到的图。给定点，由若干个完全图分别与点 做联运算（完全图中的每个点与点 之间加边）得到的图称为广义完全图。通常用、分别表示 个点的圈、星。众所周知，距离在笛卡尔乘积图上具有可加性，即：给定笛卡尔乘积图 的两个点（，）和（，），则（，），（，）（，）（，）。（）给定两点，（），（，）表示 和 在图 中的区间，即位于最短，路上的所有点的集合。从而，（，）：（，）（，）（，）。对于 （），如果 （，），则称 在图 中位于，测地线上。对正整数，。文中未定义的术语和记号参见文献。引理 若 是一棵树，则（）（）。引理 设 是笛卡尔乘积图 的一般位置集。若点（，），则（）或 第 期田 静，等：笛卡尔乘积图的一般位置数：（）。引理 若正整数 且，则（），或 ，其他。引理 若 是一棵阶数至少为 的树，则（）（）（）。引理 设 是 的圈，是阶数至少为 的任意图。若 是 的一个 集，则 （），其中 （）。引理 若 和 是两个阶数至少为 的图，则（）（）（），等式成立当且仅当 和 是广义完全图。主要结果及其证明文献 给出了任意两个连通图的笛卡尔乘积图的一般下界。下面考虑树与任意图的笛卡尔乘积图的一般位置数的下界。定理 若 是一棵阶数至少为 的树，是阶数至少为 的图，则（）（）（）。证明 设（）是树 的叶子点集，是图 任意一个 集。给定点 和树 非叶子点，令 （）（），其中 。基于引理，由 的选取，有（）（）。下证 是 的一般位置集。考虑 的任意三元集 ，其中 （，），（，），（，）。假设（），知 与。利用式（）可得到：（，）（，），（，）（，），（，）（，）。又，（），所以有：（，）（，）（，），（，）（，）（，），（，）（，）（，），从而可得，、和 不位于 的同一条测地线上。因此 在 中是非测地的。同理，当 时，在 中也是非测地的。下面不妨设 （）且，则有 且 。基于式（），有：（，）（，）（，），（，）（，）（，），（，）（，）。由此推出，、和 在 中不可能位于同一条测地线上，即 是 的非测地集。类似地，当，（）和 时，也是 的非测地集。因此 是 的一个一般位置集，故（）（）（）。由引理 知，当 时，定理 的下界是可达的。下面给出另一个达到下界的更一般的例子。命题 若 是 的星，是前面定义的图，且，则（）。证明 由定理 知，（）。若（），那么根据引理 有，（）。但等号成立要求 是广义完全图，这与 的结构矛盾。从而证得（）。引理 推出（）（），下面继续研究树 与圈（）的笛卡尔乘积图的一般位置集。引理 设（），表示圈 的点集，（），表示树 的叶子点集，其中，。令 ，则，有：）若，则（，），（，）：是 的一般位置集；）若 ，则（，），（，）：（，）：（，）是 的一般位置集。证明）假设。设 （，）：和 （，）：。令 ，则 。考虑 的任意三元子集 ，其中，（，），（，）和 （，）。集美大学学报（自然科学版）第 卷：基于 式（）知，（，）（，）（，），（，）（，）（，），（，）（，）（，）。因为，（），所以（，）（，）（，）。假设 ，则意味着、和 位于圈 的同一条路 上，其中（）。不妨假设在 上位于 和 之间，即（，）（，）（，）。因此（，）（，）（，），从而知 不位于 的，测地线上。同理，可得 和 分别不位于 的，测地线、，测地线上。故、和 在 中不位于同一条测地线上。类似地，当 时，同样证得、不位于 的同一条测地线上。不妨假设 且，从而得 不位于圈 的，测地线上，因此 不位于 的，测地线上。根据式（）得，（，）（，）（，）以及（，）（，）（，）。故（，）（，）（，）和（，）（，）（，），由此知 和 分别不位于 的，测地线、，测地线上。因此，、不位于 的同一条测地线上。类似地，当，且 时，、也不位于 的同一条测地线上。综上所述，是 的一个一般位置集。）假设 。设 （，）：，（，）：以及 （，）：。令 （，）。考虑 的任意三元子集 ，。假设 （，），（，），（，），其中 。基于式（）有，（，）（，）（，），（，）（，）（，），（，）（，）（，）。如果 ，那么有（，），（，）（，）（，），（，）。又 且，（），所以（，）（，）（，）。因此（，），（，）（，），（，）（，），由上可得（，）（，）（，），（，）（，）（，）。从而推出 与 分别不位于 的，测地线和，测地线上。剩下的证明类似于）的证明，这里省略。故 是 的一个一般位置集。下面考虑星 与圈 的笛卡尔乘积图的一般位置数问题。定理 若 是阶数 的圈，是阶数 的星，则（）（），。证明 设 是 的任意 集，。经简单计算，有（）。当 且 时，由引理 推出（）。若 ，则由引理，有（）。所以在下面证明中，设 且。情形 。在本情形下，由引理 的）推出（）（）。要证等式成立，需证（）（）。假 设 ，对 任 意 点 （），断 言（）。若 存 在（）且 （，），（，）（），那么由引理 可得（）和（），其中 （）且，（）。又，则基于引理，有（）（），与假设矛盾，故断言成立。根据假设和引理，可得到（），其中 是星 的通用点。令 （，）（），（，），使得 在圈 上距离 最近，其中。不妨假设 ，显然有 （）。下证（）。假设（）且令（，），（，）（），其中，。如果 ，则，且（，）。因为、和 位于最短，路，为计算方便，令 ，第 期田 静，等：笛卡尔乘积图的一般位置数：所以由式（）得（，）（，）（，）（，）。从而知 位于 的，测地线上，这与，矛盾。类似地，当 或 时，可得到类似的矛盾，此处证明省略。如果 且，则 位于最短，路上，即（，）（，）（，）。基于式（），有（，）（，）（，）（，），因此 位于 的，测地线上，再次与，矛盾。故（）。令 （），下证（）。注意 且 。如果（），则存在 ，使得（），其中（）。不妨假设 （，）以及 （，），其中 。由假设可知，且 位于最短，路。利用上述类似的方法，基于等式（），有（，）（，）（，），即 位于 的，测地线上，这与，是 的一般位置集矛盾。因此（）。综上，（）（）（）。从而证得（）。情形 。在本情形下，由引理 的）推出（）。如果（），基于引理，有（），其中 是星的通用点。令 （，）（），（，），使得 在圈 上距离 最近，其中 。不妨假设 。类似情形 的证明，有 （），（）。设 （），注意 。类似情形 的证明，有（）。因此，（）（）（），与假设矛盾，从而证得（）。上述考虑的笛卡尔乘积图中至少一个图含通用点且通用点不在 集中，下面考虑两图的通用点均不包含在 集中的情形。命题 设、分别是含通用点 和 的图，且、是图 和 的 集。若 且，则（）（）是 的一般位置集。证明 令 （）（）。下证 是 的一般位置集。考虑 的任意三元子集 ，假设 。根据假设可推出、位于 的 层上。因为 是 层的一个一般位置集，所以、在 的 层上不可能位于同一条测地线上。因此三元子集 在 上是非测地的。同理，当 时，三元子集 在 中是非测地的。故下面不妨假设 且，其中 （，），（，），（，）。因为、位于层上，所以（，），。利用式（），从而有（，）（，）（，）和（，）（，）（，）。又因为 和 分别是 和 的通用点且，所以（，），（，）（，）。由此可推出（，）（，）。因此、和 不可能位于 的同一条测地线上，即三元子集 在 上是非测地的。类似地，当，且 时，三元子集 是 的非测地集。根据定义，是 的一般位置集。由命题，容易得到推论。集美大学学报（自然科学版）第 卷：推论 若、均是阶数至少为 含有通用点的图，且通用点均不在其 集中，则（）（）（）。参 考 文 献 ：，：，：，：，：，：，：，：，（）：，：，：，：，：，：，：，：，：，：，：，：，：，：，（责任编辑 马建华 英文审校 黄振坤）