割
图论中，割（cut）是将图的顶点分为两不交子集的划分。割确定了割集，是两端分别在两子集中的边集，称这些边跨过（cross）了割。连通图中，割集唯一确定一个割，识别割有时是通过割集，而非顶点划分。 网络流中，s–t割指使得源与汇不在同一子集的割，其割集只含源一侧到汇一侧的边。s-t割的容量（capacity）定义为割集中所有边的容量和。 定义 割C=(S,\ T)是将图G=(V,\ E)的顶点V分为两子集S、T的划分。 割C=(S,\ T…
标签：#图的连通性
共 8 篇文章
代数连通度
，直径3，连通度1，代数连通度0.722。]] 图G的代数连通度（algebraic connectivity）是G的拉普拉斯矩阵的第二小的特征值（重特征值要重复计算）。这个特征值大于0当且仅当G是连通图。这是一个简单的推论，因为拉普拉斯矩阵的特征值0的重数就是图的连通分支的个数。这个值的大小反映了整个图的连通程度。它可以用于分析网络的稳定性与可同步性。 性质 图G的代数连通度大于0当且仅当G是连通图。而且，图的代数连通度的值不大于（顶…
元件 (圖論)
在圖論中，元件（）又稱為連通元件、-{zh-hant:分量;zh-hans:元件;}-、或分支，是一個無向子圖，在元件中的任何兩個頂點都可以經由該圖上的邊抵達另一個頂點，且沒有任何一邊可以連到其他子圖的頂點。例如右圖中的無向圖可以分成3個無向子圖，也就是3個元件。沒有與任何其他頂點相連的單一頂點也可以算是一個元件。 如果圖是一個有向圖，而每2個頂點都存在可以來回該頂點的路徑則稱為強連通元件；而若圖上任兩個點之間皆有不止一條路徑連通，則稱…
连通性 (图论)
在数学与计算机科学中，连通性是图论的一个基本概念：它是需要移除的元素（节点或边）的最小数量，使得剩余的节点分离成两个或多个独立的子图。它与网络流问题的理论密切相关。图的连通性是衡量其作为网络的韧性的重要标准。 连通节点和连通图 在无向图中，如果包含一条从到的路径，则两个顶点和被称为是连通的。否则，它们被称为是非连通的。如果这两个顶点由一条长度为的路径连接，即由一条边连接，则这两个顶点被称为是相邻的。 如果图中的每一对顶点都是连通的，则称…
道路 (图论)
在图论中，一个图中一条道路或稱路徑（）是一个顶点序列，使得从它的每个顶点有一条边到该序列中下一顶点。一条道路可能是无穷的，但有限道路有一个最先顶点，称为起点，和最后顶点，称为末点。两者都成为这条道路的端点。道路中其它顶点成为内点。一个圈是起点与末点相同的道路。注意到一个圈中起点的选取是任意的。 道路与圈是图论中的基本概念，在大部分图论教材中的绪论一节会介绍。例如参见 Bondy and Murty (1976)、Gibbons (198…
双连通图
在图论中，一个点双连通图是一个连通且“不可分离”的图，意思是如果任何一个顶点被去除，图仍是连通的。所以这样一个双连通图就没有。的性质和点双连通是几乎等价的，除了一条边连接两个点构成的图，它是点双连通的，但不是2-点连通的。 这个性质在维护一个有2度冗余的图中特别有用，为了防止去除一条边（或连接）之后的不连通。 由于冗余的这种特性，双连通图的使用在网络领域非常重要（参见网络流）。 定义 一个双连通的无向图是一个连通图，不会因为删除任一个节…
强连通分量
在有向图的数学理论中，如果一个图的每一个顶点都可从该图其他任意一点到达，则称该图是强连通的。在任意有向图中能够实现强连通的部分我们称其为强连通分量。判断一个图是否为强连通以及找到一个图强连通分量只需要线性时间（Θ(V + E)）。 定义 如果有向图的每一对顶点之间在每个方向上都有一条路径，则称该有向图为强连通图。也就是说，顶点对中的第一个顶点到第二个顶点存在一条路径，从第二个顶点到第一个顶点存在另一条路径。在本身可能不是强连通的有向图G…
桥 (图论)
和6個橋的圖（橋以紅色線段標示）]] 在圖論中，一條邊被稱為「橋」代表這條邊一旦被刪除，這張圖的連通塊數量會增加。 等價地說，一條邊是一座橋若且唯若這條邊不在任何環上。一張圖可以有零或多座橋。 樹和森林 一張 n 個點的圖最多有 n-1 座橋，因為再加一條邊就一定會產生一個環。恰好有 n-1 座橋的圖就是樹；而圖上每一條邊都是橋的圖就是森林。 無橋圖 一個無橋圖就是一個沒有橋存在的圖。等價條件是每個圖中的連通分支都擁有一個張開的耳狀分解…