超图的最优标号与特征值

研究超图的标号性质,首先利用拉普拉斯张量的第二小和最大特征值给出4一致超图的带宽和与割宽的上下界;其次构造与超图对应的简单图,通过其拉普拉斯矩阵的特征值给出超图带宽的下界.     

偶一致超图划分问题的若干结果

划分问题因其在多个领域的重要应用一直是图论的研究热点.利用张量的特征值研究超图的划分与奇划分,并结合边割的界给出最大奇割、平均最小割、等周数等超图拓扑指标的界.当k取2时,这些结果与对应的图谱理论中的经典结论一致,因此可视为这些结论在超图的推广.     

T-乘积下张量广义逆及其广义Cayley-Hamilton定理北大核心CSCD

本文通过张量在T-乘积下的T-Moore-Penrose逆、T-Drazin逆以及T-corenilpotent分解定理,引入三阶F-square(正面方的)张量在T-乘积下的T-DMP逆与TCMP逆的定义,同时给出它们的若干刻画和性质.最后将三阶张量的Cayley-Hamilton定理推广到张量的T-Drazin逆与T-DMP逆上,并给出例子进行验证.     

非负不可约矩阵的广义Perron补矩阵

1989年Meyor为计算马尔可夫链的平稳分布向量构造了一个算法，首次提出非负不可约矩阵的Perron补矩阵的概念，本给出非负不可约矩阵A的广义Perron补矩阵若干性质，并且证明若矩阵A是不可约逆M-矩阵，其广义Perron补矩阵也是不可约逆M-矩阵。     

关于非负不可约矩阵的广义Perron补的一些性质

1989年Meyer为计算马尔可夫链的平稳分布向量构造了一个算法，首次提出非负不可约矩阵的Perron补的概念。本文给出非负不可约矩阵A的广义Perron补若干性质，并且证明当矩阵A是不可约逆M-矩阵，其广义Perron补也是不可约逆M-矩阵。     

环Z/p~kZ上矩阵广义逆的拓展

设R=Z/pkZ(其中k>1,p是一个奇素数),A是R上一个给定的可相似对角化的n阶矩阵.利用组合方法和有限局部环上的矩阵方法,讨论了矩阵A的拓展广义逆,得到了矩阵A的拓展广义逆存在的充要条件和一些的计数定理.     

关于非负矩阵Perron特征值的上、下界

本文通过构造一可逆矩阵,对一类非负矩阵A进行若干次简单的相似变换,便可同时得到矩阵A之Perron特征值的较好的上、下界.     

偶数阶张量core逆的性质和应用

张量广义逆是张量理论研究的重要内容之一,在近年张量广义逆研究的基础上.该文给出在爱因斯坦积下张量core逆的性质、张量偏序和张量方程A*X=B在条件χ∈R(A)下的最小二乘解等.     

广义超度量矩阵的封闭性质

本文研究了广义超度量矩阵的封闭性质.证明了若A为非奇异的广义超度量矩阵,则A与A的转置的Hadamard积仍然是一个广义超度量矩阵,并且它的逆矩阵是一个对角占优的M矩阵.给出了两个广义超度量矩阵Hadamard积封闭的一个充分条件.最后,讨论了广义超度量矩阵的Perron补与和的封闭条件.     

可迹图的谱充分条件

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

k圈图的最大Laplace分离度

设$ G $是一个$ n $阶$ k $圈图, $ k $圈图为边数等于顶点数加$ k-1 $的简单连通图。$ \mu_{1}(G) $、$ \mu_{2}(G) $分别记为图$ G $的Laplace矩阵的最大特征值和次大特征值, 图$ G $的Laplace分离度定义为$ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $。本文研究了给定阶数的$ k $圈图的最大Laplace分离度, 并刻画了相应的极图, 其结果推广了已有当$ k=1, 2, 3 $时的结论。     

k圈图的最大Laplace分离度

设$ G $是一个$ n $阶$ k $圈图, $ k $圈图为边数等于顶点数加$ k-1 $的简单连通图。$ \mu_{1}(G) $、$ \mu_{2}(G) $分别记为图$ G $的Laplace矩阵的最大特征值和次大特征值, 图$ G $的Laplace分离度定义为$ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $。本文研究了给定阶数的$ k $圈图的最大Laplace分离度, 并刻画了相应的极图, 其结果推广了已有当$ k=1, 2, 3 $时的结论。     

单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。     

单位无穷范数下边权有界的最小支撑树逆最优值问题

