图论 王智慧 复旦大学计算机学院
图论 王智慧 复旦大学计算机学院
图的基本概念 ●图的概念 ●通路与回路 ●图的连通性 ●图的矩阵表示 ●图的运算
2 图的基本概念 z 图的概念 z 通路与回路 z 图的连通性 z 图的矩阵表示 z 图的运算
无序积,多重集 定义:设A和B为任意的两个集合,称{a,b}|a∈A,b∈B}为A 与B的无序积,记做A&B 定义:元素可以重复出现的集合称为多重集,其中某元素重复出 现的次数称为该元素的重复度 例如:{a,a,b}为一个多重集,其中元素a的重复度为2,元素b的重 复度为1
3 无序积, 多重集 定义: 设A和B为任意的两个集合，称{ {a, b} | a∈A, b∈B }为A 与B的无序积，记做A&B. 定义: 元素可以重复出现的集合 称为多重集, 其中某元素重复出 现的次数称为该元素的重复度. 例如: {a, a, b}为一个多重集, 其中元素a的重复度为2, 元素b的重 复度为1
无向图与有向图的概念 定义:一个无向图是一个有序的二元组G=<V,E>,其中 (1)V≠φ称为顶点集,其元素称为顶点或结点; (2)E称为边集E={(vy)vv∈V是无序积V&V的多 重子集,其中(vp称为无向边(或简称边) 定义:一个有向图是一个有序的二元组D=<V,E>,其中 (1)V≠φ称为顶点集,其元素称为顶点或结点; (2)E称为边集E={<v2yv,veV}是笛卡儿积Vx 的多重子集,其中<V,v称为有向边 通常情况下,无向图和有向图都可以用图形来直观表示,即: 用小圆圈(或实心点)表示顶点,用顶点之间的连线表示无向边,用 4有方向的连线表示有向边
4 无向图与有向图的概念 定义: 一个有向图是一个有序的二元组 D = <V, E>, 其中: (1) V ≠ φ称为顶点集, 其元素称为顶点或结点； (2) E称为边集, E = { <vi, vj> | vi, vj∈V }是笛卡儿积V×V 的多重子集, 其中<vi, vj>称为有向边. 通常情况下, 无向图和有向图都可以用图形来直观表示, 即: 用小圆圈(或实心点)表示顶点, 用顶点之间的连线表示无向边, 用 有方向的连线表示有向边. 定义: 一个无向图是一个有序的二元组 G = <V, E>, 其中 (1) V ≠ φ称为顶点集, 其元素称为顶点或结点； (2) E称为边集, E = { (vi, vj) | vi, vj∈V }是无序积V&V的多 重子集, 其中(vi, vj)称为无向边(或简称边)
基本概念 在图的定义中,有时也用G来泛指图(包括无向图和有向图)用 V(G)和E(G分别表示图G的顶点集和边集 V(G川和E(G川分别表示图G的顶点数和边数,如果(G川|=n, 则称G为n阶图;若Ⅳ(G川与(G)川均为有限数,则称G为有限图 在图G中,如果边集E(G)=中,则称G为零图;此时,若G为n阶 图,则称G为n阶零图,记作Nn特别地,称N1为平凡图 5
5 基本概念 ¾ 在图的定义中, 有时也用G来泛指图(包括无向图和有向图), 用 V(G)和E(G)分别表示图G的顶点集和边集; ¾ |V(G)|和|E(G)|分别表示图G的顶点数和边数. 如果|V(G)| = n, 则称G为n阶图; 若|V(G)|与|E(G)|均为有限数, 则称G为有限图. ¾ 在图G中, 如果边集E(G) = φ, 则称G为零图；此时, 若G为n阶 图, 则称G为n阶零图, 记作Nn; 特别地, 称N1为平凡图