视频字幕
图论是数学的一个重要分支，研究由顶点和边组成的图结构。图G由顶点集合V和边集合E组成。顶点的度数是连接到该顶点的边数。路径是连接顶点的序列，而回路是起点和终点相同的特殊路径。
图有三种主要的表示方法。邻接表为每个顶点存储其相邻顶点的列表，空间效率高。邻接矩阵是n乘n的矩阵，元素为1表示顶点间有边连接，查询效率高。关联矩阵是顶点乘边的矩阵，表示顶点与边的关联关系。不同表示方法适用于不同的应用场景。
邻接矩阵具有重要的数学性质。对于无向图，邻接矩阵是对称的。矩阵的幂运算有特殊含义：A的平方中元素A²[i][j]表示从顶点i到顶点j长度为2的路径数量。拉普拉斯矩阵L等于度数矩阵D减去邻接矩阵A，它的特征值揭示了图的连通性和其他重要性质。
图同构是图论中的核心概念。两个图同构意味着存在顶点间的双射函数，保持邻接关系不变。判断同构需要检查同构不变量，如顶点数、边数、度数序列和连通性。这里展示的两个图虽然看起来不同，但通过适当的顶点重新标记，可以证明它们是同构的。
图的分解是分析复杂图结构的重要方法。连通分量分解将图分解为最大连通子图，每个分量内部顶点相互可达。强连通分量分解适用于有向图，找出相互可达的顶点集合。树分解将图结构化为树形，便于算法设计和优化。这些分解方法在图算法中有广泛应用。