实验5：图论的基本概念2008[1].4.28(2)

(3)设E1?E,且E1??,以E1为边集,E1的端点集为顶点集的图G的子图,

称为G的由E1导出的子图,记为G[E1].

G, G[{v1,v4,v5}] , G[{e1,e2,e3}] 三、 关联矩阵(点与边相关联)如何用电脑记录下图1与图2，这用线性代数中矩阵的方法。

Ｍ＝(mij)??图1?，其中：

图2对无向图Ｇ，其关联矩阵

e1e20101e300110110e4e51?v1?0?v2 0?v3?1??v41mij???0??1?若vi与ej相关联?1若vi与ej不关联 ，M=?0??0?对有向图Ｇ，其关联矩阵Ｍ＝(mij)???，其中：

mij?1????1?0?若vi是ej的起点若vi是ej的终点 若vi与ej不关联四、 邻接矩阵(点与点是否邻接)对无向图Ｇ，其邻接矩阵

A?(aij)???，其中：

6

v1v2v3v4??0101?va1若vi与vj相邻1011?1?v2ij????0若v与v，A=?ij不相邻??0101? ??v3?1110??v4对有向图Ｇ＝（Ｖ，Ｅ），其邻接矩阵A?(aij)???，其中：

a??1若（vEij?i，vj）??0若（vi，vj）?E

对无向赋权图Ｇ，其邻接矩阵A?(aij)???，其中：

?wij,　若(vi,vj)?E,且wij为其权a?ij??0，　若i?j???，　若(v i,vj)?E有向赋权图的邻接矩阵可类似定义． 如上图图2的赋权图的邻接矩阵为

v1v2v3v4??02?7?vA=?2083?1?v2???805???v。 3?7350??v4 7