网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

5.1 无向图与有向图

2021/6/28 11:57:22 人评论

文章目录5.1 无向图及有向图5.1.1 无向图5.1.2 有向图5.1.3 无向图与有向图5.1.4 顶点和边的关联与相邻5.1.5 顶点的度数5.1.6 握手定理定理证明推论应用5.1.7 图的度数列5.1.8 多重图与简单图5.1.9 完全图5.1.10 子图5.1.11 补图5.1.12 图的同构5.1 无向图及有向图 5.1.1 无向…

文章目录

  • 5.1 无向图及有向图
      • 5.1.1 无向图
      • 5.1.2 有向图
      • 5.1.3 无向图与有向图
      • 5.1.4 顶点和边的关联与相邻
      • 5.1.5 顶点的度数
      • 5.1.6 握手定理
      • 定理
      • 证明
      • 推论
      • 应用
      • 5.1.7 图的度数列
      • 5.1.8 多重图与简单图
      • 5.1.9 完全图
      • 5.1.10 子图
      • 5.1.11 补图
      • 5.1.12 图的同构

5.1 无向图及有向图

5.1.1 无向图

多重集合:元素可以重复出现的集合

定义 无向图G=<V,E>, 其中
(1) 顶点集V是非空有穷集合, 其元素称为顶点
(2) 边集E为V&V的多重子集,其元素称为无向边,简称
在这里插入图片描述

5.1.2 有向图

定义 有向图G=<V,E>D=<V,E>, 其中
(1)顶点集V是非空有穷集合, 其元素称为顶点
(2) 边集E为 V× V的多重子集,其元素称为有向边,简称

D的基图:用无向边代替有向边
在这里插入图片描述

5.1.3 无向图与有向图

  • 通常用G表示无向图, D表示有向图, 也常用G泛指无向图和有向图。
    V(G), E(G), V(D), E(D): G和D的顶点集, 边集

    n阶图: n个顶点的图

    零图: E= ∅

    平凡图: 1 阶零图

    空图: V= ∅

5.1.4 顶点和边的关联与相邻

定义 设e=(u,v)是无向图G=<V,E>的一条边, 称u,v为e的端点,e与u(v)关联

​ 若u≠v, 则称e与u(v)的关联次数为1;

​ 若u=v, 则称e为, 此时称e与u 的关联次数为2;

​ 若w不是e端点, 则称e与w 的关联次数为0

​ 无边关联的顶点称作孤立点

定义 设无向图G=<V,E>, u,v∈V, e,e’∈E, 若(u,v)∈E, 则称u,v相邻;

​ 若e,e’至少有一个公共端点, 则称e,e’相邻

​ 对有向图有类似定义。设e=<u,v>是有向图的一条边,又称u是e的始点,v是e的终点, u邻接到v, v邻接于u。

5.1.5 顶点的度数

​ 设G=<V,E>为无向图, v ∈ V,

v的度数(度) d(v): v作为边的端点次数之和
悬挂顶点: 度数为1的顶点
悬挂边: 与悬挂顶点关联的边
G的最大度 △ (G)=max{d(v)|v∈V}
G的最小度 δ (G)=min{d(v)| v∈V}

在这里插入图片描述

右图中d(v5)=3, d(v2)=4, d(v1)=4,△(G)=4, δ(G)=1,v4是悬挂顶点, e7是悬挂边, e1是环

设D=<V,E>为有向图, v∈V,
v的出度d+(v) : v作为边的始点次数之和
v的入度d-(v): v作为边的终点次数之和
v的度数(度)d(v) : v作为边的端点次数之和
d(v)= d+(v)+ d-(v)

D的最大出度△+(D) =max{d+(v)|v∈V}
最小出度δ+(D) =min{d+(v)|v∈V}

最大入度△-(D) =max{d-(v)|v∈V}

最小入度δ-(D) =min{d-(v)|v∈V}

最大度 △ (D)=max{d(v)|v∈V}

最小度 δ (D)=min{d(v)|v∈V}

实例: 在这里插入图片描述

5.1.6 握手定理

​ 任意无向图和有向图的奇度顶点个数必为偶数。

  • 应用

在这里插入图片描述

5.1.7 图的度数列

设无向图G的顶点集V={v1, v2, …, vn}

G的度数列: d(v1), d(v2), …, d(vn)

