主观题:通过无向图的关联矩阵计算顶点的度,指出那个边是环等[A]
设无向图$G=<V,E>,~V=\{v_1,v_2,v_3,v_4 \},~E=\{e_1,e_2,e_3,e_4,e_5\}$,下列矩阵是G的顶点与边的关联矩阵。①求$v_1$的度数?②图中的环是哪个边?③指出图中的悬挂点与悬挂边?
$\hspace{3em}M(G)=\begin{bmatrix}1&1&0&1&0\\1&1&0&0&0\\0&0&2&1&1\\0&0&0&0&1\end{bmatrix}$
答案:解
①由于矩阵的第1行元素之和为3,所以$d(v_1)=3$
②矩阵的第3行第3列的元素值为2,因此边$e_3$与顶点$v_3$关联了两次,所以边$e_3$是图中的环。
③矩阵第4行的元素之和为1,所以顶点$v_4$为悬挂点。矩阵第3行第5列的元素值为1,所以悬挂边为$e_5$.
$\hspace{3em}M(G)=\begin{bmatrix}1&1&0&1&0\\1&1&0&0&0\\0&0&2&1&1\\0&0&0&0&1\end{bmatrix}$
答案:解
①由于矩阵的第1行元素之和为3,所以$d(v_1)=3$
②矩阵的第3行第3列的元素值为2,因此边$e_3$与顶点$v_3$关联了两次,所以边$e_3$是图中的环。
③矩阵第4行的元素之和为1,所以顶点$v_4$为悬挂点。矩阵第3行第5列的元素值为1,所以悬挂边为$e_5$.