k臨界圖(k-critical graph)是一類特殊的圖,指關於連通度的節點臨界圖。若對於圖G上任一節點v,都有k(G-v)<k(G),則稱G是關於連通度的節點k臨界圖,或者點k板小圖。若對於圖G上任一邊e,都有k-(G-e)<k(G),稱G為k極小圖,或者邊k極小圖。
基本介紹
- 中文名:k臨界圖
- 外文名:k-critical graph
- 所屬學科:數學
- 所屬問題:組合學(圖與超圖)
- 簡介:關於連通度的節點臨界圖
基本介紹








相關性質












k臨界圖(k-critical graph)是一類特殊的圖,指關於連通度的節點臨界圖。若對於圖G上任一節點v,都有k(G-v)<k(G),則稱G是關於連通度的節點k臨界圖,或者點k板小圖。若對於圖G上任一邊e,都有k-(G-e)<k(G),稱G為k極小圖,或者邊k極小圖。
色臨界圖是狄拉克(G.A.Dirac) 於1952 年首先研究的。狄拉克在1953年證明:任意 k 臨界圖都是 (k-1) 邊連通的。k 臨界圖 G 還有如下性質:(1) G 的最小度 δ(G) > k-1;(2) G 的任意頂點割不是團。分類 臨界圖[...
臨界圖 臨界圖(critical graph)是1993年公布的數學名詞。公布時間 1993年,經全國科學技術名詞審定委員會審定發布。出處 《數學名詞》第一版。
利用此本項目討論了一些特殊圖類,如圖G是二分圖,H是星圖,或G是偶圈,H是星圖,或H是星圖,G是偶圈,或G、H分別是星圖和掃帚圖等,都給出了相應的上下界。另一方面,K_{N-1}臨界圖上一定有某種邊染色,使其既無單色G又無...
格羅蔣茨圖(Grotzsch graph)是一種特殊的圖。一個4色臨界圖的例子。極圖是一類特殊的圖。指階數一定在某種意義下最大的圖。給定一個圖族L,在所有n階圖中含邊最多,不以L中圖為其子圖的圖。概念 格羅蔣茨圖(Grotzsch graph)是...
本項目將從結構上研究圖的Pfaffian性,重點研究可定向閉曲面上Pfaffian圖的結構性質、極小Brick(3-連通雙臨界圖)的結構特徵(在緊割分解的意義下圖的Pfaffian性可歸結為Brick 的Pfaffian性)、k-圈可擴圖與圖的Pfaffian性的內在聯繫、...
圖的控制與染色理論目錄目錄 第1章圖的一般點控制(1)1.1圖的點控制概念(1)1.2圖的控制數界限(4)1.3控制相關概念及參數(7)1.4乘積圖的控制數(11)1.5控制數臨界圖(14)1.6集控制與全集控制(17)1.7反集控制與...