哈尔滨理工大学呻斛生課程 离影数 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一个无向图是一个有序的二元组<V,E>,记作G,其中 (1)V≠称为顶点集,其元素称为顶点或结点。 (2)E称为边集,它是无序积V&V的多重子集,其元素称为无向 边,简称边 定义14.2一个有向图是一个有序的二元组V,E>,记作D,其中 (1)V≠②称为顶点集,其元素称为顶点或结点。 (2)E为边集,它是笛卡儿积V×V的多重子集,其元素称为有向 边,简称边。 ‖说明》口可以用图形表示图,即用小圆圈(或实心点)表示顶 点,用顶点之间的连线表示无向边,用有方向的连线 表示有向边
定义14.1 一个无向图是一个有序的二元组<V，E>,记作G，其中 （1）V≠称为顶点集，其元素称为顶点或结点。 （2）E称为边集，它是无序积V&V的多重子集，其元素称为无向 边，简称边。 定义14.2 一个有向图是一个有序的二元组<V，E>，记作D，其中 （1）V≠称为顶点集，其元素称为顶点或结点。 （2）E为边集，它是笛卡儿积V×V的多重子集，其元素称为有向 边，简称边。 无向图和有向图 说明 ❑ 可以用图形表示图，即用小圆圈（或实心点）表示顶 点，用顶点之间的连线表示无向边，用有方向的连线 表示有向边