矩阵是一种纵横排列的二维数据表格。由于矩阵所具有的这种二维性质（行列可以分别表示图中的顶点、边亦或是图中的圈），矩阵恰好可以成为研究图中的一些性质的一种重要工具，譬如：图的遍历，图的同构等等。矩阵的运用对于更好地理解图，加深对图的理解具有重要意义。另外在一些问题中的矩阵表达方式，前人总结的经验和定理，我们需要有效地运用与传承。矩阵如果运用好了，在一定程度上会带来我们求解问题的便利，实际上也提供了我们解决问题的一条捷径。

但是，遗憾的是，从文献资料上来看，大部分的学者只是将矩阵作为图的一种表示方式，譬如，邻接矩阵，关联矩阵。很少有人去探讨、研究这些根据图所得到的矩阵真正意味着什么，它们是否可以帮助人们更好的解决图论中一些用常规手段不是很容易得到答案的问题。

本文将重点介绍图的邻接矩阵，关联矩阵，圈矩阵和长度矩阵在除了表示图以外的其他应用。通过这些矩阵的一些性质，来更好的解决一些图中使用常规解法不容易解决的问题，同时也为矩阵在图论中发挥更大的作用提供一些思路。

本文结构安排：第2部分介绍图与矩阵的基本知识。第3部分介绍邻接矩阵及其在图论中的应用。第4部分介绍关联矩阵及其在图论中的应用。第5部分介绍圈矩阵及其在图论中的应用。第6部分介绍长度矩阵及其在图论中的应用。

2  图与矩阵的基本知识

2.1 图的基本概念

我们称数学结构 为一个图，其中 是非空集合， 是从集合 到 的一个映射，则称 是一个以 为顶集合，以 为边集合的图， 中的元素称为图 的顶点， 中的元素称为 的边， 称为 的关联函数。若 ， ，则简写成 ；称 是有向边 的尾， 为有向边 的头。若 ， ， ， 时，称 为有限图，否则为无限图。本文中只谈论有限简单连通图。

下面我们要不厌其烦的对图论的术语下定义。如果不写“有向”两个字，我们下面的图皆指无向图。

（1）边的端点： 时，称顶 和 是边 的端点。

（2）边与顶相关联：若边 的端点是 和 ，则称 与 ， 相关联。

（3）邻顶：同一条边的两个端点叫做邻顶。

（4）邻边：与同一个顶相关联的两条边叫做邻边。

（5）环：只与一个顶点相关联的边叫做环。

（6）重边： ，则称 与 是重边。文献综述

（7）单图：无环无重边的图。

（8）完全图：任二顶皆相邻的图。

（9）链（walk）： 中一条 链 即为 的一个顶点序列，满足：从 出发，到 结束，且连续的顶点是邻接的。

（10）迹（trail）： 中一条 迹 即为边没有被多次经过的 链。

（11）路（path）：图中的一条 链，若链中没有重复的顶点，那么它是一条 路。

（12）回路(circuit)：图 中的一个回路是一个长至少为3的闭迹，故一个回路开始和结束与同一个顶点，但没有边重复。

（13）圈（cycle）：除了第一个和最后一个顶点外，没有顶点重复的回路称为圈。

（14）度：在图 中，与顶点 相关联的边的总数称为是 的度，记为 ；若不致引起混淆，可简记为 。

2.2 矩阵的基本概念

矩阵是一些数的矩阵表格，经常用大写字母来表示。矩阵内的数称为元素，这些数的水平列表称为矩阵的行，竖直列表称为矩阵的列。一个 行 列的矩阵的维数记作 。若 ，矩阵称为方阵。在第 行第 列的元素称为 元素，其地址记为 。若矩阵用 表示，则我们就用 表示其 。

一个 的矩阵 的抽象表示如下图所示：