集聚系数
在图论中，集聚系数（也称群聚系数、集群系数）是用来描述一个图中的顶点之间结集成团的程度的系数。具体来说，是一个点的邻接点之间相互连接的程度。例如生活社交网络中，你的朋友之间相互认识的程度。有证据表明，在各类反映真实世界的网络结构，特别是社交网络结构中，各个结点之间倾向于形成密度相对较高的网群。也就是说，相对于在两个节点之间随机连接而得到的网络，真实世界网络的集聚系数更高。 集聚系数分为整体与局部两种。整体集聚系数可以给出一个图中整体的集…
标签：#图论
共 82 篇文章
支配 (圖論)
在计算机科学中，控制流图的一个节点（基本块） d 支配节点 n，当且仅当从开始节点（可以理解为源）到节点 n的每一条路径均要经过节点d，写作d dom n (一写作d \gg n)。根据上述定义，容易得到每个节点均支配其自身。 一些相關概念： 说一个节点 d 严格支配节点n，当且仅当 d支配 n 而不等于 n。 节点 n 的直接支配节点（immediate dominator），简称 idom 是一个独特的节点，它严格支配节点 n，却不…
连通分量标记
连通分量标记（或者称连通分量分析,连通区域标记）是图论应用中的一种算法，给二值图像中的每个连通区域标上一个特定的标号。该算法可用来对图像的目标进行定位和计数。该算法不要和图像分割相混淆。 连通分量标记通常在计算机视觉领域中对二值图像的连通区域进行检测，也可以处理彩色图像和更高维的数据。当将其集成到图像识别系统或者是人机交互系统时，该算法也起到重要作用。 概述 中间像素和它周围像素的位置决定了是几邻域连接，4邻域连接是周围像素处在中间像素…
扩展图
在组合数学中，扩展图（）是一种具有强连通性质的稀疏图，可用边扩展性、顶点扩展性或图谱扩展性三种方式来量化。扩展图的构造问题引导了多个数学分支上的研究，并且在计算复杂性理论、计算机网络设计和编码理论上有诸多应用。 定义 对于有限、无向、连通的多重图，扩展性是一种能够衡量其连通强弱的指标。直观而言，扩展性较强意味着图中任何「不太大」的顶点集均有较大的边界，也就是说集合内外的交互很强。 连通图的扩展性有的弱，有的强。例如道路的扩展性很弱，而完…
网络理论
与10条边的小型网络示例]] 网络理论（Network theory）是一种对图的研究，也是对称关系或在离散对象中的一种表现。 在计算机科学和网络科学中 ，网络理论是图论的一部分：网络可以定义为节点和/或边具有属性（例如名称）的图。 网络理论目前在许多学科中有应用，学科包括统计物理学、粒子物理学、计算机科学、电气工程学、生物学、经济学、金融学、运筹学、气候学、生态学和社会学；应用包括物流网、万维网、互联网、、代谢网络、社会网络、知识论网…
图论
图论（），是组合数学分支，和其他数学分支如群论、矩阵论、拓扑学有着密切关系。 图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。 图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。 图论的研究对象相当于一维的单纯複形。 历史 一般认为，欧拉于1736年出版…
图同构
图同构（）描述的是图论中，两个图之间的完全等价关系。在图论的观点下，两个同构的图被当作同一个图来研究。 定义 一般定义 只有节点数目相同(即同阶)的两个图才有可能同构。两个简单图G和H称为是同构的，当且仅当存在一个将G的节点 1,\ldots,n 映射到H的节点1,\ldots,n的一一对应\sigma，使得G中任意两个节点i和j相连接，当且仅当H中对应的两个节点\sigma(i)和\sigma(j)相连接。同构可记作G\simeq H…
轮图
{{infobox graph | name = 轮图 | image = | image_caption = 轮图的一些例子 | girth = 3 | diameter = 2，如果n > 4 1，如果n = 4 | vertices = n | edges = 2(n − 1) | chromatic_number = 4，如果n是偶数 3，如果n是奇数 | chromatic_index = | spectrum = \{2\c…
距离 (图论)
在图论中，一张无向图里，两顶点之间的距离是指他们之间最短路径（）的长度，两顶点之间的距离也被称为测地距离（）。需要注意的是两个顶点之间可能有多条最短路径，如果两个顶点之间不存在路径（即他们属于不同的连通分量），那么按照传统它们距离被定义为无穷大。 在有向图中，如果从顶点 u 到顶点 v 存在有向路径（），那么距离 d(u,v) 被定义为从顶点 u 到顶点 v 之间最短有向路径的长度。不同于无向图，在有向图中 d(u,v) 不一定和 d(…
惠特尼连通性定理
图论中，惠特尼连通性定理（），简称惠特尼定理（），是美國數學家哈斯勒·惠特尼于1932年提出的关于2连通图等价性质的定理，该定理提供了关于2连通图的不同点对之间的连通性质刻画，描述了2连通图的特殊性质。 定理陈述 对一个图G，若G至少存在3个点，则G是2连通的当且仅当对G中任意两个点u, v，G中至少存在连接u, v的2条内部不相交路径，即除首尾相同（皆為u, v）外，沒有其他公共頂點的路徑。 定理证明 必要性 因为任意两点之间均存在路…
圖運算
在圖論中，可以藉由圖運算產生一些新的圖。 一元運算 基礎運算 圖的基礎運算，就是藉由從原先的圖上，經由簡單局部的更動，所產生的新的圖形，例如對頂點或是邊進行增加或是刪減，或是將頂點合併或是分開。 進階運算 圖的進階運算，就是藉由從原先的圖上，經由複雜的更動，所產生的新的圖形，例如: 轉置圖（） 補圖 線圖 圖子式 商圖（） 對偶圖 二元運算 二元運算相似於一元運算，也是藉由原先的圖經由運算產生新的。 G1 = (V1, E1)以及G2 …
惠特尼不等式
在图论中，惠特尼不等式 (英：Whitney's connectivity inequalities or Whitney's inequalities)，又称为惠特尼连通性不等式，是关于图的连通度的重要不等式，几乎出现于任何一本图论教科书中。该不等式明确地指出了图的点连通度与边连通度以及与图最小度之间的大小关系。但目前关于该定理的提出者是否是哈斯勒·惠特尼还没有统一定论。 叙述 对于任何一个非平凡图G，均满足 \kappa(G)\le…
度分布
度分布是图论和网络理论中的概念。一个图（或网络）由一些顶点（节点）和连接它们的边（连结）构成。每个顶点（节点）连出的所有边（连结）的数量就是这个顶点（节点）的度。度分布指的是对一个图（网络）中顶点（节点）度数的总体描述。对于随机图，度分布指的是图中顶点度数的概率分布。 定义 度分布是图论和（复杂）网络理论中都存在的概念。首先介绍图的概念。一个图G=G(V, E)是一个由两个集合V和E构成的二元组。集合V一般由有限个元素构成：V = \{…
图论术语
图论中有许多专有名词，此处总结了一些名词的一般意义和用法。 基本术语 一个图（一般记作G）由两类元素构成，分别称为“顶点”（或节点、结点）和“边”。每条边有两个顶点作为其端点，我们称这条边“连接”了它的两个端点。因此，边可定义为由两个顶点构成的集合（在有向图中为有序对，见下文“方向”一节）。 图也可以用其他模型来表示，如定义在顶点集合上的二元布尔函数，或者方形(0,1)-矩阵。 顶点或边上有标号的图称为有标号的，否则为无标号的。它们的区…
弦圖
在图论中，弦图（）是一类含有很多弦的图。所谓“弦”，即环中跨越非邻点的一条边，或者说“捷径”（可类比圆中的弦）。弦图要求图中任意一个长度不小于4的环都须含有弦。根据该定义，弦图中每一个大环都被弦切割成若干小三角形，因此弦图也被称作三角化图。 弦图是完美图的一种子类。算法可以在线性时间内判定一张图是否为弦图。而且，有些在一般图上困难的问题（比如图着色问题），在弦图上可被高效解决。 定义 设C_k := v_1 v_2 \dots v_k …
混合图
混合图（mixed graph）G = (V, E, A)是由顶点 （节点）的集合V、无向边的集合E和有向边的集合A所组成的数学对象。 定义和标识 考虑一对相邻的顶点 u,v \in V。有向边，是一个有方向的边，其可以表示为 \overrightarrow{uv} 或 (u,v) (即该有向边为由u指向v)。 同样地，无向边，是一个没有方向的边，其可以表示为 uv 或 [u,v]。如果不能从有向边形成循环，则认为混合图的方向是无环的。…
团宽
。顶点标签用颜色表示。]] 图论中，图G的团宽（clique-width）是描述图的结构复杂性的参数，与树宽密切相关，但对稠密图来说可以很小。 团宽的定义是通过以下4种操作，构造G所需的最少标号数： 创建标签为i的新顶点v，记作i(v)； 两有标图G、H的不交并，记作G \oplus H； 用边连接标i的每个顶点与标j的每个顶点，记作\eta(i,\ j),\ i\ne j； 将标签i改为标签j，记作\rho(i,\ j) 团宽有界图包…
径宽
图论中，图G的径分解（path decomposition）是G的“加粗”路径图表示，G的径宽（pathwidth）是衡量形成G的路径被加粗的程度。更正式地说，径分解是G的顶点子集序列，使每条边的端点出现在某一子集中，并使每个顶点都出现在子集连续子序列中，径宽等于这样的分解中最大集的大小减一。 径宽也叫做区间厚度（interval thickness，等于G的区间父图中的最大团大小减一）、顶点分隔数（vertex separation …
元件 (圖論)
在圖論中，元件（）又稱為連通元件、-{zh-hant:分量;zh-hans:元件;}-、或分支，是一個無向子圖，在元件中的任何兩個頂點都可以經由該圖上的邊抵達另一個頂點，且沒有任何一邊可以連到其他子圖的頂點。例如右圖中的無向圖可以分成3個無向子圖，也就是3個元件。沒有與任何其他頂點相連的單一頂點也可以算是一個元件。 如果圖是一個有向圖，而每2個頂點都存在可以來回該頂點的路徑則稱為強連通元件；而若圖上任兩個點之間皆有不止一條路徑連通，則稱…
匹配 (图论)
在图论中，一个图是一个匹配（或称独立边集）是指这个图之中，任意两条边都没有公共的顶点。这时每个顶点都至多连出一条边，而每一条边都将一对顶点相匹配。 严格定义 对于一个给定的图G=(V,E)，这幅图的一个匹配M是图G的一个子图（由原来的图的一部分顶点和一部分边构成的图），其中每两条边都不相邻（没有公共顶点）。在匹配图中，一个顶点连出的边数至多是一条。如果这个顶点连出一条边，就称这个顶点是已匹配的。 图G的一个极大匹配是指这样一个匹配，它不…