共2条回复
时间正序
¤ 『深蓝』(ー_ー)
19小时前
1. 图的定义
一个**图**（Graph）是一个由两个集合构成的数学结构：
- **顶点集**（Vertex Set）：记作 $ V $，表示图中的点。
- **边集**（Edge Set）：记作 $ E $，表示连接顶点的线。
形式化地，一个图 $ G $ 可表示为：
$G = (V, E)$
其中：
- 每个元素 $ v \in V $ 称为一个**顶点**（或节点，node）。
- 每个元素 $ e \in E $ 是一条**边**，它连接两个顶点。
> ✅ 注意：也写作 $ G = (V(G), E(G)) $，以明确图的组成部分。
3条评论
- 1
¤ 『深蓝』(ー_ー)
13小时前
2.有向图与无向图
1. 无向图（Undirected Graph）
定义：
一个无向图是一个有序对：
$G = (V, E)$
其中：
-$ V $ 是一个有限集合，称为顶点集（Vertex Set），元素为顶点（或节点）。
-$ E \subseteq \binom{V}{2} $，即边集是所有无序顶点对的子集，每条边连接两个不同的顶点。
注：$ \binom{V}{2} $ 表示从 $ V $ 中任取两个不同元素组成的无序对集合。
边的表示：
若 $ u, v \in V $ 且 $ u \neq v $，则边 $ e = \{u, v\} $ 是一条连接 $ u $ 和 $ v $ 的无向边。
特点：
- 边没有方向
- 若 $ \{u,v\} \in E $，则 $ u $ 与 $ v $ 相邻（adjacent）
- 图可以包含多重边（允许重复边）或自环（loop），但标准简单图不允许
2. 有向图（Directed Graph / Digraph）
定义:
一个有向图是一个有序对：
$D = (V, A)$
其中：
- $ V $ 是一个有限集合，称为顶点集
- $ A \subseteq V \times V $，称为弧集，即每条边是一个有序对
注：$ A \subseteq V \times V $，意味着边是有方向的。
弧的表示：
若 $ (u, v) \in A $，则称有一条从 $ u $ 指向 $ v $ 的有向边（或弧），记作 $ u \to v $。
- $ u $ 称为起点（tail）
- $ v $ 称为终点（head）
特点：
- 边具有方向性
- $ (u,v) \in A $ 不一定意味着 $ (v,u) \in A $
- 允许自环：$ (u,u) \in A $ 是合法的
- 允许多重弧：多个 $ (u,v) $ 可以同时存在（在多重图中）