OI Wiki 图论相关概念
图论相关概念 图论相关概念 目录
相邻
简单图
子图
连通
无向图
有向图
稀疏图/稠密图
反图
特殊的图
同构
无向简单图的二元运算
特殊的点集/边集
支配集
边支配集
独立集
匹配
点覆盖
边覆盖
本页面概述了图论中的一些概念,这些概念并不全是在 OI 中常见的,对于 OIer 来说,只需掌握本页面中的基础部分即可,如果在学习中碰到了不懂的概念,可以再来查阅.
图论相关定义在不同教材中往往会有所不同,遇到的时候需根据上下文加以判断.
图 (graph) 是一个二元组 .其中 是非空集,称为 点集 (vertex set),对于 中的每个元素,我们称其为 顶点 (vertex) 或 节