图的基本概念与模型 Page 11 。子图，部分图（支撑子图） 图G={V1E}和图G2={V2,E2}如果有 c'和E,∈E,称G1是G2的一个子图。 若有V=V,E,∈E,则称G是G2的 es 个部分图（支撑子图）。 es e es (G图) e6 es e6 (a) (b)
图的基本概念与模型 Page 11 子图，部分图(支撑子图) 图G1={V1、E1 }和图G2={V2，E2 }如果有 称G1是G2的一个子图。 若有 ，则称G1是G2的一 个部分图(支撑子图)。 V1 V2 和E1 E2 V1 ＝V2 ，E1 E2 v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 v3 e4 e8 e5 e6 v2 v4 v5 v3 e7 e4 e8 e6 e2 e3 v1 v2 v4 v5 (a) (b) （G图）
图的基本概念与模型 Page 12 。网络（赋权图） 设图G=(V,E),对G的每一条边(y,)相应赋予数量指标 ,w称为边(y)的权，赋予权的图G称为网络（或赋权图） 。 权可以代表距离、费用、通过能力（容量）等等。 端点无序的赋权图称为无向网络，端点有序的赋权图称为有 向网络。 ② 15 ④ 14 ⑤ 10 19 20 ③ 25
图的基本概念与模型 Page 12 网络（赋权图） 设图G＝（V，E），对G的每一条边(vi ,vj )相应赋予数量指标 wij，wij称为边(vi ,vj )的权,赋予权的图G称为网络(或赋权图）。 权可以代表距离、费用、通过能力(容量)等等。 端点无序的赋权图称为无向网络，端点有序的赋权图称为有 向网络。 ① ② ③ ④ ⑤ ⑥ 9 10 20 15 7 14 19 25 6
图的基本概念与模型 Page 13 出次与入次 有向图中，以为始点的边数称为点的出次，用d()表 示；以y为终点的边数称为点y的入次，用表示d();点 的出次和入次之和就是该点的次。 必有向图中，所有顶点的入次之和等于所有顶点的出次之 和
图的基本概念与模型 Page 13 出次与入次 有向图中，以vi为始点的边数称为点vi的出次，用d + (vi )表 示；以vi为终点的边数称为点vi 的入次，用表示d - (vi ) ；vi 点 的出次和入次之和就是该点的次。 ※ 有向图中，所有顶点的入次之和等于所有顶点的出次之 和
图的基本概念与模型 Page 14 图的模型应用 例6.1有甲，乙，丙，丁，戊，己6名运动员报名参加A,B,C,D,E,F6 个项目的比赛。下表中打V的是各运动员报告参加的比赛项 目。问6个项目的比赛顺序应如何安排，做到每名运动员都 不连续地参加两项比赛。 A B E 甲乙丙丁戊己
图的基本概念与模型 Page 14 图的模型应用 例6.1 有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F 6 个项目的比赛。下表中打√的是各运动员报告参加的比赛项 目。问6个项目的比赛顺序应如何安排，做到每名运动员都 不连续地参加两项比赛。 A B C D E F 甲 √ √ 乙 √ √ √ 丙 √ √ 丁 √ √ 戊 √ √ √ 己 √ √ √
图的基本概念与模型 Page 15 解：用图来建模。把比赛项目作为研究对象，用点表示。如 果2个项目有同一名运动员参加，在代表这两个项目的点之 间连一条线，可得下图。 在图中找到一个点序 B 列，使得依次排列的 两点不相邻，即能满 足要求。如： 1)A,C,B,F,E,D 2)D,E,F,B,C,A
图的基本概念与模型 Page 15 解：用图来建模。把比赛项目作为研究对象，用点表示。如 果2个项目有同一名运动员参加，在代表这两个项目的点之 间连一条线，可得下图。 A B C D E F 在图中找到一个点序 列，使得依次排列的 两点不相邻，即能满 足要求。如： 1) A,C,B,F,E,D 2) D,E,F,B,C,A