第23届北京高中数学知识应用竞赛初赛试题及参考答案

一、下图所示的是六角星跳棋盘,它是由一些小的正三角形拼出的,如果记棋盘上最小正三角形的边长为1 cm,六角星的每个角上的三角形的边长为kcm,就称这个六角星跳棋盘为“k-六角星棋盘”,下图就是“3-六角星棋盘”.跳棋盘上的每一个交叉点是旗子可以落下的地方.问:(1)把“3-六角星棋盘”看成一个网络地图,三角形的边组成这个网络的道路,这个网络地图里的道路总长度是多少?     

关于4-连通三角剖分的计数

本文讨论4-连通极大平面地图的计数问题.从地图对偶的角度考虑,它等价 于强3-连通3-正则有根平面地图的计数问题.在此,我们获得了具有一个和两个变 量的精确计数公式.本文的结果简化并推广了文[1,2]中的相应结果.     

射影平面和环面上奇异地图的色和

一个地图的每条边,若在同一面的边界上,则称它为奇异地图．由于含环的地图是不可着色的,本文所有地图均不含环．本文研究射影平面和环面上带根奇异地图的色和．     

块图的2-步长控制问题的一个线性时间算法

The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D.In the present paper,by using a labeling method,we provide an O(m) time algorithm to solve the2-step domination problem on block graphs,a superclass of trees.     

有根无环平面地图节点剖分计数方程

一个平面地图,如果无有边是环,则称为是无环的.有根的意义与[1]中的相同.在那里对于此类地图的一些计数问题作了研究,但从未触及到节点剖分.这篇文章的主要目的在于研究这类地图的依节点剖分的计数.求出了有根无环平面地图依节点剖分计数的母函数所满足的一个泛函方程.并且,作为这一方程的一种应用,求出了一类在节点的最大次给定情况下的有根无环平面地图依节点剖分计数的一些结果.     

关于简单平面地图依面剖分的计数方程

一个地图之谓简单是指它的母图是简单的.即,既无重边也无环.文中未解释的术语可在[1]或[2]中找到.当然,作为基础,我们还是研究有根的地图.记(?)为所有有根简单平面地图组成的集合.对于 S∈(?),记 n(S)为其根面的次,和 m_i(S)是次为 i 的非根面的数目,i≥1.本文的目的就是提供母函数     

一个新的线性规划无人工变量算法

本文研究了线性规划的求解问题.利用对偶转化的方法,获得了一个计算效率高的新的无人工变量通用算法.该新算法比最近提出的无人工变量算法push-to-pull算法效率更高.     

Klein瓶上的双奇异地图

一个地图的每条边如果不是环就是割边(即该边的两边是同一个面的边界)，则称之为双奇异地图，本文研究Klein瓶上带根双奇异地图的计数问题，得到了此类地图以边数、平面环数、手柄上本质环数和又帽上本质环数为参数的计数公式，并得到了部分计数显式。     

关于无环Euler平面地图数目的注记

本文提供了组合上不等价的有根无环Euler平面地图以边数为参数的的数目,同时对于几乎无环的情形也给出了一个计数显式.     

带根无环欧拉平面地图的计数(英文)

自20世纪60年代初Tutte的开创性工作以来,许多学者在带根地图的计数方面作了很多工作,但许多类无环地图的计数仍没有被处理.本文主要研究以根点次、非根点数和内面数为三个参数的带根无环欧拉平面地图的计数问题.     

Enumeration of weak isomorphism classes of signed graphs

A signed graph is a graph in which each line has a plus or minus sign. Two signed graphs are said to be weakly isomorphic if their underlying graphs are isomorphic through a mapping under which signs of cycles are preserved, the sign of a cycle being the product of the signs of its lines. Some enumeration problems implied by such a definition, including the problem of self-dual configurations, are solved here for complete signed graphs by methods of linear algebra over the two-element field. It is also shown that weak isomorphism classes of complete signed graphs are equal in number to other configurations: unlabeled even graphs, two-graphs and switching classes.     

t-Balanced Cayley maps of dihedral groups

