圖同態
数学分支圖論中，圖同態（）是兩幅图之間保結構的映射。具體而言，該映射將某圖的各顶点映至另一圖的頂點，且若兩頂點相鄰，則其像仍然相鄰。 同態是若干種圖着色概念的推廣，適用於表達一類重要的約束滿足問題，如排程、問題。同態可以複合，為全體圖組成的類賦予豐富的代數結構：其上的预序关系、分配格結構、範疇結構（分為無向圖範疇與有向圖範疇兩種）。欲尋找任意兩圖間的同態，而無額外條件，則現時所知的高得不切實際，但對於某些特定類別的圖，已知有多項式時間算…
标签：#图论
共 82 篇文章
奥尔定理
奥尔定理是挪威数学家奥斯丁·欧尔在1960年证明的图论定理。它为判断图为哈密顿图提供了一个充分条件，并且从本质上说明了如果一个图具有足够多的边，则它必然包含哈密顿环。具体来说，如果一个图中每一对非相邻顶点的度数和都大于等于顶点总数，那么该图为哈密顿图。 内容 设 为（有限的）简单无向图，其顶点数 。 奥尔定理表明，如果对每对 中的不相邻顶点对 和 ，均有 那么 是哈密顿图。 式中， 表示 中顶点 的度数（即与 相连的边数）。 证明 ，但…
艾狄胥-斯通定理
中，埃尔德什－斯通定理（）是禁止某子圖H出現後，圖邊數的漸近上界，推廣了图兰定理（即僅允許H為完全圖的情況）。定理由埃尔德什·帕尔與於1946年證明，因而得名。稱其為「極值圖論的基本定理」。 圖蘭圖的極值函數 先定義極值函數（）\mathrm{ex}如下：\mathrm{ex}(n; H)是眾多n個頂點的圖之中，不包含子圖（同構於）H的圖的邊數最大值。圖蘭定理斷言，當H取為完全圖K_r時，有\mathrm{ex}(n; K_r) = t…
艾狄胥－波沙定理
在圖論中，艾狄胥－波沙定理（）由保羅·艾狄胥與 Lajos Pósa 於 1965 年證明
騎士巡邏
騎士巡禮（）是指在按照国际象棋中骑士的规定走法走遍整个棋盘的每一个方格，而且每个网格只能夠经过一次。假若騎士能夠從走回到最初位置，則稱此巡禮為「封閉式巡禮」，否則，稱為「開放巡禮」。對於88棋盤，一共有26,534,728,821,064種封閉巡禮，有19,591,828,170,979,904種開放式巡禮。 由骑士巡禮引申出了一个著名的数学问题 ：骑士巡禮问题--找出所有的骑士巡禮路徑。編寫一個程式来找出骑士巡禮路徑經常在计算机系的学…
图子式
在图论中，如果无向图H可以通过图G删除边和顶点或收缩边得到，则称H为G的子式（minor）或次图。 图子式的提出源自瓦格纳定理，这个定理表明：当且仅当一个图不存在完全图K5和完全二分图K3,3的子式时，这个图才是平面图。 表明，对于任何在图上删除点或边或收缩边保留的性质，类似的'（forbidden minor characterization）也存在。 给定图G和图H，可以在多项式时间内判断H是否是G的子式。 连同上述禁子式表征，这意…
團 (圖論)
在图论领域的一个无向图中，满足两两之间有边连接的顶点的集合，被称为该无向图的团。团是图论中的基本概念之一，用在很多数学问题以及图的构造上。计算机科学中也有对它的研究，尽管在一个图中寻找给定大小的团达到了NP完全的难度，人们还是研究过很多寻找团的算法。 虽然对完全子图的研究可以追溯到中拉姆齐理论对图理论的重组，“团”这一术语本身其实源自 ，那篇文章中社会网络的完全子图被用来模拟一“团”人，也就是一组两两相互认识的人。团在科学领域特别是在生…
割宽
图论中，无向图的割宽（cutwidth）是能满足下列性质的最小整数k：图存在顶点排序，使得将顶点划分为排序的前后子集所得的割至少跨过k条边。具体点说，若将顶点编上号v_1,v_2,\dots v_n，则\forall\ell=1,2,\dots n-1，使i\le\ell,\ j>\ell的边v_iv_j最多有k条。 图的割宽也叫做其耐折数（folding number）。产生割宽的顶点排序以及计算这种排序与割宽的问题，统称为最小割线性…
共識動力學
共識動力學（consensus dynamics，agreement dynamics）是結合系统科学及图论的研究領域，其中研究的主要問題之一就是在多智能体系统中的共識問題（agreement problem，consensus problem）。 多智能体系统是指利用多個互相影響的智能設備來達到共同目的的系統。智能設備會形成網路，交換資訊以達到共識，這類系統包括生理系統、基因網絡、大型能源系統以及陸地、空中或太空中的車隊或是機隊。共識…
图的遍历
图的遍历问题分为四类： 遍历完所有的边而不能有重复，即所謂“欧拉路径问题”（又名一笔画问题）； 遍历完所有的顶点而没有重复，即所谓“哈密頓路径问题”。 遍历完所有的边而可以有重复，即所谓“中国邮递员问题”； 遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。 对于第一和第三类问题已经得到了完满的解决，而第二和第四类问题则只得到了部分解决。 第一类问题就是研究所谓的欧拉图的性质，而第二类问题则是研究所谓的哈密顿图的性质。 算法 图的遍…
凱萊公式
在图论中，凯莱公式（）计算完全图的生成树的总数。若有n个顶点，生成树的数量是n^{n-2}。 这个定理以阿瑟·凯莱的名字命名。 证明办法 使用矩阵树定理 使用母函数 * 普吕弗序列 参考文献
传输理论
传输理论（、），又称为运输理论，是数学、经济学等学科中研究最优运输和资源配置的理论。该问题最早由法国数学家加斯帕尔·蒙日于1781年提出。 1920年代，A·N·托尔斯泰是最早运用数学方法研究传输问题的学者之一。1930年，他在苏联国家交通部编纂的《运输规划》第一卷中发表了题为《寻找太空货物运输的最小千公里方法》的论文。 第二次世界大战期间，苏联数学家、经济学家列昂尼德·坎托罗维奇在该领域取得了重要进展。因此，这一问题有时也被称为蒙日-…
组装理论
）的可能性就越大。]] 组装理论并非将物体的复杂性视为空间中粒子的集合，而是通过其组装历史来表征。应用于化合物复杂性研究时，它是首个可进行实验验证的技术 ，这与其他无法验证的算法截然不同。 组装理论由格拉斯哥大学化学家勒罗伊·克罗宁（Leroy Cronin）领导的团队于2017年提出。 在该理论中，物体并非被定义为空间中粒子的集合，而是由其可能的形成历史来定义。为了计算物体的复杂性，需要将其递归地分解为各个组成部分，并将物体的“组装空…
极值圖論
T(13, 4)。在所有 n 個點但不包含 (r + 1)-團的簡單圖中，圖蘭圖 T(n, r) 的邊數最多。]] 極值圖論是數學中組合數學的一個分支，它結合了極值組合學與圖論的研究方法與問題。本質上，極值圖論探討了圖的局部子結構如何影響全域性質，極值圖論的研究多半在描述圖中全域性質（如頂點數、邊數）和局部性質（如子圖存在性）間的定量關係。 極值圖論中的問題多半可以表述為最佳化問題：當一張圖滿足某些限制時，某個圖參數的最大值（或最小值）…
圖蘭圖
{{Infobox graph | name = 圖蘭圖 | image = | image_caption = 圖蘭圖 T(13,4) | namesake = 圖蘭·帕爾 | vertices = n | edges = ~\left(1- \frac{1}{r}\right)\frac{n^2}{2} | radius = \left\{\begin{array}{ll}\infty & r = 1\\ 2 & r \le n/2…
柯尼斯堡七桥问题
柯尼斯堡七桥问题（；英語：Seven Bridges of Königsberg）是图论中的著名问题。这个问题是基於一個現實生活中的事例：當時東普魯士柯尼斯堡（今俄羅斯加里寧格勒）市区跨普列戈利亚河两岸，河中心有兩個小島。小島與河的兩岸有七條橋連接。在所有橋都只能走一遍的前提下，如何才能把这个地方所有的橋都走遍？ 解決方式 莱昂哈德·欧拉在1735年提出，並沒有方法能圓滿解決這個問題，他更在第二年发表在论文《柯尼斯堡的七桥》中，證明符合…
塞梅雷迪正則性引理
在極值圖論中，塞梅雷迪正則性引理（）由 Endre Szemerédi 證明
切格不等式 (圖論)
在譜圖論中，切格不等式（）建立圖拉普拉斯矩陣第二小特徵值 \lambda_2 與圖的切格常數（，又稱等周常數（））之間的雙向關係。此不等式由 Jeff Cheeger 在黎曼流形上提出
警察與小偷遊戲
警察與小偷遊戲（）是圖論中的追蹤－迴避博弈（）：一名或多名警察與一名小偷在圖的頂點上移動，輪流行動，警察能否在有限步內與小偷同處一頂點即獲勝。此博弈與樹寬（）、可拆解圖（）及圖搜尋理論密切相關。
稀疏割
在圖論與近似演算法中，稀疏割問題（）要求將圖的頂點集分成兩部分，使跨越分割的邊相對於兩側「體積」（）的比例最小。此問題同時要求分割既稀疏（跨割邊少）又均衡（兩側大小相近），是譜圖論、擴展圖與圖分割中的核心問題。