## Graph coloring problem

### [1]

Given undirected connected graphs, G and m have different colors. These colors are used to color the vertices of graph G, and each vertex has a color. Is there a shading method that makes the 2 vertices of each edge in G have different colors.

### [2]

If a graph needs at least m colors to make the two vertices connected by each edge in the graph have different colors, this number m is called the chromatic number of the graph.

## Problem solving ideas

### [1]Title Link

#### problem analysis

The first is to give a picture and a fixed color, so that we can judge whether we can dye successfully or have several dyeing schemes;

#### Problem solving ideas

Backtracking + DFS

- The i-th node is dyed with dfs(i). When I > N, the dyeing is completed;
- For each node, it is necessary to enumerate all nodes connected to it to see whether the colors coincide. If the colors coincide, enumerate the next color. If a color does not coincide with the connected node, enumerate the next node (dfs(i+1));
- After all colors are enumerated, if there are still no qualified ones, go back and enumerate again;
- If you find it, you don't need to go back, because you only need to judge whether the dyeing can be successful (this should be paid special attention);

#### Code demonstration

#include<iostream> #include<cstring> using namespace std; const int maxn = 110; int G[maxn][maxn]; int color[maxn]; bool ans; int n,m,k; void init(){ //Used for array initialization ans = 0; memset(G, 0 , sizeof G); memset(color, 0 , sizeof color); } void dfs(int cur){ if(cur > n) { ans = 1; return; } for(int i=1; i<=m; i++){ //Try to paint cur nodes with each color bool flag = 1; //Nodes before cur must be colored for(int j=1; j<cur; j++){ if(G[j][cur] == 1 && color[j] == i){ flag = 0; //Not as long as there is a conflict break; } } //If i color can be painted, consider the next node if(flag){ color[cur] = i; dfs(cur + 1); //color[curr]=0; //!!! When you need to find the number of schemes, backtracking should be put here to find all schemes!!!; } //If the cur node cannot be colored at this step, return to explore other schemes else color[cur] = 0; //to flash back; } } int main(){ while(cin>>n>>k>>m){ init(); for(int i=1; i<=k; i++){ int x,y; cin>>x>>y; G[x][y] = G[y][x] = 1; } dfs(1); cout<<ans<<endl; } return 0; }

### [2]Topic exercise

#### problem analysis

Given a graph, let's find out the minimum number of colors needed for complete coloring;

#### Problem solving ideas

Use backtracking to find out all schemes and record the number of colors;

#### Code demonstration

#include<bits/stdc++.h> using namespace std; int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); } return x*f; } /* vector<int>Room[M]People in the room Traverse before selecting a room each time, which is similar to the coloring problem G[110][110]Indicates the relationship between people dfs(i,j) Indicates that the number of rooms i need to live in is j; */ int G[110][110]; int n; int ans; vector<int>Room[110]; void dfs(int x,int y){ if(y>=ans)return; //prune if(x>n){ ans=min(ans,y); // cout<<"y "<<y<<endl; return; } for(int j=1;j<=y;j++){ bool flag=1; //Judge whether this room x can live for(int i=0;i<Room[j].size();i++){ if(G[Room[j][i]][x]){ flag=0; break; } } if(flag){ //This room is available Room[j].push_back(x); dfs(x+1,y); Room[j].pop_back(); } } //Open another room for x Room[y+1].push_back(x); dfs(x+1,y+1); Room[y+1].pop_back(); } void init(){ memset(Room , 0, sizeof Room); memset(G, 0, sizeof G); ans = INT_MAX; } int main(){ init(); int m,a,b; n=read(); //Read quickly and update later m=read(); while(m--){ a=read();b=read(); G[a][b]=G[b][a]=1; } dfs(1,1); cout<<ans; return 0; }