图的着色问题-信号与系统分析吴京第二版
图9.12彼得森图可以收缩成K5 9.4图的着色问题9.4.1地图染色与四色猜想与平面图有密切关系的一个图论应用问题是图的着色。图的着色问题起源于地图染色问题和四色猜想。例如，对图9.13所示的中国地图，要给每个省份染色，使得任何两个相邻的省份颜色均不同。与江西省相邻的省份有浙江、福建、广东、湖南、湖北、安徽，要使得这7个省份中任何两个相邻省份颜色均不同，至少需要使用3种颜色。图9.13给出了一个用3种颜色染色的方案：江西省染为红色（r），浙江、广东、湖北染为绿色（g），福建、湖南、安徽染为蓝色（b）。现在的问题是，要给所有省份染色，使得任何两个相邻的省份颜色均不同，至少需要使用多少种颜色？
文件大小：6.83MB
评论区