type
status
date
slug
summary
tags
category
icon
password
From BarryZed
基本概念
阶数
即顶点数（n）
顶点（V）
度数
点接到一个顶点上的边数（）
- 入度：该顶点为终点（）
- 出度：该顶点为起点（）
：最小度
：最大度
悬挂顶点
- 度数为1
- 该边为悬挂边
边数
字母表示：m
正则图
所有顶点度数相同
子图、母图与补图
相当于
集合、该集合的子集、子集的补集
补图的字母表示：
生成子图：所有顶点都有
导出子图：选几个边，自动带出有关点的图
图的连通性
割集
删除一些顶点或边使图不连通
删除的点形成的集合为点割集，若点唯一，则称该点为割点
删除的边形成的集合为边割集，若边唯一，则称该点为割边或桥
连通度
删除多少个点或边使图不连通或仅剩一个点
删除的点称为点连通集（）
删除的边称为边连通集（）
连通图/弱连通图
去向后没有孤立的点的有向图
有向时任意节点单向可达：单向连通图
有向时任意节点双向可达：强连通图
图的矩阵表示
邻接矩阵
两点间有几条通路（有向）
可达矩阵
邻接矩阵+对角线全为1
可达矩阵的几次方就是几步可达
写可达矩阵：十字架走一遍
欧拉图
有欧拉回路的图
欧拉回路
一笔画完走的路（走过所有边）
欧拉通路
一笔画完的路，并最后回到起点
无向图为欧拉图
=
G为连通图且无奇数度顶点
无向图有欧拉通路，但没有欧拉回路
=
无向图为连通图，且有两个奇度顶点
=
每条欧拉通路都以这两个点为端点
有向图为欧拉图
=
连通图且所有顶点
哈密顿图
有哈密顿回路的图
哈密顿通路
过每个顶点一次把图串起来
哈密顿回路
过每个顶点一次把图串起来，并最后回到起点
平面图
边没有相交
极大平面图
- 连通
面的次数都为3
面的次数：该面是有几条边围成的(deg)
欧拉定理
r：面数
k：连通分支数（几块大陆）
G为连通的平面图，每个面的deg至少为
对偶图
把每个面当点，拆掉每一面墙
- 作者:BarryZed
- 链接:
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
