著色數目問題（chromatic number problem）是2018年公布的計算機科學技術名詞。
基本介紹
- 中文名：著色數目問題
- 外文名：chromatic number problem
- 所屬學科：計算機科學技術
- 公布時間：2018年
定義,出處,
定義
對於給定圖 G及整數k，判定是否存在G頂點的至多使用k 種不同顏色的著色方法，使得任意邊的兩個頂點具有不同顏色的問題。
出處
《計算機科學技術名詞 》第三版。
著色數目問題
相關詞條
- 著色數目問題
著色數目問題（chromatic number problem）是2018年公布的計算機科學技術名詞。定義對於給定圖 G及整數k，判定是否存在G頂點的至多使用k 種不同顏色的著色方法，使得任意邊的兩個頂點具有不同顏色的問...
- 全著色猜想
全著色猜想 對於任何簡單圖G，均有 Δ表示G中節點的最大次。相關性質定理 圍繞這一著名猜想，人們對全著色問題進行了深入的研究：一方面，研究全著色猜想對一些特殊圖類的正確性；另一方面，給出一般圖的全色數的上界，並不斷改進。張忠輔等人研究全著色時，按全色數定義了兩類圖。即第一類圖集 和第二類圖集 。
- 圖著色問題
圖著色問題（Graph Coloring Problem, GCP） 又稱著色問題，是最著名的NP-完全問題之一。道路著色問題（Road Coloring Problem）是圖論中最著名的猜想之一。數學定義：給定一個無向圖G=（V, E），其中V為頂點集合，E為邊集合，圖著色問題即為將V分為K個顏色組，每個組形成一個獨立集，即其中沒有相鄰的頂點。其...
- 正常著色
也著上紅色；其次，將頂點c著上黃色，並將與c不鄰接的e也著上黃色；接下來，將頂點d著上藍色，並將與d不鄰接的a也著上藍色，g與d和a均不鄰接，因此它也可以著上藍色，這樣整個著色過程就結束了，的色數 。例2 考試安排問題，期末每個學校都要舉行考試，設學校開設的課程集合為X，學生集合為Y，要求學同一...
- 地圖著色
地圖著色問題是指：最少需要幾種顏色能夠完成地圖著色。著名的四色猜想為：在一個平面或球面上的任何地圖能夠只用四種顏色來著色。為了理解四色猜想問題，我們不妨先分析一下平面或球面上能夠組成一組相鄰(即兩兩相鄰)的區域數最多是幾個。先來看平面地圖，我們先從最少的數目開始排列。兩個區域相鄰是任何人都知道的...
- 重大數論問題聯合表示m理論
藉助一具歧管，將一系列重大數學問題與物理學廣義相對論和量子力學的m理論聯繫起來。起因 1，從四色定理開始 法蘭西斯·古德里於1831年生於倫敦，在1852年提出的猜想，只需要四種顏色為地圖著色。這是因為他發現在平面上或者球面上，只能有4個區域兩兩相連，英國數學家德摩根證明了平面上不存在5個區域兩兩相連。197...
- 一筆畫問題
兩兩相連的區域可以不經過其它區域到達任何一個區域。P。J希伍德以畢生精力研究四色定理，並且證明了5色定理，稀伍德考察了一般曲面著色問題提出一個推測：在有P>1個洞的封閉曲面上，足以為任何地圖著色的最小數等於（左圖上下對摺再左右對摺就是一個輪胎，7個區域兩兩相連，可以一筆畫）。一筆畫的規律 數學家歐拉...
- NP完全問題
2.任意理想圖的圖著色問題是多項式時間問題；3.任意理想圖，其圖著色問題可在多項式時間內轉換為它的最大團問題。證明大綱：定理1.設G=（V,E）是簡單無向圖，va、vb是G中距離大於2的兩個頂點，E'=E∪{（va，vb）}，則G'=(V，E')與G有相同的最大團。證明：顯然。推論：對任意簡單無向圖G=（V,E）...
- 波利亞定理
1.等邊三角形的3個頂點用紅，藍，綠3著色，有多少種方案？2.在正6面體的每個面上任意做一條對角線，有多少方案？解： 在每個面上做一條對角線的方式有2種，可認為是面的2著色問題。但面心-面心的轉動軸轉±90時，無不動圖像象。除此之外，都有不動圖像。正六面體轉動群:面的置換表示 不動: (1)(2...
- 多面體染色
多面體染色是組合數學中一類常見問題。其大致題意為：對於一個正多面體，用一定種類的顏色對其表面、頂點或（和）邊進行染色。若兩種染色方案可以通過旋轉對應，則視其為同一染色方案。題目希望求得對於給定條件下，不同染色可能的方案數目。注意，本文所指多面體染色和圖著色問題為兩類完全不同的問題。多面體染色問題...
- 色平均
色平均(chromatic average)一類組合數.指在一定條件下地圖著色的平均數.在地圖集合.l中，若參數為n;(il＞的地圖數目為A. nl, nz,…)，色和為(F_rn ,nz, ''.. .,)，則稱 (F，y ,nz，…;幾)(f1.rnl nz，…)為地圖集合才對於參數n;(＜i妻1)的色平均.色平均問題是為了研究著色問題並受到數論中...
- 細胞學
這涉及胚胎學問題。但是如果用雜交研究異種精核的功能，則需要根據異種性狀的出現來判斷，這就涉及到遺傳的問題。早期在這方面的工作基本上是由胚胎學家進行的，其特點是綜合性的研究，不是單純地從細胞的角度研究卵子，而是拿卵子作為細胞來研究與發育、遺傳等有關的問題。一些重大的問題都已勾劃出來，因而在學術思想...
- 圖論(數學的一個分支)
這個問題後來就叫做漢密爾頓問題。由於運籌學、計算機科學和編碼理論中的很多問題都可以化為漢密爾頓問題，從而引起廣泛的注意和研究。猜想 在圖論的歷史中，還有一個最著名的問題——四色猜想。這個猜想說，在一個平面或球面上的任何地圖能夠只用四種顏色來著色，使得沒有兩個相鄰的國家有相同的顏色。每個國家必須由一個...
- 拓撲(數學術語)
著名的“四色問題”也是與拓撲學發展有關的問題。四色問題又稱四色猜想，是世界近代三大數學難題之一。四色猜想的提出來自英國。1852年，畢業於倫敦大學的格斯里（Francis Guthrie）來到一家科研單位搞地圖著色工作時，發現每幅地圖都可以只用四種顏色著色。這個現象能不能從數學上加以嚴格證明呢？他和他正在讀大學的弟弟...
- 距離正則圖
距離正則圖(distance-regular graph)是一類與結合方案有關的圖。圖論是研究各種圖的性質和特徵的一門理論，主要包括圖與子圖、圖的連通性、可平面性、正則圖、樹、著色問題、圖的矩陣以及網路等內容。圖論的發展已有200多年的歷史，早在18世紀中葉就已出現有關圖的文字記載。概念 距離正則圖(distance-regular graph...
- 回溯法操作
（6）圖的m著色問題 （7）宿舍分配問題 0-1背包問題 問題：給定n種物品和一背包。物品i的重量是wi，其價值為pi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?分析：問題是n個物品中選擇部分物品，可知，問題的解空間是子集樹。比如物品數目n=3時，其解空間樹如下圖1，邊為...
- 顏色量化算法
而用計算機來顯示時，由於顯示設備所提供的能力和經濟的原因，可表示的顏色數目總是有限的。另 一方面 ，不同的計算機設備條件可顯示的顏色數目往往不同，而同一幅圖象我們希望在較低檔次的機器設備條件下得到較好的再現。面臨的問題是如何利用設備能力可提供的有限色彩數，儘可能完美再現其原圖象的色彩效果，這就是...
- 樹多項式
圖論是研究各種圖的性質和特徵的一門理論，主要包括圖與子圖、圖的連通性、可平面性、正則圖、樹、著色問題、圖的矩陣以及網路等內容。圖論的發展已有200多年的歷史。早在18世紀中葉就已出現有關圖的文字記載。這時的圖論尚處於萌芽階段，多數問題是圍繞著遊戲而產生的，最有代表性的是著名的哥尼斯堡七橋問題(...
- 拓撲學(數學學科)
四色問題 著名的“四色問題”也是與拓撲學發展有關的問題，又稱四色猜想。1852年，畢業於倫敦大學的弗南西斯.格思里來到一家科研單位搞地圖著色工作時發現：每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色。1872年，英國當時最著名的數學家凱利正式向倫敦數學學會提出了這個問題，於是四色猜想成...
- 皮膚色素
雀斑遺傳性對稱性色素異常症、種族性黑皮病、著色於皮病等 （二）內分泌因素 妊娠黃褐斑、阿狄森病、甲狀腺功能亢進肢端肥大症、庫欣綜合徵、黑棘皮病等 （三）物理機械、化學性刺激 曬斑溫熱、機械性刺激引起的色素沉著斑、焦油黑變病瑞爾黑變病、砷劑黑變病、藥物性色素沉著等 （四）炎症的色素沉著 扁平苔燕...
- 排列組合(組合數學中的一種)
計算一些物品在特定條件下分組的方法數目。這些是關於排列、組合和整數分拆的。地圖著色問題：對世界地圖著色，每一個國家使用一種顏色。如果要求相鄰國家的顏色相異，是否總共只需四種顏色？這是圖論的問題。船夫過河問題：船夫要把一匹狼、一隻羊和一棵白菜運過河。只要船夫不在場，羊就會吃白菜、狼就會吃羊。船夫的...
- 東方百合(百合屬中國栽培雜種系)
採收有5～10個花蕾的至少有2個著色，5個以下至少有1個著色才能採收。採收時間以早晨為宜。花莖剪下部位視種球是否留用而定，若種球需要再使用，植株基部應留20厘米長，並儘量不傷及留下的葉片；若種球不再使用，依市場對花枝的長度要求進行剪下。分級和包裝採收後，根據每枝花的花苞數、花莖長短及堅硬度，進行...
- 分散劑
聚合物分散劑可以提高顏料濃度，不僅增加產量，而且減少從研磨色漿直到最終產品中潛在的介質不相容性問題。所以特別是使用高相容性樹脂的條件下，聚合物分散劑擴大了基礎塗料的使用範圍。這對混合著色塗料生產非常重要。流動/流平 流平性是塗料在特定表面擴散的能力。塗料表面缺陷通常由表面張力造成，而且發生相對較快。
- 臨界邊
唯一的著色方案中，穩定集就是包含x的那些團的配偶。由於 屬於 個最大團。這 個團的配偶同時屬於 和 。這使得圖中僅剩下了 個頂點，其中包含頂點 和穩定集S，並且 和 。推論 設G是一個可分圖，如果邊 不出現在任何最大團中，則 是可分的。如果 是未出現在任何最大穩定集中的不相鄰頂點，則 是可分的。
- 近代數學
1852年，畢業於倫敦大學的弗南西斯.格思里來到一家科研單位搞地圖著色工作時，發現了一種有趣的現象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家著上不同的顏色。”這個結論能不能從數學上加以嚴格證明呢？他和在大學讀書的弟弟格里斯決心試一試。兄弟倆為證明這一問題而使用的稿紙已經堆了一大疊，...
- 匹配多項式
例如，算法及其複雜性的理論和組合計算幾何的出現與發展等，就是直接的產物.在圖論近50年來的成果中，四色問題的計算機驗證、希伍德地圖著色問題的解決以及塔特多項式的出現等，也是對整個數學領域的重要貢獻。關於中國在圖論方面近30年來的發展，可參見顏基義等人在《中國自然科學年鑑》1989年卷的數學進展專欄中發表的...
- 掩模圖形拆分
圖形拆分可以被認為是有條件的間距問題，基於設計規則定義一系列拆分規則，根據拆分規則完成圖形分解。拆分規則會對版圖上的多邊形尺寸、間距提出要求。違反規則的位置被定義為“衝突“，拆分過程即消除衝突的過程。拆分規則定義完成後，可以藉助EDA工具完成拆分。EDA軟體往往會將拆分問題轉化成有約束條件的著色問題來進行計算...
- 甜椒(茄科辣椒屬植物)
尤其對於彩椒來說，果形、著色直接關乎價格高低、收入多少，非常重要。因此，在甜椒管理上，合理整枝、留枝是必不可少的。所以說，甜椒整枝時首先要看種植密度，不能生搬硬套別人的經驗。甜椒在每畝地上的生長空間是一定的，適宜生長的枝條數也是一定的。種植實踐表明，甜椒每畝的主枝數保留在5000-7000之間為好。也...
- 正常細胞
比利時動物學家布拉謝從胚胎學的問題出發，利用專一的染色方法研究核酸在發育中的，意義。差不多與此同時，瑞典生化學家卡斯珀松根據各種物質對一定波長的吸收，創建了紫外線細胞分光光度計，來檢測蛋白質、DNA和RNA這些物質在細胞中的存在。他們的工作引起人們對核酸在細胞生長和分化中的作用的重視。在他們工作的基礎...
