图矩阵(graph matrix),理学-数学-图论-超图,图矩阵主要包括关联矩阵和邻接矩阵,在离散数学中即用矩阵来表示图。关联矩阵(incidence matrix)设图的顶点集为,边集为,则的关联矩阵是一个矩阵,式中是指和相关联的次数(0,1,或2)。图的关联矩阵正是描述该图的另一种方式。具有如下性质:①每列元素之和等于2,所有元素之和等于。②第行元素之和等于顶点的度。③第行元素全为0,当且仅当为孤立点。④若图为简单连通图,那么的秩为。若是无自环的有向图,也可以定义其关联矩阵。记的顶点集为,弧集为,则的关联矩阵是一个矩阵,且满足:若与不关联,则;若是的尾,则;若是的头,则。具有如下性质:①每列元素之和等于0,所有元素之和等于0。②第行值为1的元素个数等于顶点的出度,值为-1的元素个数等于顶点的入度;③中值为1的元素个数等于值为-1的元素个数,即为图中弧的条数。