科数网
学习首页
高中数学
高中物理
微积分
线性代数
概率论
赞助
在线教程
图论
图的基本概念
最后更新:
2024-04-06 18:18
查看:
46
次
下载
编辑本文
科数网
图的基本概念
## 图的基本概念 元素的无序对 $\{x, y\}$ 称为无序偶, 也记作 $(x, y)$ 。显然 $(x, y)=(y, x)$ 。 $\{(x, y) \mid x \in A, y \in B\}$ 称为集合 $A$ 与 $B$ 的无序积, 记作 $A \& B$ 。 元素可以有重复的集合称为多重集合。例如 $\{a, b, b\}$ 。 定义 1 一个无向图 $G$ 是一个有序二元组, 记作 $G=\langle V, E>$; 非空有限集合 $V$ 称为顶点集或结点集, 其元素称为顶点或结点; $E$ 是 $V \& V$ 的多重子集, 称为边集, 其元素称为无向边或边。 定义 2 一个有向图 $D$ 是一个有序二元组, 记作 $D=\langle V, E\rangle$; $V$ 是无向图的顶点集,边集 $E$ 是 $V \times V$ 的多重子集, 其元素称为有向边或边。若 $\langle u, v\rangle$ 为有向边, 则称 $u$ 为起点, $v$ 为终点。 若 $(u, v) \in E$ (或 $\langle u, v>\in E$ ), 则记作 $e=(u, v)$ (或 $e=\langle u, v\rangle$ ), 称 $u$ 和 $v$ 为边 $e$ 的端点, 称 $e$ 与 $u$ 和 $v$ 相互关联; 与同一条边关联的两个结点称为相邻, 有公共结点的两条边也称为相邻; 无边关联的结点称为孤立点; 端点重合的边称为环; 若关联一对结点的边多于一条, 则称这些边为平行边 (对有向图还要要求有向平行边的方向一致)。 $|V|=n,|E|=m$ 的图称为 $(n, m)$ 图, 也称为 $n$ 阶图, 记作 $G=(n, m) ;(n, 0)$ 图称为零图; $(1,0)$ 图称为平凡图; 具有平行边的图称为多重图; 不含环和平行边的图称为简单图; 将无向图 $G$ 的每条无向边均加上一个方向所得的有向图称为 $G$ 的定向图。 用平面上的点代表图的结点, 用连接相应结点而不经过其他结点的线 (直线或曲线)代表边, 即得图在平面上的图解。点的位置、线的形状都有很大的随意性, 一个图可以有各种外形上差别很大的图解.
上一篇:
没有了
下一篇:
结点的度与子图
本文对您是否有用?
有用
(
0
)
无用
(
0
)
科数网知识库旨在打造一个可以顺序阅读的在线电子学习教程,点击顶部的
编辑本文
来完善本文,如果本文对您有用,也欢迎
赞助我们
0
篇笔记
写笔记
更多笔记
提交笔记