作业7.1无向图及有向图无向图有向图给每条边赋与权的图G=<V,E>称为加权图，记为G=<V,E,W>,其中W表示各边权的集合。设ek＝(vi,vj)为无向图G＝<V,E>中的一条边,称vi,vj为ek的端点,ek与vi(或vj)是彼此关联的.无边关联的顶点称为孤立点.若一条边所关联的两个顶点重合,则称此边为环.ek与vi(或vj)的关联次数设G＝<V,E>为一无向图或有向图(1)若V,E都是有穷集合,则称G是有限图.(2)若｜V｜＝n,则称G为n阶图．(3)若E＝,则称G为零图．特别是,若此时又有｜V｜＝1,则称G为平凡图.相邻始点终点度设D＝<V,E>为一有向图,vj∈V,称vj作为边的始点的次数之和,为vj的出度,记作d+(vj)；称vj作为边的终点的次数之和,为vj的入度,记作d-(vj)；称vj作为边的端点的次数之和,为vj的度数,简称度,记作d(vj).显然d(vj)＝d+(vj)＋d-(vj).deg(v1)＝3，deg+(v1)＝2，deg-(v1)＝1；deg(v2)＝3，deg+(v2)＝2，deg-(v2)＝1；deg(v3)＝5，deg+(v3)＝2，deg-(v3)＝3；deg(v4)＝deg+(v4)＝deg-(v4)＝0；deg(v5)＝1，deg+(v5)＝0，deg-(v5)＝1；其中，v5是悬挂结点，<v1，v5>为悬挂边。最大度和最小度若D＝〈V,E〉是有向图,除了Δ(D),(D)外,还有最大出度、最大入度、最小出度、最小入度,分别定义为基本定理(握手定理)推论定理度数序列例7.1平行边、重数、多重图、简单图例无向完全图、有向完全图图7.2子图、真子图生成子图、导出子图在如下图中，给出了图G以及它的真子图G’和生成子图G’’。G’是结点集{v1，v2，v4，v5，v6}的导出子图。补图图7.4图的同构同构有向图的同构(1)≌(2),顶点之间的对应关系为av1,bv2,cv3,dv4,ev5.两图同构1、顶点个数相同2、边的条数相同3、度数相同的结点数相同(a)≌(b)≌(c).(a)所示图称为彼德森图.例7.2(1)画出4个顶点3条边的所有可能非同构的无向简单图；(2)画出3个顶点2条边的所有可能非同构的有向简单图.7.1结束，返回目录