Member Avatar for Hiroshe

Since trivial problems bore me, I thought I might make a weekly programming challenge for a bit of fun. Sometimes I find it fun to solve a problem, and compair it to other peoples solutions.

Let me know what you think about the idea (if you like the idea, if the problems are too easy/hard, or if I should just stop).

Rules: There are no rules. You may use any programming language, or any other method of finding the answer (even by hand).

Warning! Don't read the comments if you don't want to see other peoples solutions. You should probably try the problem out yourself before reading the comments.

Challenge #1: Graph Colourability

Difficulty: 2/5
Consider the following two graphs: Click Here
The graph on the left is said to be two-colourable (or bipartite), because you are able to colour the nodes with two colours such that no adjacent nodes are the same colour.
It is impossible to colour the graph on the right with two colours such that no adjacent nodes share the same colour. Thus, it is not two-colourable.

Out of all possible graphs with 7 nodes, how many are two-colourable?

Edited by Hiroshe
  • 1 Contributor
  • 2 Replies
  • 151 Views
  • 2 Hours Discussion Span
  • Latest Post Latest Post by Hiroshe
Member Avatar for Hiroshe

Here's my own solution in Racket.

I do not make any guarentee that my solution is correct!

647168
Time: 5.1s

colourable.zip (0.6 KB)
Edited by Hiroshe
Member Avatar for Hiroshe

Whoops! I made the mistake of assuming that the first element's colour doesn't matter. Goes to show you you shouldn't take my word for it.

379312
Time: 5.6s

colourable.zip (0.61 KB)
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.