西安电子科技大学：《离散数学》课程教学课件（题解）第七章 图论 7-3 图的矩阵表示

西安电子科技大学离散数学软件学院第四篇图论第6章图论第27-28课时6.1图的基本概念（1）-第29课时6.2路径与回路第30课时二6.3图的矩阵表示第31-32课时V6.4欧拉图与汉密尔顿图6.5平面图第33-34课时A第35课时6.6图的着色6.7 树第36-37课时E6.8图的应用第38课时

西安电子科技大学 离散数学 软件学院 第四篇 图论 6.1 图的基本概念（1） 第6章 图论 6.4 欧拉图与汉密尔顿图 6.2 路径与回路 6.5 平面图 第29课时 第33－34课时 第30课时 6.3 图的矩阵表示 第35课时 6.6 图的着色 第31－32课时 第36－37课时 6.7 树 第27－28课时 第38课时 6.8 图的应用

西安电子科技大学图的邻接矩阵的定义$6.3.1软件学院家家设G-是一个线图，结点集V={V1，V2…,邻接矩阵vn，则n阶方阵A(G)=[a]称为G的邻接矩阵。其中若[Vi,例]EE+若[Vi,]E

西安电子科技大学 图的邻接矩阵的定义 软件学院 邻接矩阵 §6.3.1

西安电子科技大学$6.3.1图的邻接矩阵的定义软件学院【例题】设G1是有向图，G2是无向图，分别如下图（a）和（b）所示，写出G1和G2的邻接矩阵。+2V3VV.00VV10001V31v0V40011001 11)

西安电子科技大学 软件学院 v4 v1 v2 v3 §6.3.1 图的邻接矩阵的定义 ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ 1100 0011 0100 0011 ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ 1101 1011 0101 1111 V1 V2 V3 V4 V1 V2 V3 V4

西安电子科技大学S6.3.2邻接矩阵的运算软件学院设G=是有向线图，IVI-n，A是G的邻接矩阵。（1）AAT的元素的意义a12a1a12an2a2xa21a2a12a.2aa2B-[baQaianαa1aL2L2若有b，a元=m(m20),则表示存在m个k使得ai和a我均等于1.aik

西安电子科技大学 §6.3.2 邻接矩阵的运算 软件学院

西安电子科技大学$6.3.2邻接矩阵的运算软件学院设G=是有向线图，IVI-n，A是G的邻接矩阵。（1）AAT的元素的意文b，表示这样的结点个数，即从和均有边引出到该结点。特别地，当时b表示的出度

西安电子科技大学 §6.3.2 邻接矩阵的运算 软件学院

西安电子科技大学$6.3.2邻接矩阵的运算软件学院家家家设G=是有向线图，IVI-n，A是G的邻接矩阵。（2）ATA的元素的意义[a1adiSCi2Cg?aaaCaaa,[aa若有6am?ag=m(m0)，则表示存在m个k使得a和a均等于1

西安电子科技大学 §6.3.2 邻接矩阵的运算 软件学院

西安电子科技大学$6.3.2邻接矩阵的运算软件学院设G=是有向线图，VI-nh，A是G的邻接矩阵。（2）ATA的元素的意义b，表示这样的结点个数，即以该结点为始点既有边引入到和又有边引入到i。特别地，当i-时b,表示的入度。+

西安电子科技大学 §6.3.2 邻接矩阵的运算 软件学院

西安电子科技大学S6.3.2邻接矩阵的运算软件学院家设G=是有向线图，IVI-n，A是G的邻接矩阵，（3）Am的元素的意义411(12C(11a12(1iCinhiC21022a21422aaia2aCnj..B=[b,]2Ck142ailai20CiCunCalCniC2Qx2若有Eaiag=m(m20),则表示存在m个k使得a和a均等于1.K-l

西安电子科技大学 §6.3.2 邻接矩阵的运算 软件学院

西安电子科技大学$6.3.2邻接矩阵的运算软件学院设G=是有向线图，VI-n，A是G的邻接矩阵，（3）Am的元素的意义b,表示从v到长度为2的路径的总数。特别地，当时表示到自身长度为2的回路的总数。K1

西安电子科技大学 §6.3.2 邻接矩阵的运算 软件学院

西安电子科技大学S6.3.2邻接矩阵的运算软件学院教家I定理」设G-为有向线图，结点集V={Vi,V2...,Vn。A=[aijlnxn为G的邻接矩阵，A(k)=[bijlnxn，则bij表示从vi到V;长度为k的路径的条数，bi为v到自身长度为k的回路条数

西安电子科技大学 §6.3.2 邻接矩阵的运算 软件学院