图论部分简介
图论（graph theory） 是数学的一个分支，它以 图 为研究的对象。
图论本身是应用数学的一部分，历史上图论曾经被很多数学家各自独立建立过。关于图论的最早文字记载最早出现在欧拉 1736 年的论著中，也就是著名的柯尼斯堡（Konigsberg）问题（七桥问题）。
图的定义¶
一个图 是一个二元组，即序偶 ，或记作 ，其中 是有限非空集合，称为 的顶点集， 中的元素称为顶点或结点； 称为 的边的集合， ，都有 中的结点与之对应，称 为 的边。
简单来说，就是图 就是一个结点的集合 和边的集合 ，其中任意一条边都可以表示为两个结点之间的关系。若 表示为 ，则有 。
有向边和无向边¶
以上定义的结点对 可以是有序的，也可以是无序的 。如果边 和结点无序对 相对应，则称 为无向边，记作 ，称 为边 的两个端点。
如果边 和结点有序对 相对应，则称 为有向边，记为 ，称 为边 的 始点 ， 为该边的终点。
简单来说，如果边对结点的关系是双向的，那么这条边是无向边；如果是单向的，那么这条边是有向边。
图的基本概念¶
无向图：每条边都是无向边的图。
有向图：每条边都是有向边的图。
混合图：在一个图中，有些边是有向边，另一些边是无向边，则该图为混合图。
有限图：一个图的点集和边集都是有穷集的图。
零图：边集为空集的图。
平凡图：仅有一个结点而没有边构成的图。
关联：若有 且 ，则称 是和 相关联的。
孤立点：无边关联的点。
自环：若一条边所关联的两个结点重合，则称此边为自环。
邻接：关联于同一条边的两个点 和 称为邻接的；关联于同一个点的两条边 和 是邻接的（或相邻的）。
结点的度数¶
设图 为一个有向图， ，关联于结点 的 边 的条数，称为点 的度数，记作 。
注意：一个自环为它的端点增加 2 度。
当图 为一个有向图， ，称以 作为始点的边数之和称为结点 的出度，记为 。将以 作为终点的边数之和称为结点 的入度，记为 。称以 作为端点的边数之和为结点 的度数或度，记为 。
显然， 。
定理 1¶
推论：在任意图中，度数为奇数的点必然有偶数个。
定理 2¶
即所有点入度之和等于出度之和。
子图的概念¶
设有图 和图 。
如果 ，则称 是 的子图，记作 。
如果 ，即 或 ，则称 是 的真子图，记作 。
如果 ，则称 是 的生成子图。
如果 且 ，以 为结点集，以两端点均在 中的边为边集的 的子图，称为 导出的 的子图，简称为 的导出子图。
如果 使得 ，且 中仅包含 中的边所关联的结点，则称 是子图 相对于原图 的补图。
特殊的图¶
树：边数比结点数少一的连通图。更多内容，详见树相关基础。
森林：由 棵（ ）互不相交的树组成的图。
基环树：边数和点数相等的连通图。
仙人掌：每个结点至多在一个简单环上的图。
在无向图中，关联一对顶点的边多于 1 条，则称这些边为重边（平行边），重边的条数称为重数。
简单图：不含重边和自环的图。
多重图：含重边的图。
完全图：每对不同的顶点之间都恰连有一条边相连的简单无向图。容易证明， 个顶点的完全图有 条边。
竞赛图：通过在完全图中为每条边分配方向而获得的有向图。
参考资料¶
离散数学（修订版），田文成 周禄新 编著，天津文学出版社，P184-187
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用