A Cayley map is an embedding of a Cayley graph where the cyclic ordering of generators around every vertex is the same. The involution indicating the position of mutually inverse generators in the cyclic ordering is called the distribution of inverses of a Cayley map. The Cayley maps whose distribution of inverses is linear (modulo the degree of the map) with 'slope' t are called t-balanced. An exponent of a Cayley map is a number e with the property that, roughly speaking, the Cayley map is isomorphic to its 'e-fold rotational image'.In the contribution we present results related to the construction of t-balanced Cayley maps which are not regular and do not have t as an exponent.     

An algorithm to solve polyhedral convex set optimization problems

An algorithm which computes a solution of a set optimization problem is provided. The graph of the objective map is assumed to be given by finitely many linear inequalities. A solution is understood to be a set of points in the domain satisfying two conditions: the attainment of the infimum and minimality with respect to a set relation. In the first phase of the algorithm, a linear vector optimization problem, called the vectorial relaxation, is solved. The resulting pre-solution yields the attainment of the infimum but, in general, not minimality. In the second phase of the algorithm, minimality is established by solving certain linear programs in combination with vertex enumeration of some values of the objective map.     

Counting unrooted maps on the plane

A planar map is a 2-cell embedding of a connected planar graph, loops and parallel edges allowed, on the sphere. A plane map is a planar map with a distinguished outside (“infinite”) face. An unrooted map is an equivalence class of maps under orientation-preserving homeomorphism, and a rooted map is a map with a distinguished oriented edge. Previously we obtained formulae for the number of unrooted planar n-edge maps of various classes, including all maps, non-separable maps, eulerian maps and loopless maps. In this article, using the same technique we obtain closed formulae for counting unrooted plane maps of all these classes and their duals. The corresponding formulae for rooted maps are known to be all sum-free; the formulae that we obtain for unrooted maps contain only a sum over the divisors of n. We count also unrooted two-vertex plane maps.     

Operations on maps,and outer automorphisms

By representing maps on surfaces as transitive permutation representations of a certain group Γ, it is shown that there are exactly six invertible operations (such as duality) on maps; they are induced by the outer automorphisms of Γ, and form a group isomorphic to S₃. Various consequences are deduced, such as the result that each finite map has a finite reflexible cover which is invariant under all six operations.     

Weak Graph Map Homotopy and Its Applications∗

The authors introduce a notion of a weak graph map homotopy (they call it M-homotopy), discuss its properties and applications. They prove that the weak graph map homotopy equivalence between graphs coincides with the graph homotopy equivalence defined by Yau et al in 2001. The difference between them is that the weak graph map homotopy transformation is defined in terms of maps, while the graph homotopy transformation is defined by means of combinatorial operations. They discuss its advantages over the graph homotopy transformation. As its applications, they investigate the mapping class group of a graph and the 1-order MP-homotopy group of a pointed simple graph. Moreover, they show that the 1-order MP-homotopy group of a pointed simple graph is invariant up to the weak graph map homotopy equivalence.     

The structure of graph maps without periodic points

In this paper we show that any graph map without periodic points has only one minimal set. We describe a class of graph maps without periodic points. Our main result is to give a structure theorem of graph maps without periodic points, which states that any graph map without periodic points must be topologically conjugate to one of the described class. In addition, we give some applications of the structure theorem.     

图象的自反与渐近自反

本文对B（X,Y）的自反子空间及渐近自反子空间上的映射（或映射组）,分别给出了一些判别它们的图象（或联合图象）仍为自反及渐近自反的方法。     

On natural isomorphisms of cycle permutation graphs

Two problems are approached in this paper. Given a permutation onn elements, which permutations onn elements yield cycle permutation graphs isomorphic to the cycle permutation graph yielded by the given permutation? And, given two cycle permutation graphs, are they isomorphic? Here the author deals only with natural isomorphisms, those isomorphisms which map the outer and inner cycles of one cycle permutation graph to the outer and inner cycles of another cycle permutation graph. A theorem is stated which then allows the construction of the set of permutations which yield cycle permutation graphs isomorphic to a given cycle permutation graph by a natural isomorphism. Another theorem is presented which finds the number of such permutations through the use of groups of symmetry of certain drawings of cycles in the plane. These drawings are also used to determine whether two given cycle permutation graphs are isomorphic by a natural isomorphism. These two methods are then illustrated by using them to solve the first problem, restricted to natural isomorphism, for a certain class of cycle permutation graphs.