哈尔滨理工大学呻斛生課程 离影数 14章图的基本概念 计算机系
第14章 图的基本概念 离 散 数 学 哈尔滨理工大学本科生课程 计算机系
本章内容 14.1图 14.2通路与回路 14.3图的连通性 14.4图的矩阵表示 14.5图的运算 基本要求 作业
本章内容 14.1 图 14.2 通路与回路 14.3 图的连通性 14.4 图的矩阵表示 14.5 图的运算 基本要求 作业
14,1图的基本概贪 口图的定义 口图的一些概念和规定 口简单图和多重图 口顶点的度数与握手定理 口图的同构 口完全图与正则图 口子图与补图
14.1 图的基本概念 ❑ 图的定义 ❑ 图的一些概念和规定 ❑ 简单图和多重图 ❑ 顶点的度数与握手定理 ❑ 图的同构 ❑ 完全图与正则图 ❑ 子图与补图
无序积与多重集合 口设A,B为任意的两个集合,称{a,b|a∈A∧b∈B为A与B 的无序积,记作A&B 可将无序积中的无序对{a,砂记为(a,b),并且允许a=b 无论a,b是否相等,均有(a,b)=(b,a),因而A&B=B&A 口元素可以重复出现的集合称为多重集合或者多重集,某元 素重复出现的次数称为该元素的重复度 例如在多重集合{a,a,b,b,b,c,l中, a,b,c,d的重复度分别为2,3,1,1
无序积与多重集合 ❑ 设A，B为任意的两个集合，称{{a,b}|a∈A∧b∈B}为A与B 的无序积，记作A&B。 可将无序积中的无序对{a,b}记为(a,b)，并且允许a＝b。 无论a,b是否相等，均有(a,b)＝(b,a)，因而A&B＝B&A。 ❑ 元素可以重复出现的集合称为多重集合或者多重集，某元 素重复出现的次数称为该元素的重复度。 例如 在多重集合{a,a,b,b,b,c,d}中， a,b,c,d的重复度分别为2,3,1,1
无向图和有向图 定义14.1一个无向图是一个有序的二元组,记作G,其中 (1)V≠称为顶点集,其元素称为顶点或结点。 (2)E称为边集,它是无序积V&V的多重子集,其元素称为无向 边,简称边 定义14.2一个有向图是一个有序的二元组V,E>,记作D,其中 (1)V≠②称为顶点集,其元素称为顶点或结点。 (2)E为边集,它是笛卡儿积V×V的多重子集,其元素称为有向 边,简称边。 ‖说明》口可以用图形表示图,即用小圆圈(或实心点)表示顶 点,用顶点之间的连线表示无向边,用有方向的连线 表示有向边
定义14.1 一个无向图是一个有序的二元组,记作G，其中 （1）V≠称为顶点集，其元素称为顶点或结点。 （2）E称为边集，它是无序积V&V的多重子集，其元素称为无向 边，简称边。 定义14.2 一个有向图是一个有序的二元组，记作D，其中 （1）V≠称为顶点集，其元素称为顶点或结点。 （2）E为边集，它是笛卡儿积V×V的多重子集，其元素称为有向 边，简称边。 无向图和有向图 说明 ❑ 可以用图形表示图，即用小圆圈（或实心点）表示顶 点，用顶点之间的连线表示无向边，用有方向的连线 表示有向边
例14,1 例14.1(1)给定无向图G=,其中V={v1,v2v3,Vv4,vs}, (2)给定有向图D=,其中V={a,b,c,d}, E={,,,,,<c,b为}。 画出G与D的图形。 b
例14.1 例14.1 (1) 给定无向图G＝，其中 V＝{v1 ,v2 ,v3 ,v4 ,v5 }， E={(v1 ,v1 ),(v1 ,v2 ),(v2 ,v3 ),(v2 ,v3 ),(v2 ,v5 ),(v1 ,v5 ),(v4 ,v5 )}. (2) 给定有向图D=，其中 V＝{a,b,c,d}， E＝{,,,,,,}。 画出G与D的图形
的一些概念和规定 口G表示无向图,但有时用G泛指图(无向的或有向的)。 口D只能表示有向图。 口V(G),E(G)分别表示G的顶点集和边集。 口若|V(G)|=n,则称G为n阶图。 口若|V(G)与|E(G)|均为有限数,则称G为有限图。 口若边集E(G)=,则称G为零图,此时,又若G为n阶图,则称G 为n阶零图,记作N,特别地,称N1为平凡图 口在图的定义中规定顶点集V为非空集,但在图的运算中可能产 生顶点集为空集的运算结果,为此规定顶点集为空集的图为 空图,并将空图记为
图的一些概念和规定 ❑ G表示无向图，但有时用G泛指图(无向的或有向的)。 ❑ D只能表示有向图。 ❑ V(G)，E(G)分别表示G的顶点集和边集。 ❑ 若|V(G)|＝n，则称G为n阶图。 ❑ 若|V(G)|与|E(G)|均为有限数，则称G为有限图。 ❑ 若边集E(G)＝，则称G为零图，此时，又若G为n阶图，则称G 为n阶零图，记作Nn，特别地，称N1为平凡图。 ❑ 在图的定义中规定顶点集V为非空集，但在图的运算中可能产 生顶点集为空集的运算结果，为此规定顶点集为空集的图为 空图，并将空图记为
标定图与非标定图、基图 口将图的集合定义转化成图形表示之后,常用e表示无向边 (v;,v1)(或有向边),并称顶点或边用字母标定 的图为标定图,否则称为非标定图。 口将有向图各有向边均改成无向边后的无向图称为原来图 的基图。 口易知标定图与非标定图是可以相互转化的,任何无向图G 的各边均加上箭头就可以得到以G为基图的有向图
标定图与非标定图、基图 ❑ 将图的集合定义转化成图形表示之后，常用ek表示无向边 (vi ,vj )（或有向边），并称顶点或边用字母标定 的图为标定图，否则称为非标定图。 ❑ 将有向图各有向边均改成无向边后的无向图称为原来图 的基图。 ❑ 易知标定图与非标定图是可以相互转化的，任何无向图G 的各边均加上箭头就可以得到以G为基图的有向图
关联与头联次数、环、孤立点 口设G=为无向图,e=(vy∈E, 称v;v为e的端点,ek与或ek与v是彼此相关联的。 若v≠v;,则称ek与v或e与v的关联次数为1。 若v=v,则称e与v的关联次数为2,并称e为环。 任意的v∈V,若vv且v≠v,则称ek与v的关联次数为0。 口设D=《,E>为有向图,=<v吵∈E, 称vv为的端点。 若v=v,则称e为D中的环。 口无论在无向图中还是在有向图中,无边关联的顶点均称为孤 立点
关联与关联次数、环、孤立点 ❑ 设G＝为无向图，ek＝(vi,vj)∈E， 称vi,vj为ek的端点，ek与vi或ek与vj是彼此相关联的。 若vi≠vj，则称ek与vi或ek与vj的关联次数为1。 若vi＝vj，则称ek与vi的关联次数为2，并称ek为环。 任意的vl∈V，若vl≠vi且vl≠vj，则称ek与vl的关联次数为0。 ❑ 设D＝为有向图，ek＝∈E， 称vi,vj为ek的端点。 若vi＝vj，则称ek为D中的环。 ❑ 无论在无向图中还是在有向图中，无边关联的顶点均称为孤 立点
相邻与邻 口设无向图G=,E>,v,v∈V,"k,e∈E 若e∈E,使得e=(,),则称与是相邻的。 若e与e至少有一个公共端点,则称e与e是相邻的。 口设有向图D=,v,v∈V,ek,e∈E。 点,并称邻华。则称为的始点,为e的终 若彐e∈E,使得e=<v, 接于 若ek的终点为e的始点,则称与e相邻
相邻与邻接 ❑ 设无向图G＝，vi，vj∈V，ek，el∈E。 若et∈E，使得et ＝(vi，vj )，则称vi与vj是相邻的。 若ek与el至少有一个公共端点，则称ek与el是相邻的。 ❑ 设有向图D＝，vi，vj∈V，ek，el∈E。 若et∈E，使得et ＝，则称vi为et的始点，vj为et的终 点，并称vi邻接到vj，vj邻接于vi。 若ek的终点为el的始点，则称ek与el相邻