广义容斥原理及其应用

容斥原理(包含和排斥原理的简称,又称取舍原理或出入原理)是组合计数中的一个非常基本而重要的工具。Schwenk和魏万迪推广了容斥原理。本文给出了容斥原理的一种新的拓广,得到了广义容斥原理。     

计数多项式与计数子

容斥原理、广容斥原理等都可视为相应于某个特定的集合运算函数的计数原理。我们证明了,对任一集合运算函数,都可有一个类似的计数原理,且存在唯一的一个多项式——计数多项式,使相应计数原理可由此多项式直接给出。作为具体例子,我们给出了容斥、广容斥原理等公式简明的新处理及其若干推广。作为计数多项式概念的推广,我们研究了计数子的概念、性质、计算原则与方法及其与某二个布尔代数间同构映射之间的关系。     

容斥原理及其应用

容斥原理是解决组合计数这类数学问题的有力工具,一些具有某些重叠性质的元素的集合的元的个数的计算问题,应用一般方法不易着手,若应用容斥原量,则可迎刃而解。容斥原理有N件事物,其中N_a件有     

组合几何(一) 计数

计数是组合数学的基本组成部分之一,它是组合数学的基础,其基本内容包括数学归纳法、排列组合、迭代与归纳、映射与反演、容斥原理等,还有其他计数技巧.计数表现在组合几何上大致有两个方面:一是对某些几何元素或几何量直接计算它的数目;二是研究当由几何元素或几何量构成的集合的元素达到某     

错排问题的递推求解

一、错排问题现有五件球衣分属五个运动员,现问五个运动员都不穿自己的球衣,而穿其它球员的球衣,这样的穿法有几种?这就是5个元素的错排问题.就一般而言,有几个不同的元素,它们一一对应于几个位置,如果这n个元素都不排在自身对应的位置上,这种排列的方法称为几个元素的一个错排.现要计算这种错排的个数.大数学家欧拉曾用容斥原理求出了n个元素的错排个数为:Dn=n!1-11!+21!-31!+……+(-n1!)n这是运用容斥原理解决问题的一个典范.现从另一个角度出发,运用错排问题自身的递推规律,求错排问题的解.二、错排问题的递推规律设有n个不同的元素a1,a…     

关于维数公式

指出线性子空间维数公式不存在与容斥原理相类似的结论,并且分析了原因。     

多角度处理分装模型的计数与概率计算

从多个角度利用多种方法计算一类分装模型的计数,同时给出了相应的概率计算.分装模型就是将n个球分装到m个盒子中计数的模型.分装模型涉及到排列与组合、反演公式、容斥原理、Stirling数、生成函数及整数的分拆等组合数学中的大部分的计数方法.本文从组合数学的不同计数方法入手,详细叙述分装模型在不同情形下的解,深入剖析不同情形下解不同的原因.     

关于维数公式

指出线性子空间维数公式不存在与容斥原理相类似的结论，并且分析了原因。     

错位排列问题

文应用容斥原理求得了“装错信封问题”的一个计数公式：将规个元素a1,n2,…,an排在行个位置上,则元素a1（i=1,2…,n）不排在第i个位置上的排法种数Gn=n!     

关于Schrder路径计数的几个递推式的组合证明

利用Schrder路径中不同类型的步的特点,研究不同初始高度的Schrder路径,给出了Schrder路径计数的递推公式的组合证明.     

Upper bounds on the independence and the clique covering number

New upper bounds for the independence number and for the clique covering number of a graph are given in terms of the rank, respectively the eigenvalues, of the adjacency matrix. We formulate a conjecture concerning an upper bound of the clique covering number. This upper bound is related to an old conjecture of Alan J. Hoffman which is shown to be false. Key words: adjacency matrix, eigenvalues, independence number, clique covering number. AMS classification: 05C.     

On the adjacency matrix of a threshold graph

