圖的最小秩

Abstract

我們讓G表示一個沒有重邊且沒有迴路的無向圖。若x是G上的一個點，則Gx是把點x及連接x的所有邊都去掉。我們獲得來回演算法去計算G的最小秩m(G)如下：定理：假設y和x是圖G上的點且兩個相連，其中y只與x相連。則$m(G)=m(G_{y})+1$若且唯若 $m(G_{y}) \leq m(G_{x})+1$。

Let $G$ be an undirected graph without loops or edges. For a vertex $x\in V(G)$, let $G_x$ denoted the subgraph induced on the vertex set $V(G)\in \{x\}$. We obtain the following back and Forth algorithm to compute the minimun rank $m(G)$: Theorem: Suppose $y$ is a vertex of $G$ with degree 1 and $x$ is the neighbor of $y$. Then $m(G)=m(G_y)+1$ iff $m(G_y)\leq m(G_x)+1$.