在圖論中,二部圖(英語:Bipartite graph)是一類特殊的圖,又稱為二部图、偶图、雙分圖。二分圖的頂點可以分成兩個互斥的独立集 U 和 V 的圖,使得所有邊都是連結一個 U 中的點和一個 V 中的點。頂點集 U、V 被稱為是圖的兩個部分。等價的,二分圖可以被定義成圖中所有的環都有偶數個頂點。...
27 KB (3,752 words) - 08:14, 22 January 2024
二分图最佳带權匹配问题是指在给定带权二分图上求出一个最大匹配的问题,使得所有匹配边权值之和最大。这个问题也被称为二分图最优匹配。 此类问题通常使用KM算法或转换为一个网络费用流问题进行求解。 一个带权二分图 G = ( X , Y , E ) {\displaystyle G=(X,Y,E)} 中的边...
3 KB (525 words) - 19:38, 30 August 2021
完全二分图是一种特殊的二分图,可以把图中的顶点分成两个集合,使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。 完全二分图 G := ( V 1 + V 2 , E ) {\displaystyle G:=(V_{1}+V_{2},E)} 是一个二分图,使得对于任何两个顶点 v 1 ∈ V 1...
2 KB (318 words) - 10:31, 28 April 2023
在音乐记谱中,二分音符是一种音符时值。在五线谱记法中,二分音符表示为一个空心的椭圆符头加上一个不带符尾的符桿(如右图左边的记号)。当符头位於五线谱第三线上方(包括第三线)时,符桿朝下,否则符桿朝上,符桿改变方向时,符头的方向也要作相应改变(见图)。二分音符的音长是全音符的二分...
1 KB (151 words) - 07:44, 24 July 2021
conjecture)的反例,有46个点的图特图(英语:Tutte graph)。1971年,图特猜想所有的二分立方图都有哈密顿回路。然而Joseph Horton提出了图特猜想的反例,有96个点的Horton图(英语:Horton graph)。在这之后,Mark Ellingham(英语:Mark...
6 KB (784 words) - 01:55, 10 October 2023
图来刻画完美图。 一个完美图是具有下述性质的无向图:在其每个导出子图中,最大团的顶点数都等于对该导出子图的着色的颜色数的最小值。完美图包括了很多重要类型的图,例如二分图、弦圖和可比图(英语:comparability graph)。 一个图的补图在某两个顶点之间连一条边当且仅当原图...
8 KB (933 words) - 22:03, 6 October 2020
graph)。k-点连通图通常也简称k-连通图。 二分图(英語:bipartite graph)是指这样的简单图:其点集可以被划分称两个集合W和X,其中W中的任意两个节点之间没有边相连,X中的任意两个节点之间也没有边相连。二分图是点着色色数为2的图。 若一张图...
25 KB (3,662 words) - 10:07, 29 August 2023
图属性与其相关性较高: 如果具有P属性的图其每一个诱导子图都具有P属性,则称该图是遗传的。例如,完美图和弦图是遗传的。 如果具有P属性的图其每一个子图都具有P属性,则称该图是单调的。例如,二分图和无三角形图是单调的。所有单调的图都是遗传的,但遗传的图不一定单调。例如,弦图的子图不一定是弦图,所以弦图并不是单调的。...
8 KB (1,092 words) - 03:25, 6 October 2020
theorem,当且仅当一个图不包含 K 5 {\displaystyle K_{5}} ,以及完全二分图 K 3 , 3 {\displaystyle K_{3,3}} 作为它的一部分时,这个图是平面图。根据Wagner's theorem,当且仅当一个图不包含 K 5 {\displaystyle...
11 KB (1,118 words) - 19:08, 17 November 2021
二分埔,原寫為二份埔,是臺灣臺中市北屯區的一個傳統地域名稱,位於該區西南部,地名來自當地最大姓氏賴姓對土地的劃分方式。相較於今日行政區,其範圍大致包括平陽里不含西北端、平和里不含西南端、平德里、平安里不含西南端、平心里、平福里、平順里、平興里、平田里不含東南端、平昌里不含東南部,以及北區賴興里東北部...
9 KB (1,251 words) - 02:29, 13 September 2022
在图论中,如果无向图H可以通过图G删除边和顶点或收缩边得到,则称H为G的子式(minor)或次图。 图子式的提出源自瓦格纳定理,这个定理表明:当且仅当一个图不存在完全图K5和完全二分图K3,3的子式时,这个图才是平面图。 罗伯逊-西摩定理(英语:Robertson–Seymour...
18 KB (2,057 words) - 14:40, 17 March 2024