1 概念定义
入度是图论中的基本度量之一，主要用于有向图，用来表示某个顶点“被指向”的次数。它能够反映顶点在局部结构中的受入连接强度，因此在路径分析、层次关系判断和网络建模中都具有基础作用。
1.1 有向图中的入度
在有向图中，若一条有向边从顶点 \(u\) 指向顶点 \(v\)，则称这条边对 \(v\) 的入度作出一次贡献。顶点 \(v\) 的入度记作 \(d^-(v)\)，表示所有终止于 \(v\) 的有向边条数。
例如，若某顶点有三条边分别从不同顶点指向它，则它的入度为 3。入度只统计“进入”该顶点的边，不考虑这些边从哪里发出。
1.2 无向图与入度的关系
在无向图中，边不具有方向，因此通常不使用“入度”这一术语，而是直接讨论顶点的度。若在某些分析中将无向边临时赋予方向，那么入度和出度会随方向设定而变化，但这已超出无向图本身的原始定义。
因此，入度概念本质上属于有向图理论。在没有方向信息的图结构里，对应的基本量是顶点度，而不是入度。
1.3 顶点、边与方向的基本术语
在讨论入度时，通常需要先明确几个基础概念。顶点是图中的基本元素，边是连接顶点的线段或弧；在有向图中，边具有起点和终点，分别对应“出发”和“到达”的方向。
若一条边从 \(u\) 指向 \(v\)，则 \(u\) 是该边的起点，\(v\) 是终点。凡是以某顶点为终点的有向边，都会计入该顶点的入度。若一条边的起点和终点相同，即形成自环，则它同时从该顶点出发又回到该顶点，计数时需要特别处理。
2 计算方式
入度的计算方法取决于图的表示方式。对于规模较小的图，可以直接逐条统计；对于计算机处理中的图结构，常用邻接矩阵或邻接表进行高效计算。
2.1 直接计数法
直接计数法是最直观的方法，即逐一查看所有有向边，统计有多少条边的终点是目标顶点。若图中边数较少，这种方法简单明了，适合手工计算。
例如，在一张有向图中，若顶点 \(v\) 的所有入边分别来自 \(a\)、\(b\)、\(c\)，则 \(v\) 的入度为 3。若存在重复边，则每一条重复边都应单独计入。
2.2 邻接矩阵法
邻接矩阵是表示有向图的常用方式。若图有 \(n\) 个顶点，则可用一个 \(n \times n\) 的矩阵表示边的连接情况。矩阵中元素的数值反映顶点之间是否存在边，以及边的条数。
2.2.1 矩阵列和与入度
在常见约定下，邻接矩阵的第 \(i\) 行第 \(j\) 列元素表示从顶点 \(i\) 指向顶点 \(j\) 的边数。于是，某个顶点的入度可以通过该顶点对应列的元素求和得到。
也就是说，若第 \(j\) 列中所有元素之和为 \(k\)，则顶点 \(j\) 的入度就是 \(k\)。这一方法便于程序化处理，也便于在矩阵框架下统一分析图结构。
2.2.2 多重边与自环的处理
若图中允许多重边，邻接矩阵中的元素可以大于 1，用以表示同一对顶点之间的多条有向边。在计算入度时，这些边的条数都要累加。
对于自环，即从某顶点指向自身的边，邻接矩阵的对角线元素会记录这类边的数量。自环对入度的贡献通常按其边数计算，因此一个自环一般会对该顶点的入度贡献 1。
2.3 邻接表法
邻接表法通过为每个顶点保存其所有出边列表来表示图。由于入度是“被指向”的边数，因此在这种表示中，若要直接求入度，通常需要额外维护一个统计数组，或反向遍历所有邻接表。
常见做法是建立一个入度数组：每读入一条从 \(u\) 到 \(v\) 的边，就将 \(v\) 的入度加 1。这样无需在统计阶段重复扫描整个图，适合动态构建和大规模数据处理。
3 性质与定理
入度不仅是局部特征量，还与图的整体结构密切相关。很多关于有向图的基本结论，都可以通过入度与出度的关系推导出来。
3.1 入度与出度的关系
与入度相对应的是出度，表示一个顶点发出的有向边条数。对同一顶点而言，入度和出度分别描述其作为“接收者”和“发送者”的角色。
在同一张有向图中，某顶点的入度和出度可以相等，也可以差异较大。它们的具体大小取决于顶点在图中的位置、方向结构以及是否存在回路、自环等情况。
3.2 全图入度总和定理
有向图中的一个基本性质是，全图所有顶点入度之和与边的总数存在直接对应关系。这一结论在图论证明和算法设计中经常使用。
3.2.1 入度总和等于边数
在不考虑特殊计数约定时，每一条有向边都会恰好为其终点提供 1 次入度贡献。因此，把全图所有顶点的入度相加，结果等于图中的边数。
这一性质体现了“每条边只被终点统计一次”的原则，是入度最基本、也最常用的整体恒等式之一。
3.2.2 含自环图中的修正
若图中含有自环，具体计数方式需保持统一。按照常规定义，自环的终点仍是该顶点本身，因此它对入度的贡献按 1 计算。只要沿用这一规则，全图入度总和仍等于边数。
需要注意的是，在不同教材或软件实现中，可能对自环在邻接矩阵中的表示方式有细微差异，但只要入度的定义保持一致，总和关系就不会改变。
3.3 极端情况分析
当某顶点没有任何入边时，它的入度为 0，这类顶点常见于有向图的起始层或源点附近。若某顶点的入度特别高，则说明它在图中接收连接较多，往往具有更强的汇聚特征。
在极端情况下，若整张图没有任何边，则所有顶点的入度均为 0。若图中只有自环，则相应顶点的入度完全由自环决定。
4 特殊图中的入度
不同类型的有向图对入度的含义和计算会有不同影响。了解这些特殊情形，有助于正确处理理论问题和实际计算。
4.1 简单有向图
简单有向图通常指不含重边、也不含自环的有向图。在这种情况下，任意一对顶点之间至多存在一条方向确定的边。
对于简单有向图，入度的计算最为直接：只需统计所有指向该顶点的不同边即可。由于不存在重复边和自环，结构更规整，很多基本定理也更容易表述。
4.2 多重有向图
多重有向图允许同一对顶点之间存在多条同向边。此时，入度不再只是“有无连接”的问题，而是要精确统计边的数量。
如果有三条边同时从 \(u\) 指向 \(v\)，那么它们都会对 \(v\) 的入度各贡献 1。多重边的存在使入度能够反映连接强度的差异，这在某些网络模型中具有实际意义。
4.3 含自环的有向图
含自环的有向图中，顶点可以通过一条边指向自身。自环会同时影响路径结构与度的统计，因此在分析中需格外注意。
通常情况下，自环对所在顶点的入度贡献 1，同时也对出度贡献 1。若图中存在多个自环，则应按各自条数分别计入，不能合并忽略。
4.4 完全有向图
完全有向图是指任意两个不同顶点之间都存在方向相反的两条边，即双向连接。若没有自环，则每个顶点都会从其余所有顶点接收一条边。
在这种图中，若共有 \(n\) 个顶点，则每个顶点的入度都为 \(n-1\)。这是一个高度对称的结构，常用于作为图论中的标准模型。
5 入度的应用
入度不仅是定义层面的量，也广泛应用于算法、结构分析和网络建模之中。它常常作为判断先后顺序、衡量依赖关系的重要指标。
5.1 拓扑排序
拓扑排序是有向无环图中的经典问题，目标是给顶点安排一个线性顺序，使每条边的起点都排在终点之前。入度在这一过程中起到核心作用。
5.1.1 零入度顶点的作用
在拓扑排序中，入度为 0 的顶点通常被视为当前阶段可以优先处理的对象，因为它们不依赖于任何前驱顶点。算法常从这些顶点出发，逐步移除它们及其外出边。
当一个顶点的所有入边都被删除后，它的入度会降为 0，此时它也可以进入待处理队列。这个机制使入度成为维护“可选顶点集合”的关键指标。
5.1.2 DAG中的排序过程
在有向无环图中，拓扑排序通常借助入度数组实现。初始时将所有零入度顶点入队，随后每取出一个顶点，就将其所有后继顶点的入度减 1。
若某后继顶点的入度减为 0，则说明它已不再依赖未处理顶点，可以继续加入队列。重复这一过程，最终得到一个符合边方向约束的排列。
5.2 图的连通性分析
入度可以帮助判断有向图的局部可达性和连接倾向。若某顶点入度很高，通常意味着它被许多路径或边所指向，可能处于结构中的汇集位置。
在连通性分析中，入度常与出度结合使用，以判断图是否存在孤立点、源点、汇点或分层结构。虽然入度本身并不能完全决定连通性，但它是重要的辅助特征。
5.3 网络与信息流模型
在信息流、任务依赖和资源传递模型中，入度常用来表示一个节点接收外部输入的数量。比如在任务调度中，一个任务的入度可视为其前置任务数。
这种视角下，入度越大，通常说明该节点越依赖外部条件；入度为 0 的节点则往往可作为系统的起始处理单元。由于这种解释直观，入度在工程建模中应用十分广泛。
5.4 社交网络与关系建模
在社交网络中，入度可用来描述某个对象被关注、被引用或被指向的频率。例如，在“关注”关系图中，某用户的入度可以理解为其关注者数量。
这种指标常被视为节点受欢迎程度或影响力的一个近似描述。但需要注意，入度只是结构上的统计量，不能单独代表所有语义层面的社会意义。
6 相关概念
入度并不是孤立存在的概念，它与多种图论术语相互关联。理解这些概念的区别，有助于避免混淆。
6.1 出度
出度是与入度完全对应的概念，表示某顶点发出的有向边条数。若说入度描述“被连接”，那么出度描述的就是“连接出去”。
在很多算法中，入度与出度会同时使用。例如，构造拓扑排序时主要依赖入度，而在遍历邻接结构时则常直接处理出边。
6.2 度
度是更一般的图论概念，在无向图中表示与顶点相连的边数。在有向图中，度有时可以理解为入度与出度之和，具体取决于所采用的定义体系。
因此，度包含的信息比单独的入度更全面，但在方向性分析中，入度和出度往往比总度更有解释力。
6.3 半度
半度是有向图中对入度或出度的另一种称呼，强调它只反映度的一部分。使用这一术语时，通常是为了与无向图的“度”作区分。
在一些教材中，入度和出度会被统称为两个半度，便于说明有向图中连接关系的双向统计性质。
6.4 邻接与关联
邻接表示两个顶点之间存在边或方向上的联系；关联则更强调边与顶点之间的从属关系。入度正是通过“哪些边关联到该顶点”为基础来定义的。
从本质上看，入度是对顶点关联边的一种数量化描述，而邻接则是更基础的结构关系描述。二者配合使用，可以更完整地刻画图的局部形态。
7 常见题型与例子
在图论学习与考试中，入度相关题目通常包括直接计算、性质证明和综合应用三类。它们分别考查概念理解、推理能力和算法意识。
7.1 典型计算题
典型计算题通常给出一张有向图，要求分别求出若干顶点的入度，或列出全图各顶点的入度数组。解题时应先确定每条边的方向，再统计终点数量。
例如，若边集为 \(a \to b\)、\(c \to b\)、\(d \to a\)，则 \(a\) 的入度为 1，\(b\) 的入度为 2，\(c\) 与 \(d\) 的入度为 0。此类题目重在细致，不可将出边误算为入边。
7.2 证明题
证明题常围绕“入度总和等于边数”等基本结论展开，要求说明为何每条边在统计中恰好被计算一次。证明时一般采用按边分类或按顶点求和的方法。
另一些证明题会结合拓扑排序，要求说明有向无环图中必存在入度为 0 的顶点。此类结论往往需要从反证或结构递推角度入手。
7.3 综合应用题
综合应用题常将入度与算法、模型或图结构结合，例如给出一个任务依赖关系图，要求判断执行顺序、寻找可并行处理的节点，或分析某些顶点是否可能成为源点。
在这类问题中，入度不仅是一个计算量，更是决策依据。正确理解其含义，往往能帮助快速识别图中的起点、层次关系以及约束传播方向。