如右图度数列:4,4,2,1,3 在这里插入图片描述

设有向图D的顶点集V={v1, v2, …, vn}

D的度数列: d(v1), d(v2), …, d(vn)

D的出度列: d+(v1), d+(v2), …, d+(vn)

D的入度列: d-(v1), d-(v2), …, d-(vn)

如右图度数列:5,3,3,3 在这里插入图片描述

        出度列:4,0,2,1
        入度列:1,3,1,2

例题:

  1. 一个部门有25个人,由于意见不同,是否可能每个人恰好与其他5个人意见一致?

    ​ A 可能 B 不可能

  2. 唐氏夫妇邀请另外三对夫妇来家里吃饭,已知每个人都不和自己握手,不和自己的配偶握手,同时最多和一人握手一次。在大家吃完饭后,唐先生问大家握了几次手,每个人的回答都不相同。请问:唐太太握手几次?

​ A 0 B 1 C 2 D 3 E 4 F 5 G 6

答案:1. B 2. D

5.1.8 多重图与简单图

(1)在无向图中,如果有2条或2条以上的边关联同一对顶点, 则称这些边为平行边, 平行边的条数称为重数
(2)在有向图中,如果有2条或2条以上的边具有相同的始点和终点, 则称这些边为有向平行边, 简称平行边, 平行边的条数称为重数
(3) 含平行边的图称为多重图
(4) 既无平行边也无环的图称为简单图

注意:简单图是极其重要的概念。

实例:在这里插入图片描述

5.1.9 完全图

n阶无向完全图Kn:每个顶点都与其余顶点相邻的n阶无向简单图

简单性质:边数m=n(n-1)/2,Δ=δ=n-1

K5在这里插入图片描述

n阶有向完全图:每对顶点之间均有两条方向相反的有向边的n阶有向简单图

简单选择:边数m=n(n-1),Δ=δ=2(n-1)

Δ++--=n-1

3阶有向完全图在这里插入图片描述

5.1.10 子图

设G=<V,E>,G’=<V’,E’>是两个图。

(1)若V’⊆V且E’⊆E,则称G’是G的子图,G是G’的母图,记作G’⊆G

(2) 若G’⊆G 且V’=V,则称G’为G的生成子图

(3) 若V’⊂V 或E’⊂E,称G’为G的真子图

(4) 设V’⊆V 且V’≠∅, 以V’为顶点集, 以两端点都在V’中的所有边为边集的G的子图称作V’的导出子图,记作 G[V’]。

(5) 设E’⊆E且E’≠∅, 以E’为边集, 以E’中边关联的所有顶点为顶点集的G的子图称作E’的导出子图, 记作 G[E’]。

注意:每个图都是本身的子图。

生成子图的实例:

K4的所有非同构的生成子图

在这里插入图片描述

导出子图的实例:

在这里插入图片描述

5.1.11 补图

定义:设G=<V,E>是n阶无向简单图,以V为顶点集,所有使G成为完全图Kn的添加边组成的集合为边集的图,称为G的补图。记作G’。若G≌G’,则G是自补图

5.1.12 图的同构

定义:G1=<V1,E1>, G2=<V2,E2>为两个无向图(有向图), 若存在双射函数 f: V1→V2, 使得对于任意的vi,vj∈V1, (vi,vj)∈E1(<vi,vj>∈E1)当且仅当 (f(vi),f(vj))∈E2(<f(vi),f(vj)>∈E2),并且, (vi,vj)(<vi,vj>)与 (f(vi),f(vj))(<f(vi),f(vj)>)的重数相同,则称G1与G2同构的,记作G1≌G2

同构实例:

在这里插入图片描述

左边上下两图是同构的,右边上下两图也是同构的。
在这里插入图片描述
在这里插入图片描述

说明:

  • 图之间的同构关系具有自反性对称性传递性

  • 能找到多条同构的必要条件,但它们都不是充分条件:

    边数相同,顶点数相同

    度列数相同(不计度数的顺序)

    对应定点的关联集及领域的元素个数相同,等等

  • 若破坏必要条件,则两图不同构

  • 至今没有找到判断两个图同构的多项式时间算法

例题:

(1)在这里插入图片描述

A 同构 B 不同构

(2)在这里插入图片描述

A 同构 B 不同构

(3)在这里插入图片描述

A 同构 B 不同构

答案:(1)A (2)A (3) B

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?