覆盖 (图论)
覆盖了四条边（标记为绿色），剩余两条黑边未覆盖。 右上图红色顶点覆盖了三条边，剩余三条边未覆盖。 下图用两个红色顶点完成了所有边的覆盖。 ]] 图的覆盖是一個顶点的集合，使图中的每一条边都至少連結該集合中的一个顶点。寻找最小的顶点覆盖的问题称为顶点覆盖问题（），它是一个NP完全问题。 顶点覆盖和边覆盖分别与独立集合和匹配问题有关。 定义 图G的顶点覆盖是一个顶点集合V，使得G中的每一条边都接触V中的至少一个顶点。我们称集合V覆盖了G的边…
标签：#图论
共 82 篇文章
树宽
图论中，无向图的树宽（treewidth）是描述图与树的距离的正整数。树宽为1的图就是树或森林。树宽不大于2的图叫做系列并行图。树宽恰为k的最大图称作k树，树宽不大于k的图称作部分k树。很多有充分研究的图族的树宽也是有界的。 树宽可用几种等价方式正式定义：图的树分解中最大顶点集的大小、图的弦补全中最大团的大小、描述图上追逃对策的港的最大阶数、刺藤（bramble，相互接触的连通子图的集合）的最大阶数。 树宽常用作图算法的参数复杂性分析中…
调和矩阵
在图论中，调和矩阵（harmonic matrix），也称拉普拉斯矩阵或拉氏矩阵（Laplacian matrix）、离散拉普拉斯（discrete Laplacian），是图的矩阵表示。 调和矩阵也是拉普拉斯算子的离散化。换句话说，调和矩阵的缩放极限是拉普拉斯算子。它在机器学习和物理学中有很多应用。 定义 若G是简单图，G有n个顶点，A是邻接矩阵，D是度数矩阵，则调和矩阵是 E(f) = \sum w(uv)(f(u)-f(v))^2…
圖乘積
在圖論中，圖乘積為一個在圖上的二元運算，精確地說，這是一個需要兩個圖G1和G2，並產生出圖H 有著以下性質 圖H的頂點集合 是 笛卡爾乘積 V(G1) × V(G2)，其中 V(G1)和 V(G2)分別是圖 G1 和 G2的頂點集合。 H的兩個頂點(u1, u2)和(v1, v2) 是由一條邊所連接頂點 u1, u2, v1, v2滿足一個條件需要將圖 G1 和 G2的邊列入考慮。 關於用詞以及符號對於特定的圖乘積有非常多，讀者應當注意…
Tarjan算法
Tarjan算法（以發現者Robert Tarjan命名）是一個在圖中尋找強連通分量的算法。雖然發表時間更早，它仍可以被視為Kosaraju算法的一個改進。它的效率跟差不多。 概述 此算法以一個有向圖作為輸入，並按照所在的強連通分量給出其頂點集的一個劃分。圖中的每個節點只在一個強連通分量中出現，即使是在有些節點單獨構成一個強連通分量的情況下（比如圖中出現了樹形結構或孤立節點）。 算法的基本思想如下：任選一節點開始進行深度優先搜索（若深度…
图的次幂
在数学的一个分支图论中，一个无向图的*k次幂Gk指的是另一个有相同顶点集的图，但在G中所有距离小于k的顶点在该图中是相邻的。图的次幂常用数的次幂相关术语来表示：G2被称为G的平方，G3被称为立方，以此类推。 图的次幂应该与图本身的乘积区别开来，图的乘积（与次幂不同）通常比原图有更多的顶点。 属性 如果一个图的直径是d，那么它的d次幂就是完全图。如果一个图族具有有界的团宽，那么对于任意固定的d，它的d次幂也具有有界的团宽。 着色 图平方的…
一笔画问题
一笔画问题（Eulerian graph）是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了一笔画定理，顺带解决了一笔画问题。一般认为，欧拉的研究是图论的开端。 与一笔画问题相对应的一个图论问题是哈密顿路径问题。 能夠在不重複折返的前提下一笔画寫出或一次走完該路徑的條件，是文字、圖形、路徑的奇顶点的數目正好是0個或2個時，而如果奇顶点的數目兩個時，…
同胚 (圖論)
在圖論中，同胚（）是兩個圖之間的一種關係，指在僅考慮圖分支架構的情況下，兩圖有相同的分支架構。在部分情況下，同胚這個術語亦用於拓樸學中。 定義 若兩圖G和G'，其中G是某圖的若干細分變換結果，且G'可以透過其原像套用若干細分變換來形成，則稱G和G'同胚。若兩圖的線條（即從一個頂點出發抵達另外一個頂點中途都沒有其他分支的路徑）皆能一一對應，則稱兩圖同胚。 計算複雜性 判定兩圖是否同胚是一個NP完全的問題。在與同胚相關的研究中，更常探討的議…
双体模型
在统计力学和图论中，双体模型（dimer model）是二维空间密鋪的模型，也称为骨牌密鋪（Domino tiling，多米诺密鋪）或随机密铺模型（random tiling model）。这也是平方格子的完美匹配。 介绍 若有 m \times n 平方格子G、以及 mn/2 把骨牌，覆盖数量或密铺数量是 例如： 2 \times n 格子： Z_n是斐波那契数列 m = n = 2k = 0, 2, 4, \ldots ，可以使用普…
桥 (图论)
和6個橋的圖（橋以紅色線段標示）]] 在圖論中，一條邊被稱為「橋」代表這條邊一旦被刪除，這張圖的連通塊數量會增加。 等價地說，一條邊是一座橋若且唯若這條邊不在任何環上。一張圖可以有零或多座橋。 樹和森林 一張 n 個點的圖最多有 n-1 座橋，因為再加一條邊就一定會產生一個環。恰好有 n-1 座橋的圖就是樹；而圖上每一條邊都是橋的圖就是森林。 無橋圖 一個無橋圖就是一個沒有橋存在的圖。等價條件是每個圖中的連通分支都擁有一個張開的耳狀分解…
随机最小生成树
在数学中，将一个无向图按照某种分布随机分配边权后可得一个新图，后者的最小生成树便称为随机最小生成树。 若给定的图是个顶点的完全图，且边权的分布函数处处连续并在原点处导数，则随机生成树的边权总和有上界，后者不随的增长而增长。更精确地讲，趋向于无穷大时，趋向于，其中为黎曼ζ函數，为阿培里常数。例如，若边权均匀分布于单位区间，则其导数为，趋向于无穷大时，恰趋向于。 的随机生成树在多孔介质中液态流体的模型以及算法中都有所应用。 参考资料
随机图
在數學中，随机图是指由随机过程产生的图。随机图的理论处于图论和概率论的交叉地带，主要研究各种经典随机图的性质。随机图的实际应用主要在复杂网络中所有建模领域中。第一批关于随机图的结果是保罗·埃尔德什和阿尔弗雷德·雷尼在1959年至1966年的一系列论文中提出的ER随机图。。在其他语义中，任何图模型都可以被称为随机图。 定义与模型 随机图的“随机”二字体现在边的分布上。一个随机图实际上是将给定的顶点之间随机地连上边。假设将一些纽扣散落在地上…
网络编码
网络编码是一种通过中继节点对接收到的信息进行编码来达到提高多播网络容量的技术。Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Raymond W. Yeung在2000年首次提出网络编码的概念。 在右图的网络拓扑中，s节点试图向t_{1}, t_{2}组播两条消息x,y。设每条消息占用的带宽为1，每个节点之间的网络带宽也为1，那么每个节点之间只能同时传输一条消息。线路cd上会需要同时传输x,…
因子 (圖論)
在圖論中，因子是某個圖G的生成子圖，並且是與G相同的頂點的子圖。通常因子名稱前面會加一個數，例如k-因子，表示每個頂點的度均為k，換句話說即該因子為k-正則生成子圖。將某個圖G的邊分解為若干個互斥的k-因子之動作稱為k-分解。類似於除法整除的概念，如果圖G可以被k-分解，則G可以稱為k-因子分解圖（類似於G可被k整除的概念），而圖與因子間關係則可以類比為數與因數。特別地，將任意圖1-分解為1-因子是一種完美匹配，因為其結果括了圖G中原來…
重构猜想
重构猜想(英语:Reconstruction Conjecture)，图论中的重構猜想，认为一个图能够由它的子图唯一决定。此猜想由PAUL J. KELLY和斯塔尼斯拉夫·乌拉姆共同提出。 正式陈述 给定图 G = (V,E), 其 顶点子图（英文：vertex-deleted subgraph）是在G中删除了一个顶点得到的子图. 根据定义, 它是图 G的导出子图。 对于图G, 其deck, 记作D(G),是由G的所有顶点子图的同构类所…
邊 (圖論)
]] 在圖論中，邊（edges）是圖的基本單元之一，其與點共同組成了圖。一般的情況下，邊通常是連接兩個點的圖論元素，而在部分的情況下會只連接1個點（如非簡單圖）或連接3個或更多個點（如超圖），因此邊通常可以被定義為將點相連的元素，而被邊連接的點稱為端點。 分類 邊依照連接的點數量可以分為三類，其中一種稱為簡單邊，即這些邊連接2個相異的點。簡單圖的每一個邊皆為簡單邊。另一種為超邊（hyperedges），即這些邊連接3個或更多個點，通常出…
圖論傅立葉轉換
圖論傅立葉轉換（Graph Fourier Transform，GFT），是將離散傅立葉轉換延伸至處理圖訊號時的推廣型態。其轉換函數由其預設的圖決定，沒有既定的方程式表示法。 在形式上，變換兩端（時域和頻域）的資料維度皆為有限長。 常見定義 一個已編號的N點一般圖（有限不重邊無向圖）G，考慮它的拉普拉斯矩陣（Laplacian matrix）L： :L = D-W 其中D為此圖的度數矩陣，W為邻接矩陣。 因L為實對稱矩陣，L會有特徵分解…
邻接表
在图论和计算机科学中，邻接表（英语：adjacency list）是表示了图中与每一个顶点相邻的边集的集合，这里的集合指的是无序集。 如果是无向图，那么每条边由两个结点组成，分别代表边的两个端点；如果是有向图，那么每条边是一个结点对，分别代表边的始点和终点。 计算机科学中的应用 在计算机科学中，邻接表描述一种紧密相关的数据结构，用于表征图。在邻接表的表示中，对于图中的每个顶点，将保存所有其它与之相连的顶点（即“邻接表”）。例如，由吉多·…
边
邊或邊緣（）可以指： 邊 (幾何)或稱稜（）是一个几何图形两个相邻頂點之间线段。假如连接两个端点的是一段曲线，数学上稱為弧。 邊 (圖論)（）是两个事物间某种特定关系的抽象化。两个事物间有联系，则这两个事物代表的顶点间就连有边，用一根直线或曲线表示。 邊 (魔術方塊)或稱邊塊：魔術方塊解法術語。 边长通常指一個邊的長度，亦可以指： *边长或稱稜長：一個幾何結構內特定邊的長度 邊長在某些教科书中，也用于表示在一个封闭的平面几何图形中的所有…
树同构
树同构(Tree Isomorphism)描述的是图论中，两个树之间的完全等价关系。在图论的观点下，两个同构的树可以被当作同一个图来研究。 定义 树同构的概念源于图同构。图同构的概念为，两个简单图G和H称为是同构的，当且仅当存在一个将G的节点 1,\ldots,n 映射到H的节点1,\ldots,n的一一对应\sigma，使得G中任意两个节点i和j相连接，当且仅当H中对应的两个节点\sigma(i)和\sigma(j)相连接。树同构即在…