连通图

子图

type: concept tags: [图论, 图, 子图] created: 2026-05-04 updated: 2026-05-04子图定义子图是原图的一个子集，包含原图的部分节点和边（这些边必须连接子图中的节点）。常见类型生成子图：包含原图所有节点的子图导出子图：包含选定节点及其所有相连的边连通子图：子图中任意两节点间有路径相关概念[[图]]：子图的主体[[连通图]]：连通子图

弱连通图

type: concept tags: [图论, 图, 有向图, 弱连通图] created: 2026-05-04 updated: 2026-05-04弱连通图定义弱连通图是指有向图忽略边的方向后，变成的无向图是连通的。核心特性仅适用于有向图强连通图一定是弱连通图，反之不成立弱连通分量：忽略方向后的连通分量相关概念[[有向图]]：弱连通图仅适用于有向图[[连通图]]：忽略方向后的对应概念[[强连通图]]：更严格的连通性[[强连通分量]]：有向图的极大强连通子图

强连通图

type: concept tags: [图论, 图, 有向图, 强连通图] created: 2026-05-04 updated: 2026-05-04强连通图定义强连通图是指有向图中任意两个节点都互相可达（从 u 到 v 和从 v 到 u 都有路径）。核心特性仅适用于有向图强连通分量：极大的强连通子图 → [[强连通分量]]强连通图只有1个强连通分量（自身）相关概念[[有向图]]：强连通图仅适用于有向图[[连通图]]：无向图的对应概念[[强连通分量]]：有向图的极大强连通子图[[弱连通图]]：忽略方向后的连通性

无向图

type: concept tags: [图论, 图, 无向图] created: 2026-05-04 updated: 2026-05-04无向图定义无向图是由节点（顶点）和无向边组成的图结构，每条边没有方向，通常用无序对 {u, v} 表示，意为连接节点 u 和节点 v 的边。核心特性边无方向：边 {u, v} 与 {v, u} 是同一条边节点的度（连接的边数）= 入度 + 出度（无向图中两者等价）常见类型：连通图、树（无环连通无向图）相关概念[[图]]：无向图是图的一种[[有向图]]：对比类型（边有方向）[[度]]：无向图节点的度[[连通图]]：无向图的特殊类型

连通分量

type: concept tags: [图论, 图, 连通分量] created: 2026-05-04 updated: 2026-05-04连通分量定义连通分量是无向图中极大的连通子图（即不能再添加更多节点而不破坏连通性）。核心特性无向图的连通分量是互不相交的连通图只有1个连通分量（自身）非连通图有多个连通分量相关概念[[连通图]]：连通分量的主体[[子图]]：连通分量是特殊的子图[[强连通分量]]：有向图的对应概念[[DFS]]：用于寻找连通分量

index

Harness Engineering Wiki - 内容索引本页面由 Claude 自动维护，每次 ingest 新资料后更新📊 Stats总页面数: 151实体页: 2概念页: 81摘要页: 62对比页: 6最后更新: 2026-05-09📚 摘要页 (Summaries)| 页面链接

图论术语-总结

type: summary tags: [图论, 数据结构, 算法基础, 术语] source: "[[raw/articles/2026/05/图论术语-原文]]" created: 2026-05-04 updated: 2026-05-04图论术语一句话简介图论基础术语详解：图的结构组成、度的概念、边节点数量关系、子图类型及连通性等核心概念。关键要点1. 图的基本结构节点 (Vertex)：图的基本组成单元，每个节点有唯一 ID边 (Edge)：连接节点的线，可以是有向或无向有向图 (Directed Graph)：边有方向，只能沿箭头方向到达无向图 (Undirected Graph)：边无方向，可双向到达（可理解为双向图）加权图 (Weighted Graph)：边带权重，可用于表示距离、成本等无权图 (Unweighted Graph)：边无权重2. 度的概念度 (Degree)：无向图中与节点相连的边的条数入度 (Indegree)：有向图中指向该节点的边数出度 (Outdegree)：有向图中从该节点指向其他节点的边数3. 边和节点的数量关系简单图 (Simple Graph)：无自环边和多重边的图边数的取值范围：$0 \leq E \leq V(V-1)/2 \approx V^2$稠密图 (Dense Graph)：$E$ 接近 $V^2$，几乎每两个节点间都有边稀疏图 (Sparse Graph)：$E$