§1图的基本概念与模型 。链，圈，路，回路，连通图 图中某些点和边的交替序列，若其中 各边互不相同，且对任意V1和v均相 邻称为链。用μ表示： u=ivo,e,v1,.,es,v es 起点与终点重合的链称作圈。 e 链中所有顶点不相同，这样的链称为路。 起点与终点重合的路称作回路。 如果每一对顶点之间至少存在一条链， 称这样的图为连通图，否则称图不连通。 2014-12-15 11
2014-12-15 11 §1 图的基本概念与模型 链，圈，路，回路，连通图 图中某些点和边的交替序列，若其中 各边互不相同，且对任意vi,t-1和vit均相 邻称为链。用μ表示： v3 e7 e4 e8 e5 e6 e1 e2 e3 v1 v2 v4 v5 { , , , , , } 0 1 1 k k v e v e v 起点与终点重合的链称作圈。 链中所有顶点不相同，这样的链称为路。 起点与终点重合的路称作回路。 如果每一对顶点之间至少存在一条链， 称这样的图为连通图，否则称图不连通
§1图的基本概念与模型 。完全图与二部图（偶图） 一个简单图中若任意两点之间均有边相连，这样的 图叫完全图。图G=(V,E)的点集V可以分为两个非空 子集X,Y,集XUY=V,X∩Y=0,使得同一集合中任 意两个顶点均不相邻，称这样的图为偶图。 V3 (a) (b) (c) (a)明显为二部图，(b)也是二部图，但不明显，改画为(c) 时可以清楚看出。 2014-12-15 12
2014-12-15 12 §1 图的基本概念与模型 完全图与二部图（偶图） 一个简单图中若任意两点之间均有边相连，这样的 图叫完全图。图G=(V,E)的点集V可以分为两个非空 子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任 意两个顶点均不相邻，称这样的图为偶图。 v1 v3 v5 v2 v4 v6 v1 v2 v3 v4 v1 v4 v2 v3 (a) (b) (c) (a)明显为二部图，(b)也是二部图，但不明显，改画为(c) 时可以清楚看出
§1图的基本概念与模型 。子图，部分图（支撑子图） 图G={V1、E}和图G2={V2,E2}如果有 VsV和EsE,称G1是G2的一个子图。 若有V=V,E1SE, 则称G1是G2的一 es 个部分图（支撑子图）。 e 3 es (G图) e6 es 2014-12闭 (b) 13
2014-12-15 13 §1 图的基本概念与模型 子图，部分图(支撑子图) 图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图）
§1图的基本概念与模型 图的模型应用 例1有甲，乙，丙，丁，戊，己6名运动员报名参加A,B,C,D,E,F6个 项目的比赛。下表中打V的是各运动员报告参加的比赛项目。 问6个项目的比赛顺序应如何安排，做到每名运动员都不连 续地参加两项比赛。 A B E 甲乙丙丁 戊 2014-12-15 14
2014-12-15 14 §1 图的基本概念与模型 • 图的模型应用 例1 有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F 6个 项目的比赛。下表中打√的是各运动员报告参加的比赛项目。 问6个项目的比赛顺序应如何安排，做到每名运动员都不连 续地参加两项比赛。 A B C D E F 甲 √ √ √ 乙 √ √ √ 丙 √ √ 丁 √ √ 戊 √ √ √ 己 √ √ √
§1图的基本概念与模型 解：用图来建模。把比赛项目作 D 为研究对象，用点表示。如果2 个项目有同一名运动员参加， 在代表这两个项目的点之间连 一条线，可得下图。 在图中找到一个点序列， 使得依次排列的两点不相 邻，即能满足要求。如： A B E 1)A,C,B,F,E,D 2)D,E,F,B,C,A 甲乙丙丁 2014-12-15 15 已
2014-12-15 15 §1 图的基本概念与模型 解：用图来建模。把比赛项目作 为研究对象，用点表示。如果2 个项目有同一名运动员参加， 在代表这两个项目的点之间连 一条线，可得下图。 A B C D E F 在图中找到一个点序列， 使得依次排列的两点不相 邻，即能满足要求。如： 1) A,C,B,F,E,D 2) D,E,F,B,C,A A B C D E F 甲 √ √ √ 乙 √ √ √ 丙 √ √ 丁 √ √ 戊 √ √ √ 己 √ √ √