图论入门

符号与定义

基础定义：

• 重边：端点和方向（有向图）完全相同的边称为重边。

  • 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\) 边双连通。一个点和它自身点双连通，但由一条边直接相连的两点不一定边双连通。