图论基础：连通性、同构与路径

本PPT聚焦于图论(graph theory)的基本概念与性质，它是一种数学工具，用于研究由顶点（vertices）和边（edges）构成的结构。在图论中，一个图通常表示为G={V,E}，其中V是顶点集合，包含n个元素，记作{v1, v2, ..., vn}，n>=1；E是边的集合，由m对有序对组成，如{(vi1, vj1), (vi2, vj2), ..., (vim, vjm)}，m>=0。图的大小或基数（cardinality）即为顶点数量，记为|G|=n。 每个顶点的度（degree）指的是与之相连的边的数量。在邻接矩阵中，一个n×n的矩阵用0和1来表示哪些顶点之间有边连接，对于多图，非零值可以是其他整数，比如2、3或4，代表多条边存在。 图的同构性（isomorphism）是指两个图具有相同的边结构，即使顶点的标记不同，其连接关系保持不变。例如，环（loop）指的是一个顶点自身相连的边，而路径（walk）是一系列连续的顶点和边组成的序列，但不考虑重复。 一条路径（path）则是无重复顶点的走法，而在连通图中，任何两个顶点间都存在至少一条路径，这是连通性的基本定义。环路或循环（circuit）则指路径结束于起点的特殊情况。图论中有两种特别重要的路径：欧拉路径（Eulerian path）和欧拉环（Eulerian cycle），它们要求所有边恰好被遍历一次；哈密顿路径（Hamiltonian path）和哈密顿环（Hamiltonian cycle）则是所有顶点恰好被访问一次的路径或环。 在讨论图形类型时，我们引入了有向图（directed graphs）。有向图中的每条边都有方向，每个顶点具有入度（incoming edges）和出度（outgoing edges）。有向图中特别强调的是无环图（acyclic graphs），即不存在从某个节点出发能回溯到该节点的路径，这样的图没有自环，也没有回路。 此外，还提到了无向图与有向图的区别，以及关于图论在实际应用中的重要性和可能性，如网络分析、计算机科学中的算法设计等。这PPT为理解基础图论提供了全面且清晰的框架。