邻接矩阵
在图论和計算機科學中，邻接矩阵（）是一種方块矩阵，用來表示有限图。它的每個元素代表各点之间是否有边相连。 作爲特例，簡單圖的鄰接矩陣是(0,1)矩陣並且對角線元素都爲0。無向圖的鄰接矩陣是對稱矩陣。圖和其鄰接矩陣的特徵值和特徵向量之間的關系是譜圖理論的研究對象。 圖的關聯矩陣}-需要和鄰接矩陣區分。它是圖的另一種矩陣表示方式，它的元素表示各個节点-邊對是否相關。還有圖的度數矩陣，含有每個結點的度數信息。 距離矩陣可算是鄰接矩陣的擴充。 …
标签：#图论
共 82 篇文章
生成树
在图论中，無向圖 G 的生成树（）是具有 G 的全部顶点，但边数最少的連通子圖。 以V表示顶点，E表示边，若图 G=(V(G),E(G))和树T=(V(T),E(T))，有E(T)\subset E(G)和V(G)=V(T)，那么T是G的生成树。 一个图的生成树可能有多个。 最小生成树 带权图的生成树中，总权重最小的称为最小生成树。 求取最小生成树的算法： 克鲁斯克尔演算法 - 一种贪心算法，复杂度是 O(E \log{E})。 普林姆…
瓦格纳定理
的图子式 (彩色小圆圈和黑色边，删除红色顶点，收缩每个黄色圆圈内的边)。]] 在图论中，瓦格纳理论（）是平面图的禁图表征，以Klaus Wagner的命名。 该定理说：当且仅当有限图的子式不包含完全图K5 或完全二分图K3,3 时候，那么该图就是平面的。 这是图子式论最早的结果之一，也是罗伯逊–西摩定理（Robertson-Seymour theorem）的先驱。 库拉托夫斯基定理的关系 瓦格纳1937年发表了证明。 库拉托夫斯基以前1…
星 (图论)
在图论中，星（）Sk属于完全二分图K1,k：是具有一个内部节点和k个叶节点的树（但当k≤1时，没有内部节点且由k+1个叶节点）。另外，一些文章将Sk 定义为最大直径为2的k阶树；在这种情况下，k>2的星具有k−1个叶节点。 有三条边的星又称为爪。 当k是偶数时，星Sk是边优美图，当k是奇数时则不是。它是一个边传递的火柴杆图，其直径为2（当k > 1时），围长为∞（无循环结构），色指数为k，色数为2（当k > 0时）。此外，星具有较大的自…
亏格
数学上的亏格，也称为曲面种数（）有几个不同但密切相关的意思。最常见的概念是（有方向的）曲面的亏格，是其具有的“孔”的数量，因此，一个球体的亏格为0，而一个圆环的亏格为1。 拓扑 可定向曲面 连通，可定向曲面的亏格是一个整数，代表沿闭简单曲线切开但不切断曲面的最大曲线条数。这和柄的个数是相同的。 例如： 球面，圆盘和环亏格都为0。 环面亏格1，和带一个柄的咖啡杯的表面是一样的。 Image:Sphere-wireframe.png|亏格0…
细分 (图论)
{{Double image|right|Digon_graph.svg|150|Circle graph C4.svg|150|細分也可以用於將無圖轉換成簡單圖，為圖子式理論中的基本運算元之一，而變換完的像稱為細分圖。 在圖論的一般情況下，細分通常是指對邊的細分，而在一些領域中會有對面或其他結構的細分（如高維度的標記），例如，有時會稱為剖分及剖分圖。 定義 細分 細分是一種作用於邊上的變換，因此其需作用於特定的邊，令其記為e，並令e所…
图 (数据结构)
和3条边的有向图]] 在计算机科学中，图（）是一种抽象数据类型，用于实现数学中图论的无向图和有向图的概念。 图的数据结构包含一个有限（可能是可变的）的集合作为节点集合，以及一个无序对（对应无向图）或有序对（对应有向图）的集合作为边（有向图中也称作弧）的集合。节点可以是图结构的一部分，也可以是用整数下标或引用表示的外部实体。 图的数据结构还可能包含和每条边相关联的数值（），例如一个标号或一个数值（即权重，；表示花费、容量、长度等）。 操作…
拓撲排序
在计算机科学领域，有向图的拓扑排序（）或拓撲定序（）是对其顶点的一种线性排序，使得对于从顶点 u 到顶点 v 的每个有向边 uv ， u 在排序中都在 v 之前。 例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。 当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。 任何有向无环图至少有一个拓扑排序。已知有算法可以在-{}-线性时间内，…
普吕弗序列
在图论中，标号树的普吕弗序列（）是由树唯一地产生的序列。n顶点的标号树有长n − 2的普吕弗序列，可以从一个简单的迭代算法得到。普吕弗序列在1918年首先由海因茨·普呂弗用来证明凯莱公式。 算法 一棵树要得到普吕弗序列，方法是逐次去掉树的顶点，直到剩下两个顶点。考虑树T，其顶点为{1, 2, ..., n}。在第i步，去掉标号最小的叶，并把普吕弗序列的第i项设为这叶的邻顶点的标号。 一棵树的序列明显是唯一的，而且长为n − 2。 例子 …
圖模式
在概率论、統計學及機器學習中，概率图模型（）是用圖論方法以表現數個獨立隨機變數之關聯的一種建模法。一个p个節點的图中，节点i对应一个隨機變數，记为X_i。概率图模型被广泛地应用于贝叶斯统计与机器学习中。 有向和无向概率图模型的定义 在一个无向概率图模型(Undirected Graphical Model)中，两个节点i和j之间没有边相连，当且仅当它们对应的随机变量X_i和X_j给定其它所有节点上的随机变量条件下条件独立。数学表述为： …
刻宽
图论中，图的刻宽（carving width）是由图定义的数，描述了图顶点的层次聚类中，分隔聚类的边数。 定义与例子 刻宽是根据给定图顶点的分层聚类（称作“刻”，carving）定义的。刻可以描述为无根二叉树，其叶上标有给定图的顶点。从树上移除任意一条边，都会将树分为两子树，并相应地将树上顶点分为两簇。这样形成的顶点簇构成了层状集合族（Laminar set family）：任意两顶点簇（不仅是移除同一条边形成的两互补簇）或不交，或是包…
书 (图论)
在图论中，书图（book graph，常写作B_p ）是由多个环经过同一条边而形成的图。 种类 由p个共享一条边（称为书的“脊”或“基”）的四边形组成的书称为四边形书。也就是说，它是一个星图和一条单边的笛卡尔积。这种类型的7页书图提供了一个没有协调标号的图的例子。 这种类型的书属于分割图。这种图也称为 K_e(2,p)。 三角形书是线完美图的一个关键构建模块。 术语"书图"曾用于其他用途。 Barioli曾将该词用于表示由具有两个共同顶…
競賽樹
競賽樹（）是指組合博弈理論中用來表達一個賽局中各種後續可能性的樹，一個完整的競賽樹（complete game tree）會有一個起始節點，代表賽局中某一個情形，接著下一層的子節點是原來父節點賽局下一步的各種可能性，依照這規則擴展直到賽局結束。競賽樹相同於擴展形式的博弈理論中的樹。競賽樹中形成的葉節點代表各種遊戲結束的可能情形，例如井字遊戲會有26,830個葉節點。 競賽樹在人工智慧的應用相當重要，若要尋找某賽局中最佳的步法的一個方式，…
偶级图
在图论中，偶极图(dipole graph)，又称为偶级(dipole)或键合图(bond graph)，是一个两个顶点之间由多重边连接的多重图。包含n条边的偶极图称为n阶偶极图，用Dn表示。n阶偶极图是循环图Cn的对偶图。 作为抽象图的蜂巢是偶极图D3的最大阿贝尔覆盖图，而作为抽象图的金刚石晶体是D4的最大阿贝尔覆盖图。 与柏拉图的图相似，偶极图形成了多面形的骨架。它们的对偶，周期图，形成了二面体的骨架。 参考文献 Weisstein…
循环图
在图论中，循环图（cycle graph）或环形图（circular graph）是由一个单环组成的图，或者说是在一个闭合链中互相连接的若干顶点（至少3个）。有n个顶点的循环图写作Cn。Cn中的顶点个数等于边的个数，每个顶点的度均为2；这意味着每个节点都是两条边的端点。 术语 “循环图”有许多同义词。其中包括简单循环图（simple cycle graph）和周期图（cyclic graph），尽管后者的使用频率较低，因为它也可以指代不…
任务分配问题
任务分配问题是在加权二分图中寻找最大（或最小）加权匹配的问题，也称二分图最佳带權匹配问题或二分图最优匹配。此类问题通常使用匈牙利算法（KM算法）或转换为一个网络费用流问题进行求解。 详述 分为以下几类： 线性任务分配问题：P是二元组(a, b)的集合，其中a和b分别是集合A和B中的元素。C是某一函数，并满足特定约束条件，例如：A的每一个元素必须在P中出现一次，或者B的每一个元素必须在P中出现一次，或者以上二者都必须满足。线性任务分配问题…
最小费用最大流问题
最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。 问题提出 有足够多辆卡车要将数量无限的某种物品从一个地点运输到另外一个地点，现在有有限条单向行驶道路直接或者间接地连接了这两地。但是每一条道路都有运输通过总数量的限制，称为容量，同时携带物品通过该路段时，都会按照携带物品数…
顶点 (图论)
在数学中，更确切地说，在图论中，一个顶点（vertex，或多个顶点，vertices）或节点（node）是构成图的基本单位：一个无向图包括一个顶点的集合和一个边（顶点的无序对）的集合，而一个有向图包括一个顶点的集合和一个弧（顶点的有序对）的集合。在一个图的示意图中，一个顶点通常表示为一个带标号的圆形，而一条边表示为连接两个顶点的一条直线或一个箭头。 站在图论的角度上，顶点被视为无特征且不可分割的对象，虽然因为该图的用途不同，他们可能有额…
道路 (图论)
在图论中，一个图中一条道路或稱路徑（）是一个顶点序列，使得从它的每个顶点有一条边到该序列中下一顶点。一条道路可能是无穷的，但有限道路有一个最先顶点，称为起点，和最后顶点，称为末点。两者都成为这条道路的端点。道路中其它顶点成为内点。一个圈是起点与末点相同的道路。注意到一个圈中起点的选取是任意的。 道路与圈是图论中的基本概念，在大部分图论教材中的绪论一节会介绍。例如参见 Bondy and Murty (1976)、Gibbons (198…
独立集
独立集（英语：Independent set）是图论中的概念。一个独立集（也称为稳定集）是一个图中一些两两不相邻的顶点所形成的集合。换句话说，独立集S由图中若干顶点组成，且S中任两个顶点之间没有边。等价地，图中的每条边至多有一个端点属于S。一个独立集的基数是它包含顶点的数目。 如果往图G的独立集S中添加任一个顶点都会使独立性丧失（亦即造成某两点间有边），那么称S是极大独立集。如果S是图中所有独立集之中基数最大的，那么称S是最大独立集，且…