学习笔记 (5)

       又要介绍概念了，其实连我自己都没有理解这些定义，居然还写出来实在是误人子弟了，所以大家如果看到不对的地方大可不必大惊小怪。去Google上搜一下保证有更好的解释。开始。

       图中节点的度是以该节点最为端点的边的条数。

       图论与关联矩阵之间的关系：拥有m个节点和n条边的图G=(V,E)的关联矩阵是一种m*n的矩阵，其中第i行第j列的元素是1，当且仅当节点i是边j的一个端点，否则该元素是0。通过研究可以发现任何列的表项和为2，这是因为每条边恰好有两个端点；另外，行的和是节点的度。如果节点的度是0，则说这个节点是孤立的。

       相邻矩阵：拥有m个节点和n条边的图G=(V,E)的相邻矩阵是一种m*m矩阵，其中第i行第j列的元素是1，当且仅当节点i和节点j之间存在一条边，否则该元素是0。行的和是节点的度。

       图中的路径：是一系列的边，对于序列中的任何相邻边对偶ei,ej，边都拥有相同的（节点）端点。

    另一个概念，组件：图的组件是相连节点的最大集合。

    图的另一个性质，圈数：图G的圈数由V(G)=e-n+p给出，其中：e是G的边数n是G中的节点数p是G中的组件数。

    下面介绍有向图，

    有向图中节点的内度，是将该节点作为终止节点的不同边的条数。有向图中节点的外度，是将该节点作为开始节点的不同边的条数。（呵呵，真是来而不往非礼也）。由此可见，一般图和有向图对于度的概念之间的联系是：deg(n)=indeg(n)+outdeg(n)。

    节点的类型：内度为0的节点是源节点，外度为0的节点是吸收节点。内度不为0，并且外度不为0的节点是传递节点。既是源节点又是汇节点（吸收节点）的节点是孤立节点。