共查询到11条相似文献,搜索用时 265 毫秒
1.
2.
3.
4.
5.
研究了单位$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|)$ 的强多项式时间算法。 相似文献
6.
研究了单位$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|)$ 的强多项式时间算法。 相似文献
7.
8.
9.
设$ 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 $ 时的结论。 相似文献
10.
设$ 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 $ 时的结论。 相似文献