图论 王智慧 复旦大学计算机学院
图论 王智慧 复旦大学计算机学院
图的基本概念 ●图的概念 ●通路与回路 ●图的连通性 ●图的矩阵表示 ●图的运算
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=,其中 (1)V≠φ称为顶点集,其元素称为顶点或结点; (2)E称为边集E={(vy)vv∈V是无序积V&V的多 重子集,其中(vp称为无向边(或简称边) 定义:一个有向图是一个有序的二元组D=,其中 (1)V≠φ称为顶点集,其元素称为顶点或结点; (2)E称为边集E={<v2yv,veV}是笛卡儿积Vx 的多重子集,其中<V,v称为有向边 通常情况下,无向图和有向图都可以用图形来直观表示,即: 用小圆圈(或实心点)表示顶点,用顶点之间的连线表示无向边,用 4有方向的连线表示有向边
4 无向图与有向图的概念 定义: 一个有向图是一个有序的二元组 D = , 其中: (1) V ≠ φ称为顶点集, 其元素称为顶点或结点； (2) E称为边集, E = { | vi, vj∈V }是笛卡儿积V×V 的多重子集, 其中称为有向边. 通常情况下, 无向图和有向图都可以用图形来直观表示, 即: 用小圆圈(或实心点)表示顶点, 用顶点之间的连线表示无向边, 用 有方向的连线表示有向边. 定义: 一个无向图是一个有序的二元组 G = , 其中 (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为平凡图
基本概念 在图的定义中,我们规定顶点集V为非空集,但在图的运算中 可能产生顶点集为空集的运算结果,为此规定顶点集为空集 的图为空图,并将空图记为 在将图的集合定义转化成图形表示之后,常用e表示无向边 vVy)或有向边vpy→)称顶点或边用字母标定的图为标定 图,否则,称为非标定图 将有向图各有向边改成无向边后的无向图称为原来图的基图
6 基本概念 ¾ 在图的定义中, 我们规定顶点集V为非空集, 但在图的运算中 可能产生顶点集为空集的运算结果, 为此规定顶点集为空集 的图为空图, 并将空图记为∅. ¾ 在将图的集合定义转化成图形表示之后, 常用ek表示无向边 (vi, vj)(或有向边), 称顶点或边用字母标定的图为标定 图, 否则, 称为非标定图. ¾ 将有向图各有向边改成无向边后的无向图称为原来图的基图
基本概念 >设G=为无向图,ek=(vpv)∈E,则称vv为e的端 点,e与v或ek与v是彼此相关联的; 若v≠v则称ek与v或ek与v的关联次数为1若v=v1p则称 ek与v的关联次数为2,并称e为环;Ws∈V若vs≠V且vs≠ vp则称ek与v。的关联次数为0; 设D=V,E>为有向图,ek=vpvy>∈E,称vv为e的端点; 若v1=vp则称ek为D中的环; 无论在无向图中还是有向图中,无边关联的顶点称为孤立点
7 基本概念 ¾ 设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为环; ∀vs∈V, 若vs ≠ vi且vs ≠ vj, 则称ek与vs的关联次数为0; ¾ 设D = 为有向图, ek = ∈E, 称vi, vj为ek的端点; 若vi = vj, 则称ek为D中的环; ¾ 无论在无向图中还是有向图中, 无边关联的顶点称为孤立点
基本概念 >设无向图G=,vyeV,eke∈E若彐e∈E,使得et= (vv少则称v与v是相邻的若ek与e。至少有一个公共端点,则 称ek与e是相邻的。 设有向图D=,则称v为e的始点,v为e的终点,并称v邻接到v1Y邻接于 v若ek的终点为e的始点,则称ek与e相邻
8 基本概念 ¾ 设无向图G = , vi, vj∈V, ek, es∈E. 若∃et∈E, 使得 et = (vi, vj), 则称vi与vj是相邻的. 若ek与es至少有一个公共端点, 则 称ek与es是相邻的。 ¾ 设有向图D = , vi, vj∈V, ek, es∈E. 若et∈E, 使得 et = , 则称vi为et的始点, vj为et的终点, 并称vi邻接到vj, vj邻接于 vi. 若ek的终点为es的始点, 则称ek与es相邻
基本概念 设无向图G=,v∈V称{u|ueV∧(u,v)∈E∧u≠v} 为v的邻域,记做N(v);称N。(v)U{v}为v的闭邻域,记做N(); 称{e|e∈E∧e与v相关联}为v的关联集,记做(v) >设有向图D=,veV,称{u|ueVA∈E∧u≠v} 为v的后继元集,记做r0(v)称{u|u∈V∧∈E∧u≠v} 为v的先驱元集,记做r(v);称r()Ur(v)为的邻域,记做 ND(v);称Nv)U{v}为v的闭邻域,记做ND()
9 基本概念 ¾ 设无向图G = , ∀v∈V, 称 { u | u∈V∧(u, v)∈E∧u ≠ v } 为v的邻域, 记做NG(v); 称 NG(v)∪{ v }为v的闭邻域, 记做 ; 称 { e | e∈E∧e与v相关联 }为v的关联集, 记做IG(v) ¾ 设有向图D = , ∀v∈V, 称 { u | u∈V∧∈E∧u ≠ v } 为v的后继元集, 记做Γ+D(v); 称 { u | u∈V∧∈E∧u ≠ v } 为v的先驱元集, 记做Γ-D(v); 称Γ+(v)∪Γ-(v)为v的邻域, 记做 ND(v); 称ND(v)∪{ v }为v的闭邻域, 记做 ( ) N v G ( ) N v D
平行边,多重图,简单图 定义: 在无向图中,若关联一对顶点的无向边多于1条,则称这些边为 平行边,平行边的条数称为重数 >在有向图中,若关联一对顶点的有向边多于1条,并且这些边的 起点与终点相同即边的方向相同)则称这些边为平行边 >含平行边的图称为多重图;既不含平行边,也不含环的图称为简 单图 10
10 平行边, 多重图, 简单图 定义: ¾ 在无向图中, 若关联一对顶点的无向边多于1条, 则称这些边为 平行边, 平行边的条数称为重数. ¾ 在有向图中, 若关联一对顶点的有向边多于1条, 并且这些边的 起点与终点相同(即边的方向相同), 则称这些边为平行边. ¾ 含平行边的图称为多重图; 既不含平行边, 也不含环的图称为简 单图