色临界图
數學分支圖論中，色临界图或臨界圖（）是图染色问题中一类特殊的圖，從此類圖中，移除任何一邊或一點，皆會使圖的色數減少。这一类图具有一些非常好的性质，能在很多证明定理中发挥用处。 定义 如果图G的任意一个真子图G'\subset G，其色數均满足\chi(G')，则称G为\chi(G)色临界图（）。 相关定义 图染色数 对于给定的图G，存在k种颜色和一种染色方案，将图中G每一个顶点都染成k种颜色中的一种。如果染色方案满足一下条件，那么将称该…
标签：#图族
共 10 篇文章
圖蘭圖
{{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…
正則圖
圖論中，正則圖（）或正規圖是每個頂點都有相同數目的相鄰點的圖，即每個頂點都有相同的度。一個正則的有向圖也必須滿足對於每個頂點，其入度與出度相同。若每個頂點的度均為 k，稱為 k-正則圖（）。 特殊例 度數至多為 2 的正則圖很容易分類： 0-正則圖是不相連的頂點組成 1-正則圖由不相連的邊組成 2-正則圖由不相連的環和無限鏈的互斥聯集組成 而 3-正則圖稱為立方圖或三次圖。4-正則圖則稱為四次圖（quartic graph）。同樣地，對…
強正則圖
圖論中，強正則圖（，SRG）是一個正則圖 G=(V,E)，有 v 個頂點和 k 度，並且滿足以下條件：對於給定的整數 \lambda, \mu \ge 0， 任意兩個相鄰頂點都有 \lambda 個共同鄰居 任意兩個不相鄰頂點都有 \mu 個共同鄰居 這樣的強正則圖通常記作 \text{srg}(v,k,\lambda,\mu)。它的補圖也是一個強正則圖，記作 \text{srg}(v,v-k-1,v-2-2k+ \mu,v-2k+\l…
小世界網路
在网络理论中，小世界网络是指一类特殊的复杂网络结构，在這種网络中大部份的节点彼此并不相连，但绝大部份节点之间經过少數幾步就可到達。 在日常生活中，人們或会发现，某些令人認為与自身相隔甚為“遥远”的人，其实与自己甚為“接近”。而小世界网络就是对此种现象（也称为小世界现象）的数学描述。就数学中图论的语言来说，小世界网络就是一个由大量顶点构成的图，其中任意两点之间的平均路径长度比顶点数量小得多。除社会人际网络外，小世界网络的例子也可見於生物学…
无尺度网络
在网络理论中，无尺度网络（Scale-free network，或称无标度网络）是带有一类特性的复杂网络，其典型特征是在网络中的大部分节点只和很少节点连接，而有极少的节点与非常多的节点连接。这种关键的节点（称为“枢纽”或“集散节点”）的存在使得无尺度网络对意外故障有强大的承受能力，但面对协同性攻击时则显得脆弱。现实中的许多网络都带有无尺度的特性，例如因特网、金融系统网络、社会人际网络等等。 源起 无尺度网络的概念是随着对复杂网络的研究而…
立方图
是立方图]] K_{3,3}是立方二分图]] 在图论中，若一个图的每个顶点度数均为三，则称其为立方图（Cubic graph）、3-正则图或三次图。 彼得森图、汤玛森图等都是立方图。 对称性 1932年，首先寻找立方的例子，并收集为。许多著名的图都是立方对称图，如汤玛森图、彼得森图等。威廉·湯瑪斯·圖特用满足下列性质的最大整数s来对立方对称图进行分类：图的自同构群在其所有长度为s的路径（其中不能有重复的边）组成的集合上作用是传递的。他证…
空圖
在圖論中，空圖可以代表無任何元素的圖（如空集合）、階數為0的圖（如K0）或雖有頂點但沒有任何邊的圖（如無邊圖，英語：）。 性質 若空圖包含了n個頂點，則其可以記為N_n。 空圖的大小（即邊的數量）恆為0， 然而空圖的階數（即頂點的數量）不一定為0。，階數不為零的空圖（即有頂點存在的圖）又稱為無邊圖。 零階圖 在圖論中，零階圖（K0）是一種沒有任何頂點的圖，因此其階數為0，且不存在任何邊。零階圖是階數為零的正則圖，然而其不存在頂點，因此也…
双连通图
在图论中，一个点双连通图是一个连通且“不可分离”的图，意思是如果任何一个顶点被去除，图仍是连通的。所以这样一个双连通图就没有。的性质和点双连通是几乎等价的，除了一条边连接两个点构成的图，它是点双连通的，但不是2-点连通的。 这个性质在维护一个有2度冗余的图中特别有用，为了防止去除一条边（或连接）之后的不连通。 由于冗余的这种特性，双连通图的使用在网络领域非常重要（参见网络流）。 定义 一个双连通的无向图是一个连通图，不会因为删除任一个节…
多分圖
在數學的分支圖論中，一個 *k-分圖*是一個图，其點集被分成 k 部分，各部分各自形成独立集。換句话說，可以把圖的所有點著色，使得相鄰的點著不同色且總共用了k 個顏色。k = 2 的情況被稱作二分圖，而 k = 3 的情況被稱作三分圖。 事實上，辨別一個圖是二分圖只需要多項式時間。但當 k > 2，辨別一個圖是否為 k-分圖卻是NP完全的 。不過，在一些圖論的應用場合中，給計算器處理 k-分圖會包含 k 個部份的劃分，比如說各個部分所代…