TADM2E 5.5 - Revision history

Matt: Matt moved page TADME 5.5 to TADM2E 5.5 over redirect: revert

2020-08-01T00:58:00Z

Matt moved page TADME 5.5 to TADM2E 5.5 over redirect: revert

FuckMatt: FuckMatt moved page TADM2E 5.5 to TADME 5.5

2020-07-31T09:39:35Z

FuckMatt moved page TADM2E 5.5 to TADME 5.5

Goku321 at 11:05, 31 May 2015

2015-05-31T11:05:04Z

Algowikiadmin: Recovering wiki

2014-09-11T18:13:00Z

Recovering wiki

New page

Graphs with max degree 2, can be bipartite (even number of edges) or tripartite (odd number of edges)

-----

Consider a triangle (3 edges, 3 vertices): it's not bipartite even though every node has an even number of edges and the graph has an even number of edges.

-----

For such a graph, such that the degree of every vertex is at most 2, we can use
a DFS traversal, coloring the child the opposite color of the parent.
When we see a Back edge, we color the currently discovered child with a
color different that the parent, and also different from the ancestor
discovered through that back edge.

Since there is just one traversal, it runs in O(m + n) (m edges, n vertices)

← Older revision		Revision as of 11:05, 31 May 2015
Line 15:		Line 15:

	Since there is just one traversal, it runs in O(m + n) (m edges, n vertices)		Since there is just one traversal, it runs in O(m + n) (m edges, n vertices)
		+
		+	-----
		+
		+	Another Solution:
		+
		+	A graph whose each vertex has degree at most K has chromatic number less than equal to K + 1.
		+
		+	It is given that each degree has vertex at most 2, therefore determine whether the graph is two colourable or not with the help of BFS traversal. If it is then the answer is 2 otherwise the answer is 3. If graph has only one vertex then the answer will be 1.
		+
		+	Let me know whether the solution is right? (sah.sslpu@gmail.com) BTW it is right!

← Older revision	Revision as of 00:58, 1 August 2020
(No difference)

← Older revision	Revision as of 09:39, 31 July 2020
(No difference)