二、图的矩阵表示、欧拉图mEnV,mnijm21miijm)deg(1imjijvm01mjijmmmnimjij2111．（无向图)关联矩阵M(G)=其中mij=vi与ej的关联次数(行为结点，列为边).(列元素之和为2)；,若,表明vi是孤立点;,即所有元素之和等于边数的2倍;设G=,具有性质：①②③④平行边的列的元素完全对应相同.mEnV,nija)deg()(11iniijmjijvaa01mjija若2．(无向图)相邻矩阵A(G)=其中aij=vi与vj相关联的边的条数(行、列均为结点).；，表明vi是孤立点;设G＝,具有性质:①A(G)是对称矩阵；②mEnV,mnijm为始点，为终点不关联与为终点为始点jijijiijvvvvvvm10,101niijm)deg(1imjijvmmmmnimjijnimjij1111)1()1(3．(有向图)关联矩阵M(D)=其中(结点为行，边为列).(列元素之和为0）；③设D＝,具有性质：①②mEnV,nijamanimjij114．(有向图)邻接矩阵A(D)=其中aij=邻接vi与vj的边的条数(与A(G)类似)(以行和列均为结点)设D=,具有性质：mEnV,nijp否则可达01jiijvvp5．(有向图)可达矩阵P(D)=其中设D=，6．欧拉通路(回路)与欧拉图通过图G的每条边一次且仅一次，而且走遍每个结点的通路(回路)，就是欧拉通路(回路).存在欧拉回路的图就是欧拉图.注：（1）欧拉回路要求边不能重复，结点可以重复.笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画.（2）欧拉图或通路的判定1)无向连通图G是欧拉图G不含奇数度结点(G的所有结点度数为偶数):(定理1)2)非平凡连通图G含有欧拉通路G最多有两个奇数度的结点；(定理1的推论)3)连通有向图D含有有向欧拉回路(即欧拉图)D中每个结点的入度＝出度4）连通有向图D含有有向欧拉通路D中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝1.(定理2)
