type
status
date
slug
summary
tags
category
icon
password
已整理
无向图与有向图
多重集
集合中允许元素重复出现
无序积
无向图
边用（）表示
有向图
边用<>表示
V：点集，E：边集
n阶图
有n个顶点的图
零图
没有边的图
平凡图
一阶零图（孤立点）
度
- 无向图中：顶点作为端点的次数
- 有向图中：出度与入度之和（）
出度与入度
- 出度：
- 入度：
握手定理
图，边数，则有
入度和=出度和=边数
推论
度数为奇数的顶点个数为偶数
多重图和简单图
平行边
- 无向图：关联同一对顶点大于一条的边
- 有向图：起点与终点相同的大于一条的边
多重图
含平行边的图
简单图
没有平行边也没有自环的图（有向图可以有环，不是自环）
重数
平行边的条数
同构
两个图中的顶点靠一个双射函数（一一对应）映射，其他属性相同。
可以理解为图的变形
满足自反性、对称性和传递性
充分条件
每个顶点的度（入度和出度）一样，有向图要考虑方向
不同构原因
- 度不同
- 方向不一样
- 找不到双射函数
完全图
每两点间都有边
- 无向完全图：图中任何顶点都与其他个顶点相连，记作
- 有向完全图：在无向完全图的基础上补全逆向边
子图
对于，若，则是的子图，记作
真子图
但
生成子图
且
例
导出子图
从的顶点集的一个子集以及中所有端点都在中的边所构成的子图。导出子图完全由决定，因此也称为导出的子图，记作。
类似可定义由边导出的子图。
即选定一些要素，将这些要素关联的部分抽离出来，组成的子图。
补图
所有使成为完全图的添加边组成的集合为边集的图，称为的补图，记作。
通路和回路
通路
- 顶点和边的交替序列
- 分别称为起点和终点
- 若则称为回路（圈）
- 边的数量称为长度
简单与初级通路
初级通路（回路）
- 除了起点终点外：点和边都不重复
简单通路（回路）
- 边不重复
- 点可重复
复杂回路
- 边重复
连通
无向图中：
- 两点间存在通路
- 可达
无向图中的连通图
所有点都是连通的或者只有一个点
顶点中的连通关系是等价关系
连通关系
是上的等价关系
连通分支
关于联通关系的等价类的导出子图
有向图中：
弱连通图（连通图）
忽略方向之后是连通图（无向连通）
单连通图
任意两个顶点至少一个可达另一个（单向连通）
强连通图
任意一对顶点相互可达（双向连通）
删除
- : 从中删除及关联的边。
- : 从中删除中所有的顶点及关联的边。
- : 从中删除。
- : 从中删除中所有边。
点割集
无向图中
在一个点集中，去掉相应的点和所相连的边后能改变图的连通性。
这样的点集中，其所有真子集都不能满足上述性质，即为点割集。
例：
边割集
与点割集类似，只去边。
矩阵表示
关联矩阵
无向图
- 值域：
- 列为顶点，行为边
- 值为2：自环
例：
性质
- 每列恰好有两个1或一个2（起点和终点）
- 第行元素之和为度数（）
- 所有元素之和为2m，即总度数为2m（握手定理）
- 为孤立点第行全为零
有向图
- 值域：
- 要求有向图不含自环
- 起点为1，终点为-1，其他为0
- 所有元素和为零
例
有向图的邻接矩阵
- 值域：，取决于具体两点间有多少边
- 行为起点，列为终点，先行后列
- 对角线为0，除非有自环
- 所有元素之和为边数
例
求通路回路数
注意这里不是逻辑加，即值域可以大于2
- 通路：所有元素和
- 回路：对角线元素和
例
有向图的可达矩阵
- 值域：
- 设为邻接矩阵，为可达矩阵，阶数为，则有
其中求和为逻辑加
