第一节图的基本概念 在这些图中，点和线的位置是按照对图研究 的方便而随意确定的，点的位置并不是实际的地 理位置，边的形状也不是实际路线的形状，图中 边的长度也不是严格按照路线的实际长度按比例 尺画出，线段本身不代表真正的长度，我们只关 心图中有多少个点，而这些点又有多少条边，如 何进行连接。因此图论中所说的“图”与几何图 形、函数图像以及机械制图中的图是完全不同的。 13
13 第一节 图的基本概念 在这些图中，点和线的位置是按照对图研究 的方便而随意确定的，点的位置并不是实际的地 理位置，边的形状也不是实际路线的形状，图中 边的长度也不是严格按照路线的实际长度按比例 尺画出，线段本身不代表真正的长度，我们只关 心图中有多少个点，而这些点又有多少条边，如 何进行连接。因此图论中所说的“图”与几何图 形、函数图像以及机械制图中的图是完全不同的
第一节图的基本概念 组成图的基本要素是一些点和连接这些点的 线（见图8-5）。 e3 V3 e4 V6 v4 V1 V2 O e5 el e7 e6 e8 V5 图8-5图的基本要素 14
14 第一节 图的基本概念 组成图的基本要素是一些点和连接这些点的 线(见图8-5)。 图8-5 图的基本要素
第一节图的基本概念 定义设V={y1,V2,Vm}是含有n个元素 的非空集合，E={e1,e2,em}是m个元素的集 合。若对任一e∈E,均有v,v∈V与之对应， 则称UE为图，记为G=(V,E)。称v:为G的顶点， e为G的边，并记e=(Ws,v)=(W,v)。称v,V 是e的端点，e是与vs,v关联的边。称vs,v为邻 接的点。 我们可以把图8-5中用点和线构成的图用数学 定义表示出来。将该图记为G=(V,E),则： 15
15 第一节 图的基本概念 定义 设 V={v1，v2，.，vn }是含有n个元素 的非空集合，E={e1，e2，.，em}是m个元素的集 合。若对任一ej ∈E，均有vs，vt ∈V与之对应， 则称VE为图，记为G＝(V，E)。称vi为G的顶点， ej为G的边，并记ej ＝(vs，vt )＝(vt，vs )。称vs，vt 是ej的端点，ej是与vs，vt关联的边。称vs，vt为邻 接的点。 我们可以把图8-5中用点和线构成的图用数学 定义表示出来。将该图记为G＝(V，E)，则：
第一节图的基本概念 V={V1,V2,V3V4 V5, V63 E={e1,e2,e3,e4, es,e6' e7 e1=(V1,V2),e2=(V2,V3),e3=( 3 e4=(W4,V3),es=(W4V2), e=(v2,vs),e8=( 5 如果图中一边的两个端点相同，则称为自回 路，如图8-5中的e3。如果图中两边具有相同的一 对端点，则称为平行边，如图8-5中的e,和eg 16
16 第一节 图的基本概念 V={v1，v2，v3，v4，v5，v6 }， E={e1，e2，e3，e4，e5，e6，e7，e8 } e1=(v1，v2 )，e2=(v2，v3 )，e3=(v3，v3 )， e4=(v4，v3 )，e5=(v4，v2 )，e6=(v5，v4 )， e7=(v2，v5 )，e8=(v5 ,v2 )。 如果图中一边的两个端点相同，则称为自回 路，如图8-5中的e3。如果图中两边具有相同的一 对端点，则称为平行边，如图8-5中的e7和e8
第一节图的基本概念 没有自回路和平行边的图称为简单图。本章 中讨论的图都是简单图。 由图的定义可知，这里的图只考虑点和边 以及点和边的对应关系，所以当两个图的形状看 来似有不同，但如它们的顶点集、边集以及点和 边的关联关系一一对应时就可以看作是同一个图。 如图8-6中(1)和(2)所表示的图就是如此
17 第一节 图的基本概念 没有自回路和平行边的图称为简单图。本章 中讨论的图都是简单图。 由图的定义可知，这里的图只考虑点和边， 以及点和边的对应关系，所以当两个图的形状看 来似有不同，但如它们的顶点集、边集以及点和 边的关联关系一一对应时就可以看作是同一个图。 如图8-6中(1)和(2)所表示的图就是如此