图论入门
符号与定义
基础定义：
-
重边：端点和方向（有向图）完全相同的边称为重边。
- example:
- 1 2
- 1 2
-
自环：自己连接自己的边称为自环。
- example:
- 1 1
- 1 1
相邻相关：
- 出边 & 入边
- 从 \(u\) 出发的边称为 \(u\) 的出边；到达 \(u\) 的边称为 \(u\) 的入边。
- 出度 & 入度
- 从 \(u\) 出发的边的数量称为 \(u\) 的出度；到达 \(u\) 的边的数量称为 \(u\) 的入度。
连通性相关：
- 弱联通：对于有向图的两点 \(u,v\)，若将有向边改为无向边后 \(u,v\) 连通，则称 \(u,v\) 弱连通。
- 连通分量：无向图 \(G\) 的极大连通子图叫做 \(G\) 连通分量。
- 割点：在无向图中，删去后使得连通分量数量增加的节点叫做割点。
- 割边（桥）：在无向图中，删去后使得连通分量数量增加的边叫做割边（桥）。
- 点双连通图：不存在割点的无向连通图称为点双连通图。孤立点和孤立边均为点双连通图。
- 边双连通图：不存在割边（桥）的无向连通图称为边双连通图。孤立点是边双连通图，但是孤立边不是。
- 点双连通分量：一张图的极大点双连通子图称为点双连通分量，简称点双。
- 边双连通分量：一张图的极大边双连通子图称为边双连通分量，简称边双。
- 点双连通：若 \(u,v\) 处于同一个点双连通分量，则称 \(u,v\) 点双连通。一个点和它自身点双连通。由一条边直接相连的两点也是点双连通。
- 边双连通：若 \(u,v\) 处于同一个边双连通分量，则称 \(u,v\) 边双连通。一个点和它自身点双连通，但由一条边直接相连的两点不一定边双连通。