SPQR樹
在圖論（數學的一個分支）中，一個雙連通圖的三連通分量是一組較小的圖，用來描述該圖中的所有 2-頂點割。SPQR樹是電腦科學中，更精確地說，是圖論演算法中的一種樹狀資料結構，用以表示圖中的所有三連通分量。一個圖的 SPQR 樹可以在線性時間內構造，並且在動態圖演算法與圖繪製中均有若干應用。 SPQR樹背後的基本結構，圖的三連通分量以及這種分解和平面圖平面嵌入之間的關係，最早由 Saunders Mac Lane (1937) 研究，在 D…
标签：#圖論
共 10 篇文章
交叉數
在圖論，交叉數\text{cr}(G)是將圖G畫在平面上時，邊的交叉點的最小數目。若\hbox{cr}(G)=0，則G稱為平面圖。在方面，計算圖的交叉數仍是一個重要問題，因為讀者研究發現，畫圖的交叉越少，越有利於讀者理解。 交叉數的研究始於。圖蘭·帕爾想求磚廠中，將每個窯爐各與全部貨倉用路軌連接的最優方案，使路軌的交叉儘可能少。按上述定義，即是問完全二部圖的交叉數。同一問題約莫同時在社會學研究提出，因為事關的繪製。 圖蘭猜想了完全二部圖…
网络流
在圖論中，網絡流（）是指在一個每條邊都有容量（Capacity）的有向圖分配流，使一條邊的流量不會超過它的容量。通常在运筹学中，有向图称为网络。顶点称为节点（Node）而边称为弧（Arc）。一道流必須符合一個結點的進出的流量相同的限制，除非這是一個源點（Source）──有較多向外的流，或是一個匯點（Sink）──有較多向內的流。一個網絡可以用來模擬道路系統的交通量、管中的液體、電路中的電流或類似一些東西在一個結點的網絡中遊動的任何事物…
哈密顿路径问题
上的哈密顿环（红色）。]] 图论中的经典问题（Hamiltonian path problem）与（Hamiltonian cycle problem）分别是来确定在一个给定的图上是否存在哈密顿路径（一条经过图上每个顶点的路径）和哈密顿环（一条经过图上每个顶点的环）。两个问题皆为NP完全。 哈密顿环问题与哈密顿路径问题之间的关系 哈密顿环问题与哈密顿路径问题之间有着很简单的关系： 给定图G ,通过加入新顶点v 并将新顶点与所有其他顶点连…
树旋转
在数据结构中，树旋转（）是对二叉树的一种操作，不影响元素的顺序，但会改变树的结构，会将一个节点上移，一个节点下移。树旋转会改变树的形状，因此常被用来将较小的子树下移、较大的子树上移，从而降低树的高度、提升许多树操作的效率。 树的旋转方向有很多不同的定义，有些定义彼此之间还存在冲突。有些人认为旋转方向应该反映节点的移动方向（左子树旋转到父节点的位置为右旋），有些人则认为旋转方向应该反映被旋转的子树是哪棵（左子树旋转到父节点的位置为左旋，与…
弦 (幾何)
弦是一個几何术语，也是一個圖論概念。 TOC 幾何術語 曲線 在几何学中，若一线段的两个端点都在曲線上，则该线段称作该曲線的弦。圓的任何弦的垂直平分線都會通過圓心。 三角形 弦可以指直角三角形上的斜边。 圖論概念 弦在圖論裡代表連接一個環上不相鄰的兩個點的一條邊。 三角函數 最早的三角函數表是以圓型的弦之長度來建表的。例如喜帕恰斯列出了每度的弦函數表。在公元二世紀，亞歷山大的托勒密在他的天文學書《天文學大成》建了更詳盡的弦長表——托勒密…
補圖
（左）以及其補圖（右）]] 在圖論裡面，一個圖G的補圖（complement）或者反面（inverse）是一個圖有著跟G相同的點，而且這些點之間有邊相連若且唯若在G裡面他們沒有邊相連。在製作圖的時候，你可以先建立一個有G所有點的完全圖，然後清除G裡面已經有的邊來得到補圖。這裡的補圖並不是圖本身的補集；因為只有邊的部份合乎補集的概念。 形式化表述 令G = (V, E)是一个图，K包含所有V的二元子集。则图H = (V, K \setmi…
度-直徑問題
度-直徑問題是圖論中一個問題，目的在定下最大直徑k及最大度數d後，找出擁有最多節點的圖。 假設圖以G=(V,E)表示，某節點的度數以\deg(v)表示，節點之間的最短距離以d(u,v)表示，則度-直徑問題是規定了 :d \ge \max_{v\in V} \deg(v) :k \ge \max_{u,v\in V} d(u,v) 求出圖G。G的大小（以節點數衡量）受制於摩爾上限，亦即節點的數目不可能多於 :1+d\sum_{i=0}^{…
中国邮递员问题
中国邮递员问题（也称路线检查问题，Route Inspection Problem）是一个图论问题。此問題為在一個連通的無向圖中找到一最短的封閉路徑，且此路徑需通過所有邊至少一次。现实意义中，中国邮递员问题就是在一個已知的地區，郵差要設法找到一條最短路徑，走過此地區所有的街道，且最後要回到出發點。 此問題是圖遍歷問題的一種。无向图的中国邮递员问题是容易解决的，是P问题；而有向图的中国邮递员问题是NP完全问题。中国邮递员问题由管梅谷教授在…
圖嵌入
圖嵌入是圖論中的一個概念。 非正式的講，圖嵌入就是一種圖在面上的繪製，該繪製使得圖的邊只在端點相交。眾所周知，任何圖都能嵌入到三維歐几里得空間，而平面圖能夠嵌入到二維歐几里得空間。 參考資料