共查询到15条相似文献,搜索用时 125 毫秒
1.
2.
研究了单位$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|)$ 的强多项式时间算法。 相似文献
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|)$ 的强多项式时间算法。 相似文献
4.
本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$ 台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$ 为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$ 为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$ 时, 该算法近似比为3, 当接受工件个数小于$(m-1)$ 时, 该算法近似比为$(2+\rho)$ , 其中$\rho$ 为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。 相似文献
5.
本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$ 台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$ 为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$ 为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$ 时, 该算法近似比为3, 当接受工件个数小于$(m-1)$ 时, 该算法近似比为$(2+\rho)$ , 其中$\rho$ 为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。 相似文献
6.
7.
8.
9.
10.
11.
12.
设$ 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 $ 时的结论。 相似文献
13.
设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。 相似文献
14.
15.
设$ 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 $ 时的结论。 相似文献