研究了单位$l_{\infty}$范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$, 支撑树$T^0$, 下界向量$\bm{l}$, 上界向量$\bm{u}$及数值$K$, 寻求一个新的边权向量$\bm{\bar{w}}$满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$, 且$T^0$是在向量$\bm{\bar{w}}$下权值为$K$的一个最小支撑树, 目标是在单位$l_{\infty}$范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$的强多项式时间算法。     

广义de Bruijn有向图的k-元控制集

$G=(V, A)$ 表示一个有向图, 其中 $V$ 和 $A$ 分别表示有向图 $G$ 的点集和弧集。 对集合 $D_{k}\subseteq V(G)$, 如果对于任意点 $v\in V(G)$, 都存在 $k$ 个点 $u_{i}$, $1\leq i\leq k$ (可能存在某个 $u_{i}$ 和 $v$ 是同一点) 使得 $(u_{i},v)\in A(G)$, 则称 $D_{k}$ 是 $G$ 的一个 $k$-元控制集。 有向图 $G$ 的 $k$-元控制数 $\gamma_{\times k}(G)$ 是 $G$ 的最小 $k$-元控制集所含点的数目。 给出了广义 de Bruijn 有向图的 $k$-元控制数的新上界, 并且具体给出了构造广义 de Bruijn 有向图的 $k$-元控制集的方法。 此外, 对某些特殊的广义 de Bruijn 有向图, 通过构造其 $k$-元控制集, 进一步改进了它们 $k$-元控制数的上界。     

图的邻点全和可区别全染色

设f:V(G)∪E(G)→{1,2,…,k}是图G的一个正常k-全染色。令■其中N(x)={y∈V(G)|xy∈E(G)}。对任意的边uv∈E(C),若有Φ(u)≠Φ(v)成立,则称f是图G的一个邻点全和可区别k-全染色。图G的邻点全和可区别全染色中最小的颜色数k叫做G的邻点全和可区别全色数,记为f tndi∑(G)。本文确定了路、圈、星、轮、完全二部图、完全图以及树的邻点全和可区别全色数,同时猜想:简单图G(≠K2)的邻点全和可区别全色数不超过△(G)+2。     

工件的释放时间和加工时间具有一致性的单机在线排序问题研究

工件的释放时间和加工时间具有一致性, 是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间, 即若$r_{i}\geq r_{j}$, 则$p_{i}\geq p_{j}$。本文在该一致性约束下, 研究最小化最大加权完工时间单机在线排序问题, 和最小化总加权完工时间单机在线排序问题, 并分别设计出$\frac{\sqrt{5}+1}{2}$-竞争的最好可能在线算法。     

带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法

$k$-种产品设施选址问题是指存在一组客户和一组可以建设设施的地址。现有$k$种不同的产品,每一客户均需要$k$种不同的产品,且每一设施最多只能生产一种产品。问题的要求是从若干地址中选择一组地址来建立设施,对所要建立的设施指定其生产的产品,并为每一个客户提供一组指派确保每一客户都有$k$个设施来为其提供$k$种不同的产品,使得设施建设费用与运输费用之和最小。对于$k$-种产品设施选址问题,我们通常简写为$k$-PUFLP,其中,当所有设施建设费用为0时,记为$k$-PUFLPN。本文对$k$-PUFLPN进行线性舍入,通过分析最优分数解特殊结构,当$k\geq 3$时分析算法将$k$-PUFLPN的近似比从$\frac{3k}{2}-1$提升到了$\frac{3k}{2}-\frac{3}{2}$。鲁棒$k$-种产品设施选址问题是指在该问题中,最多有$q$个客户可以不被服务。我们首次对无容量限制下建设费用为0时的鲁棒$k$-种产品选址问题建立模型,当$k\geq 3$,得到了$\frac{3k}{2}-\frac{3}{2}$近似算法。对顾客伴有线性惩罚的鲁棒$k$-种产品设施选址问题,本文同时考虑异常值与惩罚性,利用$k$-PUFLPN中最优整数解与最优分数解的关系,得到了$\frac{3k}{2}-\frac{3}{2}$近似算法。     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。     

两台自私型机器上自私工件排序的PoA紧界

本文研究了两台自私型机器上有自私型工件的关于二元均衡的排序问题。对任意工件序列$L$, 证明了二元均衡排序的PoA的紧界为$\frac{8}{7}$。如果工件尺寸在区间$[1, r](r\ge1)$内, 得到了二元均衡排序的PoA的紧界为关于$r$的分段线性函数。