在圖論中,平面圖是可以画在平面上并且使得不同的邊可以互不交疊的圖。而如果一个图无论怎样都无法画在平面上,并使得不同的边互不交叠,那么这样的图不是平面图,或者称为非平面图。完全图 K5和完全二分图 K3,3(湯瑪森圖)是最“小”的非平面图。 一個將平面圖畫在平面上的方法稱為平版圖,又稱為圖的平面...
21 KB (3,457 words) - 00:55, 19 March 2022
图论(英語:Graph theory),是组合数学分支,和其他数学分支如群论、矩阵论、拓扑学有着密切关系。 图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关系。...
14 KB (1,957 words) - 10:30, 7 July 2024
平面圖可以指: 平面圖 (圖論),可以畫在平面上,而使邊不相交的圖 建筑平面图,描述一層樓的佈局的圖則...
172 bytes (29 words) - 18:20, 23 June 2021
在数学中,更确切地说,在图论中,一个顶点(vertex,或多个顶点,vertices)或节点(node)是构成图的基本单位:一个无向图包括一个顶点的集合和一个边(顶点的无序对)的集合,而一个有向图包括一个顶点的集合和一个弧(顶点的有序对)的集合。在一个图的示意图...
6 KB (848 words) - 23:04, 8 September 2024
拓扑图论是图论的一个分支,研究曲面中的图嵌入、图的空间嵌入及作为拓扑空间的图,还研究图的浸入。 将图嵌入曲面意味着在曲面(如球面)上绘制图,而不使两条边相交。常作为数学谜题的基本嵌入问题是三间小屋问题,其他应用如印刷电子电路,即在电路板(面)上印刷(嵌入)电路(图),且不短路。 对无向图...
4 KB (539 words) - 12:16, 21 May 2024
細分的概念應用於圖論,最早出現在1930年波蘭數學家卡齐米日·库拉托夫斯基提出的一類禁用準則(指滿足某種條件的圖就一定無法具有某個性質)中,其所提出的庫拉托夫斯基定理使用了細分圖的概念。 細分可以用於幾個與圖論相關的證明和定理,例如判斷兩圖是否同胚以及庫拉托夫斯基定理中,對於簡單圖是否為平面圖的準則,該定理為:如果一個简单图並不包含一個是...
10 KB (1,152 words) - 16:39, 13 July 2022
多面体图(英語:Polyhedral graph)是几何图论(英语:geometric graph theory)的一个概念,指凸多面体的顶点、边构成的无向图。在图论中,多面体图均为3-连通(英语:k-vertex-connected graph)平面图。 凸多面体的施莱格尔图(英语:Schlegel...
2 KB (224 words) - 18:17, 19 October 2019
柯尼格定理 (圖論)(英语:Kőnig's theorem (graph theory)) 库拉托夫斯基定理 拉姆齐定理(而且看拉姆齐理论) 门格尔定理(Menger's Theorem) 图特定理 Vizing定理 最大流最小割定理 代数图论 看以上的平面图。 R.Diestel. 图论 第四版. 高等教育出版社...
12 KB (2,051 words) - 20:31, 28 February 2023
在图论中,图属性(graph property)或图常量(graph invariant,又称图不变量)是图的一种性质,它只取决于其抽象结构,而不取决于图的表示形式如特定的图标号或图绘制形式。 虽然图的绘制和图的表示都是图论中的有效课题,但为了只关注图的抽象结构,图属性被定义为在图...
8 KB (1,092 words) - 03:25, 6 October 2020
v},则若使用集合建构式符号,轮图的边集可以表示为{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}}。 轮图是平面图,因此有唯一的平面嵌入。更进一步,每个轮图都是哈林图(英语:Halin graph)。轮图是自对偶的:轮图的平面对偶和其自身同构。除了K4...
5 KB (578 words) - 04:06, 23 November 2022
\left|V_{2}\right|=n} 的完全二分图记为 K m , n {\displaystyle K_{m,n}} 。 K1,3 K2,3 K3,3 平面图不能含有子图 K 3 , 3 {\displaystyle K_{3,3}} ;外平面图(英语:Outerplanar graph)不能含有子图 K 3 , 2 {\displaystyle...
2 KB (318 words) - 10:31, 28 April 2023
图是完全二分图。 平面图是指可以将其节点和边画在平面上,而没有两边相交的图。 阶为n≥3的循环图(英語:cycle graph)或环形图(英語:circular graph)是指其节点可以列为v1, v2, …, vn,使得图中的边为 { v i , v i +...
25 KB (3,661 words) - 05:51, 3 August 2024
在图论中,完全图是一个简单的无向图,其中每一对不同的顶点都只有一条边相连。完全有向图是一个有向图,其中每一对不同的顶点都只有一对边相连(每个方向各一个)。 图论起源于欧拉在1736年解决七桥问题上做的工作,但是通过将顶点放在正多边形上来绘制完全图的尝试,早在13世纪拉蒙·柳利 的工作中就出现了。这种画法有时被称作神秘玫瑰。...
11 KB (1,118 words) - 19:08, 17 November 2021
在图论领域的一个无向图中,满足两两之间有边连接的顶点的集合,被称为该无向图的团。团是图论中的基本概念之一,用在很多数学问题以及图的构造上。计算机科学中也有对它的研究,尽管在一个图中寻找给定大小的团达到了NP完全的难度,人们还是研究过很多寻找团的算法。 虽然对完全子图的研究可以追溯到Erdős & Szekeres...
7 KB (1,030 words) - 07:06, 16 July 2021
在图论中,如果无向图H可以通过图G删除边和顶点或收缩边得到,则称H为G的子式(minor)或次图。 图子式的提出源自瓦格纳定理,这个定理表明:当且仅当一个图不存在完全图K5和完全二分图K3,3的子式时,这个图才是平面图。 罗伯逊-西摩定理(英语:Robertson–Seymour...
18 KB (2,057 words) - 14:40, 17 March 2024
在数学的一个分支图论中,一个无向图的k次幂Gk指的是另一个有相同顶点集的图,但在G中所有距离小于k的顶点在该图中是相邻的。图的次幂常用数的次幂相关术语来表示:G2被称为G的平方,G3被称为立方,以此类推。 图的次幂应该与图本身的乘积区别开来,图的乘积(与次幂不同)通常比原图有更多的顶点。 如果一个图...
9 KB (1,216 words) - 10:36, 28 April 2023
瓦格纳定理 (category 图论)
在图论中,瓦格纳理论(英語:Wagner's theorem)是平面图的禁图表征,以Klaus Wagner的命名。 该定理说:当且仅当有限图的子式不包含完全图K5 或完全二分图K3,3 时候,那么该图就是平面的。 这是图子式论最早的结果之一,也是罗伯逊–西摩定理(Robertson-Seymour...
2 KB (197 words) - 10:32, 28 April 2023
三間小屋問題是抽象數學問題,是數學領域中拓扑图论的問題,拓扑图论是研究曲面上图的嵌入。若用正式的圖論術語,此問題在問完全二分图K3,3是否是平面图,可以讓中間的線沒有交叉。此圖形也常稱為utility graph,也稱為湯瑪森圖(Thomsen graph)。 美國數學家大衛·庫爾曼(David...
13 KB (1,578 words) - 05:01, 14 January 2024
库拉托夫斯基定理 (category 图论)
graph(英语:utility graph)。 平面图(planar graph)是可以画在平面上,使得不同的边在除了端点之外互不相交的图。 细分(subdivision)是在一个图的一些边上加入一些点,使得这些边被分割成包含一条或多条边的路径。库拉托夫斯基定理表明,一个图G是平面图,如果它不能通过细分K5或 K3...
4 KB (550 words) - 12:23, 20 August 2023
图同构(英語:graph isomorphism)描述的是图论中,两个图之间的完全等价关系。在图论的观点下,两个同构的图被当作同一个图来研究。 只有节点数目相同(即同阶)的两个图才有可能同构。两个简单图 G {\displaystyle G} 和 H {\displaystyle H} 称为是同构的,当且仅当存在一个将...
12 KB (1,819 words) - 03:19, 2 September 2023
重边 (category 图论组成结构)
当不允许重边与自环存在于图中时,多重图或伪图通常指允许重边和自环存在的图。 例如,从图论的观点来看,重边在研究电路时是有帮助的。此外,重边可体现出多维网络中核心差异的特征。 如果在已经由边连接的两个顶点之间添加一条边,平面图仍会保持其平面性;因此,增加重边不改变其平面性。 偶极图是只有两个顶点其中所有边都相互平行的图。 邊 (圖論)...
2 KB (335 words) - 10:36, 28 April 2023
亏格 (category 图论)
亏格为1。 图的亏格是最小的整数n使得图可以不用交叉就画在有n个柄的球面上(也就是亏格为n的可定向曲面)。这样,一个平面图亏格为0,因为可以画在球面上而没有自交。 图的不可定向亏格是最小的整数n使得图可以不用交叉就画在有n个交叉帽的球面上(也就是不可定向亏格为n的不可定向曲面)。 在拓扑图论中,有几种对群的亏格的定义。Arthur...
3 KB (450 words) - 01:08, 18 January 2023
图论中,图带宽问题是用不同整数 f ( v i ) {\displaystyle f(v_{i})} 给图G的n个顶点 v i {\displaystyle v_{i}} 贴上标签,使得量 max { | f ( v i ) − f ( v j ) | : v i v j ∈ E } {\displaystyle...
9 KB (1,342 words) - 19:43, 21 August 2024
图可以指: 图 (数学),数学图论中表示物件與物件之間的關係的方法 函数图形 图形,描画出物体的轮廓、形状或外部的界限 圖表,圖像化的數據 图 (数据结构),在计算机科学中用于表示图的抽象数据类型 图 (飞机),图波列夫公司制造飞机的型号 图画,美术绘画 地图,将地球或其他星球的自然现象和社会现象通过概括和符号缩绘在平面上的图形...
743 bytes (105 words) - 21:48, 14 August 2021
拓扑学的平面定義為是唯一可收縮(英语:contractible)的曲面。 若從平面中移除任何一個點,剩下的空間仍然是連通空間,但已不是單連通空間。 在圖論中,平面圖是指可以嵌入在平面中的图,也就是圖可以畫在平面上,圖的各邊只會在端點相交。換句話中,可以在平面上畫出此圖,圖的各邊不會互相交叉。這様的圖稱為平面图。...
4 KB (461 words) - 09:57, 8 July 2022
哈密顿路径问题 (category 圖論)
图和无向图上的哈密顿环问题是卡普的二十一个NP-完全问题中的其中两个。对于一些特殊类型的图来说,它们仍然是NP完全的。例如: 二分图 最大度为3的无向平面图 入度和出度最大为2的有向平面图 无桥的无向的平面3-正则二分图 3-顶点连通,3-正则的二分图 square grid graph的子图 square...
12 KB (1,578 words) - 11:31, 23 June 2024
在圖論中,二部圖(英語:Bipartite graph)是一類特殊的圖,又稱為二部图、偶图、雙分圖。二分圖的頂點可以分成兩個互斥的独立集 U 和 V 的圖,使得所有邊都是連結一個 U 中的點和一個 V 中的點。頂點集 U、V 被稱為是圖的兩個部分。等價的,二分圖可以被定義成圖中所有的環都有偶數個頂點。...
27 KB (3,752 words) - 08:14, 22 January 2024
风玫瑰图(wind rose plot)用来简单描述某一地区风向风速的分布,可分为风向玫瑰图和风速玫瑰图。在风玫瑰图的极坐标系上,每一部分的长度表示该风向出现的频率,最长的部分表示该风向出现的频率最高。风玫瑰图通常分16个方向,也有的再细分为32个方向。 在羅盤玫瑰存在之前,地圖上也包含一個玫瑰圖...
2 KB (185 words) - 03:41, 3 May 2024
五色定理 (category 图染色)
五色定理是图论中的一个结论:将一个平面分成若干区域,给这些区域染色,且保证任意相邻区域没有相同颜色,那么所需颜色不超过五种。五色定理比四色定理弱,也比四色定理更容易证明。1879年,阿尔弗雷德·布雷·肯普(英语:Alfred Kempe)给出了四色定理的一个证明,当时为人所接受,但11年后,珀西·约...
4 KB (768 words) - 07:23, 27 December 2020
四色定理 (category 图染色)
拓扑学版本的四色问题阐述可以转化为更为抽象的图论版本。这里的转化指的是一种对偶的概念。即将一个地图转化为图论中的一个无向平面图。具体来说,是将地图中的每一个国家用其内部的一个点代表,作为一个顶点。如果两个国家相邻,就在两个顶点之间连一条线。这样得到的图必然是一个平面图...
52 KB (8,239 words) - 14:56, 14 March 2024
完全点 (category 图论组成结构)
图为平面图。 星图正是树图中含有一个完全点的图,且星图可以由向独立集中添加一个完全点来构造。类似地,轮图可以由向环形图中添加一个完全点来构造。在几何学中,三维金字塔以轮图为骨架,其可推广为任何更高维金字塔的图都有一个完全点作为金字塔的顶点。 完备图(集合论中树的可比性图...
4 KB (506 words) - 21:58, 6 October 2020