用1种颜色部分着色图形

时间:2022-10-23 00:20:52

I just started reading graph theory and was reading about graph coloring. This problem popped in my mind:

我刚开始阅读图论,正在阅读图着色。这个问题突然出现在我脑海中:

We have to color our undirected graph(not completely) with only 1 color so that number of colored nodes are maximized. We need to find this maximum number. I was able to formulate an approach for non cyclic graphs :

我们必须仅使用1种颜色为无向图(不完全)着色,以便最大化彩色节点的数量。我们需要找到这个最大数量。我能够为非循环图制定一种方法:

My approach : First we divide graph into isolated components and do this for each component. We make a dfs tree and make 2 dp arrays while traversing it so that root comes last :

我的方法:首先,我们将图形划分为独立的组件,并为每个组件执行此操作。我们制作一个dfs树,并在遍历它时制作2个dp数组,以便root来到最后:

dp[0][u]=sum(dp[1][visited children])

dp[1][u]=sum(dp[0][visited children])

ans=max(dp[1][root],dp[0][root])

dp[0][i] , dp[1][i] are initialized to 0,1 respectively.

dp [0] [i],dp [1] [i]分别初始化为0,1。

Here 0 signifies uncolored and 1 signifies colored.

这里0表示无色,1表示有色。

But this does not work for cyclic graphs as I have assumed that no visited children are connected.

但这不适用于循环图,因为我假设没有访问过的孩子。

Can someone guide me in the right direction on how to solve this problem for cyclic graphs(not by brute force)? Is it possible to modify my approach or do we need to come up with a different approach? Would a greedy approach like coloring a nodes with least edges work?

有人能指导我如何为循环图解决这个问题(而不是蛮力)吗?是否有可能修改我的方法或我们是否需要提出不同的方法?像边缘最少的节点着色一样贪婪的方法会起作用吗?

1 个解决方案

#1


This problem is NP-Hard as well, and is known as maximum independent set problem.

这个问题也是NP-Hard,并且被称为最大独立集问题。

A set S<=V is said to be Independent Set in a graph if for each two vertices u,v in S, there is no edge (u,v).

如果对于S中的每两个顶点u,v,则没有边(u,v),则集合S <= V在图中被称为独立集。

The maximum size of S (which is the number you are seeking) is called the independence number of the graph, and unfortunately finding it is NP-Hard.

S的最大大小(你正在寻找的数字)被称为图的独立数,不幸的是它发现它是NP-Hard。

So, unless P=NP, your algorithm fails for general purposes graphs.

因此,除非P = NP,否则您的算法会因一般用途图而失败。


Proving it is fairly simple, given a graph G=(V,E), create the complementary graph G'=(V,E') where (u,v) is in E' if and only if (u,v) is NOT in E.

证明它是相当简单的,给定图G =(V,E),创建互补图G'=(V,E')其中(u,v)在E'中当且仅当(u,v)是不在E.

Now, given a graph G, there is a clique of size k if and only if there is an independent set of size k in G', using the same vertices (since if (u,v) are two vertices the independent set, there is no edge (u,v) in E', and by definition there is an edge in E. Repeat for all vertices in the independent set, and you got a clique in G).

现在,给定一个图G,当且仅当在G'中存在一个独立的大小为k的集合时,才使用相同的顶点(因为如果(u,v)是两个顶点的独立集合,那么在E'中没有边(u,v),根据定义,在E中有一条边。对独立集中的所有顶点重复,你在G)中得到一个集团。

Since clique problem is NP-Hard, this makes this one such as well.

由于集团问题是NP-Hard,这使得这个问题很好。

#1


This problem is NP-Hard as well, and is known as maximum independent set problem.

这个问题也是NP-Hard,并且被称为最大独立集问题。

A set S<=V is said to be Independent Set in a graph if for each two vertices u,v in S, there is no edge (u,v).

如果对于S中的每两个顶点u,v,则没有边(u,v),则集合S <= V在图中被称为独立集。

The maximum size of S (which is the number you are seeking) is called the independence number of the graph, and unfortunately finding it is NP-Hard.

S的最大大小(你正在寻找的数字)被称为图的独立数,不幸的是它发现它是NP-Hard。

So, unless P=NP, your algorithm fails for general purposes graphs.

因此,除非P = NP,否则您的算法会因一般用途图而失败。


Proving it is fairly simple, given a graph G=(V,E), create the complementary graph G'=(V,E') where (u,v) is in E' if and only if (u,v) is NOT in E.

证明它是相当简单的,给定图G =(V,E),创建互补图G'=(V,E')其中(u,v)在E'中当且仅当(u,v)是不在E.

Now, given a graph G, there is a clique of size k if and only if there is an independent set of size k in G', using the same vertices (since if (u,v) are two vertices the independent set, there is no edge (u,v) in E', and by definition there is an edge in E. Repeat for all vertices in the independent set, and you got a clique in G).

现在,给定一个图G,当且仅当在G'中存在一个独立的大小为k的集合时,才使用相同的顶点(因为如果(u,v)是两个顶点的独立集合,那么在E'中没有边(u,v),根据定义,在E中有一条边。对独立集中的所有顶点重复,你在G)中得到一个集团。

Since clique problem is NP-Hard, this makes this one such as well.

由于集团问题是NP-Hard,这使得这个问题很好。