有向图的偏斜秩与直径之间的关系
《Linear Algebra and its Applications》:The relation between skew-rank and diameter of an oriented graph
【字体:
大
中
小
】
时间:2026年10月22日
来源:Linear Algebra and its Applications 1.1
编辑推荐:
# 给定偏秩且具有最大直径的定向图
## 摘要
设 $G_\sigma$ 是一个定向图,其底图为 $G$。$G_\sigma$ 的偏秩是其偏邻接矩阵的秩,记为 $\text{sr}(G_\sigma)$,而 $d(G)$ 定义为 $G$ 的直径。我们首先回顾对任意非平凡连
# 给定偏秩且具有最大直径的定向图
## 摘要
设 $G_\sigma$ 是一个定向图,其底图为 $G$。$G_\sigma$ 的偏秩是其偏邻接矩阵的秩,记为 $\text{sr}(G_\sigma)$,而 $d(G)$ 定义为 $G$ 的直径。我们首先回顾对任意非平凡连通定向图 $G_\sigma$ 有 $1 \leq d(G) \leq \text{sr}(G_\sigma)$,然后对每个偶数 $n \geq 4$,刻画所有满足 $d(G) = \text{sr}(G_\sigma)$ 的简约连通定向图(在交换和同构意义下)。我们还给出一个等价刻画,利用指定长度为四的圈的定向奇偶性。
## 引言
设 $G$ 是一个顶点集为 $V(G) = \{v_1, \ldots, v_n\}$ 的简单图。$G$ 的一个定向 $G_\sigma$ 是通过给 $G$ 的每条边赋予一个方向得到的,$G$ 称为 $G_\sigma$ 的底图。$G_\sigma$ 的偏邻接矩阵是 $n \times n$ 矩阵 $S(G_\sigma) = (s_{ij})$,定义为:
$$s_{ij} = \begin{cases} 1, & \text{若 } v_i \longrightarrow v_j, \\ -1, & \text{若 } v_j \longrightarrow v_i, \\ 0, & \text{否则。} \end{cases}$$
$G_\sigma$ 的偏秩为 $\text{sr}(G_\sigma) = \text{rank}\, S(G_\sigma)$。由于 $S(G_\sigma)$ 是实反对称矩阵,其非零特征值成对出现 $\pm i\lambda$;特别地,$\text{sr}(G_\sigma)$ 是偶数。
确定图的秩或刻画具有指定秩的图的问题可追溯至 Collatz 和 Sinogowitz [6]。小秩图在 [3]、[4]、[5] 中得到了刻画,图的秩与匹配数 [16]、[18]、[21]、独立数 [21]、路径覆盖数 [19] 和悬垂顶点数 [12] 等参数之间的关系也得到了研究。对每个非平凡连通简单图 $G$,其秩 $r(G)$ 和直径 $d(G)$ 满足 $1 \leq d(G) \leq r(G)$。Wong 等人 [23] 刻画了满足 $d(G) = r(G)$ 的图,称其为长图。Wang 和 Ma [20] 随后刻画了直径为 $2\lfloor r(G)/2 \rfloor - 1$ 的子长图。
对于定向图,偏秩的基本结果和小偏秩的刻画可参见 [8]、[15]、[17]。定向图的偏秩与其底图秩之间的关系在 [11]、[22]、[24] 中得到了研究。涉及匹配数 [13]、独立数 [7]、[9] 和圈空间维数 [10] 的界也是已知的。在本文中,$P_n^\sigma$ 表示阶为 $n$ 的定向路径。
交换是定向上的一个标准操作;例如参见 [1]、[2]。对子集 $U \subseteq V(G)$,关于 $U$ 交换 $G_\sigma$ 意味着将恰好有一个端点在 $U$ 中的每条弧反向,而保持其余弧不变。我们记所得定向为 $G_{\sigma_U}$。关于单个顶点 $u$ 的交换即取 $U = \{u\}$。若对同一底图的两个定向 $G_\sigma$ 和 $G_\tau$,存在某 $U \subseteq V(G)$ 使得 $G_\tau = G_{\sigma_U}$,则称 $G_\sigma$ 和 $G_\tau$ 交换等价。若 $D_U$ 是对角矩阵,其 $v$ 对应的元素在 $v \in U$ 时为 $-1$,否则为 $1$,则
$$S(G_{\sigma_U}) = D_U \, S(G_\sigma) \, D_U.$$
因此交换等价的定向图具有相同的偏谱,特别地具有相同的偏秩。关于 $U_1$ 和 $U_2$ 的连续交换等价于关于其对称差 $U_1 \triangle U_2$ 的单次交换。特别地,任一森林的所有定向都是交换等价的;因此每条定向路径都可以通过交换化为所有弧沿路径方向一致的定向。
对简单图 $G$ 和其子图 $H$,设 $N_H(u)$ 表示 $u$ 在 $H$ 中的邻居集合。若 $H_\sigma$ 是 $G_\sigma$ 的继承定向的子图,记 $N_{H_\sigma}(u) = (N_{H_\sigma}^+(u), N_{H_\sigma}^-(u))$,其中 $N_{H_\sigma}^+(u)$ 和 $N_{H_\sigma}^-(u)$ 分别是 $u$ 在 $H_\sigma$ 中的出邻居集和入邻居集。对 $u, v \in V(G)$,若它们对应的出邻居集和入邻居集相等,或者各顶点的出邻居集等于另一顶点的入邻居集,则记 $N_{H_\sigma}(u) \sim N_{H_\sigma}(v)$。当 $H = G$ 时,这样的顶点称为孪生点。等价地,$S(G_\sigma)$ 中以孪生点为索引的行相等或相反。因此,从一对孪生点中删除一个顶点不改变偏秩。此外,上述矩阵恒等式 $S(G_{\sigma_U}) = D_U \, S(G_\sigma) \, D_U$ 表明交换保持孪生关系,从而保持简约性——若一个定向图没有孪生点,则称其为简约的。
对非平凡连通定向图 $G_\sigma$,底图的直径满足
$$1 \leq d(G) \leq \text{sr}(G_\sigma) \quad (\text{见定理 3.1}).$$
等式 $d(G) = 1$ 成立当且仅当 $G$ 是完全图,此时 $G_\sigma$ 称为竞赛图。$n$ 阶竞赛图 $T$ 的偏秩在 [14] 中完全确定:
$$\text{sr}(T) = \begin{cases} n, & \text{若 } n \text{ 为偶数}, \\ n-1, & \text{若 } n \text{ 为奇数}. \end{cases}$$
因此直径为 1 的定向图无需在此单独处理。
在第 3 节中,对每个偶数 $n \geq 4$,我们构造一个阶为 $5n/2 - 2$ 的固定定向图 $H_n$。定理 3.2 将满足 $\text{sr}(G_\sigma) = d(G) = n$ 的简约连通定向图刻画为 $H_n$ 的包含其标志性路径的导出子图(在交换和同构意义下)。$H_n$ 本身在此类中达到最大的可能阶数。我们随后在定理 3.3 中通过指定长度为四的圈的奇偶性给出另一个等价描述。
## 章节摘要
### 预备知识
若 $H_\sigma$ 是 $G_\sigma$ 由顶点子集 $V(H) \subseteq V(G)$ 导出的定向子图,记 $H_\sigma \triangleleft G_\sigma$。
**引理 2.1** [8] 设 $G_\sigma$ 是一个定向图。若 $H_\sigma \triangleleft G_\sigma$,则 $\text{sr}(H_\sigma) \leq \text{sr}(G_\sigma)$。
**引理 2.2** [8] 对阶为 $n$ 的定向路径 $P_n^\sigma$,
$$\text{sr}(P_n^\sigma) = \begin{cases} n, & \text{若 } n \text{ 为偶数}, \\ n-1, & \text{若 } n \text{ 为奇数}. \end{cases}$$
若 $\text{sr}(G_\sigma) = |V(G)|$,则称定向图 $G_\sigma$ 是非奇异的。
**引理 2.3** 设 $G_\sigma$ 是一个定向图,$H_\sigma \triangleleft G_\sigma$ 非奇异且 $\text{sr}(G_\sigma) = \text{sr}(H_\sigma)$。则以下结论成立。
(i) 若 $G$ 连通,则 $V(G) \setminus V(H)$ 中的每个顶点都与 $H$ 中的某个顶点相邻。
(ii) 若 $u, v \in V(G) \setminus V(H)$ 且 $N_{H_\sigma}(u) \sim N_{H_\sigma}(v)$,则……
### 给定偏秩且具有最大直径的定向图
引理 2.1 和 2.2 给出如下直径界。
**定理 3.1** 设 $G_\sigma$ 是一个非平凡连通定向图,$\text{sr}(G_\sigma) = n$。则 $n$ 是正偶数且
$$1 \leq d(G) \leq n.$$
**证明** 下界成立是因为 $G$ 非平凡且连通。若 $d(G) \geq n+1$,则两个距离为 $d(G)$ 的顶点之间的最短路径包含一个导出定向路径 $P_{n+2}^\sigma$。由于 $n+2$ 为偶数,引理 2.2 给出 $\text{sr}(P_{n+2}^\sigma) = n+2$。引理 2.1 则意味着 $\text{sr}(G_\sigma) \geq n+2$,矛盾。故 $d(G) \leq n$。$\square$
由于向定向图添加一个孪生点……
Xiaobin Ma | Zhen Wang | Fan Jiang
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号