维津定理_关于维津定理介绍|当前关注

互联网   2023-04-28 03:38:16


(资料图片)

1、 维津定理(Vizing theorem)是关于图的边着色的一个定理,若G是简单图,则Δ≤χ′(G)≤Δ+1,其中,Δ表示G上次最大的节点的次,χ′(G)表示边色数。

2、这个定理是维津(V.G.Vizing)于1964年发表的,由此可以将简单图分为二类:对任意简单图G,若χ′(G)=Δ,则称G为第1类图;否则,称G为第2类图。

相关资讯
最新资讯