A threshold graph on n   vertices is coded by a binary string of length n−1$n-1$. We obtain a formula for the inertia of (the adjacency matrix of) a threshold graph in terms of the code of the graph. It is shown that the number of negative eigenvalues of the adjacency matrix of a threshold graph is the number of ones in the code, whereas the nullity is given by the number of zeros in the code that are preceded by either a zero or a blank. A formula for the determinant of the adjacency matrix of a generalized threshold graph and the inverse, when it exists, of the adjacency matrix of a threshold graph are obtained. Results for antiregular graphs follow as special cases.     

校园最佳游览路线问题的数学模型分析

将某高校的校园示意图转化为赋权连通图，求得该连通图的邻接矩阵，利用Floyd算法及图论软件包构造一个最短路径矩阵，得到一个赋权完全图，将求校园最佳游览路线问题归结为图论中的最佳推销员回路问题，建立混合整数线性规划模型，并利用优化软件求得最优解．从而解决了校园开放日游览计划中提出的关于校园最佳游览路线和校园游览车最优配置问题．     

可迹图的谱充分条件

设G是一个简单图,A(G),Q(G)以及Q(G)分别为G的邻接矩阵,无符号拉普拉斯矩阵以及距离无符号拉普拉斯矩阵,其最大特征值分别称为G的谱半径,无符号拉普拉斯谱半径以及距离无符号拉普拉斯谱半径.如果图G中有一条包含G中所有顶点的路,则称这条路为哈密顿路;如果图G含有哈密顿路,则称G为可迹图;如果图G含有从任意一点出发的哈密顿路,则称G从任意一点出发都是可迹的.主要研究利用图G的谱半径,无符号拉普拉斯谱半径,以及距离无符号拉普拉斯谱半径,分别给出图G从任意一点出发都是可迹的充分条件.     

邻接树图是哈密尔顿图猜想的一个等价命题

本文给出了简单图的邻接树图是哈密尔顿图”猜想的等价命题,阐明只需证明该猜想对2－连通图成立即可,另外,我们给出了该猜想一种特殊情形的构造性证明。     

Newtonian Mechanics and the Sixth Form∗ Syllabus

It is shown that a class of planar conjugated hydrocarbon molecules can be modelled in terms of a simple graph and the related adjacency matrix. Various physical and chemical properties are related to properties of the graphs. The resonance energy is related to such simple invariants as the total number of CC links and the number of Kekulé structures. Rules for enumerating these structures are described.     

A counterexample to the rank-coloring conjecture

It has been conjectured by C. van Nuffelen that the chromatic number of any graph with at least one edge does not exceed the rank of its adjacency matrix. We give a counterexample, with chromatic number 32 and with an adjacency matrix of rank 29.     

The group and the minimal polynomial of a graph

This paper presents some results linking the minimal polynomial of the adjacency matrix of a graph with its group structure. An upper bound on the order of the group is derived for graphs whose minimal and characteristic polynomials are identical. It is also shown that for a graph with transitive group, the degree of the minimal polynomial is bounded above by the number of orbits of the stabilizer of any given element. Finally, the order of the group of a point-symmetric graph with a prime number of points is shown to depend on the degree of the minimal polynomial, and an algorithm for constructing such a group is given.     

广义系统的Hamilton矩阵与H\-2代数Riccati方程的稳定化解

研究线性连续广义系统的Hamilton矩阵及H\-2代数Riccati方程.　提出一个标准的广义H\-2代数Riccati方程及对应的Hamilton矩阵，给出该Hamilton矩阵的几个重要性质. 在此基础上，得到该广义H\-2代数Riccati方程的稳定化解存在的一个充分条件并给出求解方法.此条件具有一般性, 主要定理是正常系统相应结果的推广.     

On the weighted trees with given degree sequence and positive weight set

We determine the (unique) weighted tree with the largest spectral radius with respect to the adjacency and Laplacian matrix in the set of all weighted trees with a given degree sequence and positive weight set. Moreover, we also derive the weighted trees with the largest spectral radius with respect to the matrices mentioned above in the sets of all weighted trees with a given maximum degree or pendant vertex number and so on.