[图论笔记]基本概念 什么是图 定义 一个图是由一个顶点集、一个边集和一个关系构成的三元组,其中的关系使得每一条边与两个顶点(不一定是不同的顶点)相关联,并将这两个顶点称为这条边的端点。 一个圈是两个端点相同的一条边。重边是具有同一对端点的多条边。 简单图是不含圈和重边的图。 顶点集和边集是空集的图称为空图。 图模型 一个简单图的补图也是一个简单图,其顶点集为,且当且仅当。 团是图中两两相邻的顶点构成的集合。独立集(或稳定集)是图中由两两互不相邻的顶点构成的集合。