Questions tagged [graph-theory]
For challenges regarding graphs, mathematical structures used to model relations between objects.
12
votes
10answers
946 views
Simulate an NFA
A nondeterministic finite automaton is a finite state machine where a tuple \$(state,symbol)\$ is mapped to multiple states. Ie. we replace the usual \$\delta : Q \times \Sigma \to Q\ \$ transition ...
8
votes
12answers
249 views
Construct a line graph / conjugate graph
Introduction
Given an undirected graph G, we can construct a graph L(G) (called the line graph or conjugate graph) that represents the connections between edges in G. This is done by creating a new ...
14
votes
6answers
642 views
Graph 5-Coloring
Honestly, I can't believe this hasn't already been asked, but here it is
Background
Given a simple undirected planar (the graph can be drawn in the plane without intersections) graph, it is a proven ...
13
votes
12answers
2k views
Small Ramsey Numbers
Background: the Ramsey number \$R(r,s)\$ gives the minimum number of vertices \$v\$ in the complete graph \$K_v\$ such that a red/blue edge coloring of \$K_v\$ has at least one red \$K_r\$ or one blue ...
15
votes
5answers
953 views
Minimum operations to get from one number to another
Let's define a simple language that operates on a single 8-bit value.
It defines three bitwise operations (code explanation assumes 8-bit value variable):
...
15
votes
4answers
460 views
Generate a Portmantout!
Background
Three years ago, this guy Tom Murphy got it into his head to extend the idea of a portmanteau to all words in a language and called this a portmantout (portmanteau plus tout [French for ...
15
votes
7answers
636 views
Binary tree rotations
Balanced binary search trees are essential to guarantee O(log n) lookups (or similar operations). In a dynamic environment where a lot of keys are randomly inserted and/or deleted, trees might ...
24
votes
10answers
2k views
Knight Distance
In Chess, a Knight on grid (x, y) may move to (x-2, y-1), (x-2, y+1), (x-1, y-2), (x-1, y+2), (x+1, y-2), (x+1, y+2), (x+2, y-1), (x+2, y+1) in one step. Imagine an infinite chessboard with only a ...
23
votes
12answers
2k views
Drunkard's Journey Home
Drunkard's Journey Home
In this challenge you are to write a program which simulates a drunkard stumbling his way home from the bar.
Input:
The input will be an adjacency matrix (representing a ...
16
votes
14answers
587 views
Transitive Equality
The Challenge
Your program should take 3 inputs:
A positive integer which is the number of variables,
A set of unordered pairs of nonnegative integers, where each pair represents an equality between ...
13
votes
7answers
347 views
Cutpoints in a maze
A maze is given as a matrix of 0s (walls) and 1s (walkable space) in any convenient format. Each cell is considered connected to its 4 (or fewer) orthogonal neighbours. A connected component is a set ...
10
votes
5answers
382 views
Get Two from One
As we saw in this question complex logical statements can be expressed in terms of the simple connectives of generalized Minesweeper. However Generalized minesweeper still has redundancies.
In order ...
19
votes
13answers
2k views
Check if all non-zero elements in a matrix are connected
Input:
A matrix containing integers in the range [0 - 9].
Challenge:
Determine if all non-zero elements are connected to each other vertically and/or horizontally.
Output:
A truthy value if all ...
13
votes
3answers
1k views
Hexcellent Minesweeping
Hexcells is a game based off of Minesweeper played on hexagons. (Full disclosure: I have nothing to do with Hexcells. In fact I don't really like the game.) Most of Hexcells rules can be pretty ...
10
votes
2answers
423 views
9
votes
1answer
354 views
Advent Challenge 2: The Present Vault Raid!
<< Prev Next >>
Challenge
Now that Santa has finally figured out how to get into his present vault, he realises that somehow the elves got in there before him and stole some of his presents! ...
13
votes
4answers
1k views
Is it bipartite?
A bipartite graph is a graph whose vertices can be divided into two disjoint set, such that no edge connects two vertices in the same set. A graph is bipartite if and only if it is 2-colorable.
...
8
votes
5answers
437 views
Demonstrate a lower bound for the Ramsey number R(4,4)
A special case of Ramsey's theorem says the following: whenever we color the edges of the complete graph on 18 vertices red and blue, there is a monochromatic clique of size 4.
In language that ...
10
votes
3answers
313 views
What's assignable to what?
related
What's assignable to what?
In this challenge you will be given two types, A and B and determine if ...
6
votes
4answers
299 views
Who's Going? Can you help me?
If Abe goes, then Beth and Diana go. If Beth goes, then Catherine goes. If Catherine goes, then Diana goes. If Diana goes, then Ezra goes. Only three people go. Who goes?
Challenge
Given a list of ...
18
votes
7answers
945 views
Longest hypercube path
Challenge
You are given two distinct bit strings of the same length. (For example, 000 and 111.) Your goal is to find a path ...
26
votes
8answers
2k views
Somewhere On The Tube …But On Which Lines?
The London Underground A.K.A. The Tube is the oldest underground railway in the world, it currently consists of eleven lines* servicing 267 named stations (strictly 269** stations since "Edgware Road" ...
22
votes
13answers
2k views
Do the NP: find the largest clique
Background
At the time of writing this, the P vs NP problem is still unsolved, but you might have heard of Norbert Blum's new paper claiming proof that P != NP, which is already suspected to be ...
13
votes
0answers
405 views
Determine if a Graph is Toroidal
A simple graph is toroidal if it can be drawn on the surface of a torus without any edges intersecting. Your task is to take a simple undirected graph via any reasonable method (adjacency matrix, ...
19
votes
8answers
663 views
Optimal path through a matrix
Given a matrix consisting of positive integers, output the path with the lowest sum when traversing from the upper left element to the bottom right. You may move vertically, horizontally and ...
7
votes
1answer
193 views
How related are two relatives?
The coefficient of relationship refers to how much DNA two persons have in common. A parent has 50% common DNA with their child (unless the parents are related), so to calculate it we have to find all ...
10
votes
2answers
1k views
Solve the Trolley Problem
Philosophers have long pondered the Trolley problem. Unfortunately, no human has solved this problem yet. Luckily, as programmers we can use computers to solve the problem for us!
Input
Your program ...
14
votes
3answers
627 views
Calculate Treewidth
The treewidth of an undirected graph is a very important concept in Graph Theory. Tons of graph algorithms have been invented which run fast if you have a decomposition of the graph with small ...
7
votes
4answers
902 views
Burning Bridges
Note: When I refer to a bridge, I mean it in the non-mathematical sense
Introduction
You are on a network of islands which are connected by wooden bridges and you want to see if you can burn every ...
7
votes
3answers
124 views
Rooting for Trees With the Right Nodes
Background
A rooted tree is an acyclic graph such that there is exactly one path from one node, called the root, to each other node. A node v is called the parent ...
7
votes
8answers
846 views
Is the graph acyclic?
A Directed Acyclic Graph (DAG) is a type of graph that has no cycles in it. In other words, if there is a link from node A to node B, there exists no path from B to A (via any nodes).
Challenge
...
7
votes
0answers
300 views
Don't break the bridges!
Introduction:
You are a worker, who is in charge of managing a set of bridges, connecting a square grid of "nodes":
...
5
votes
1answer
204 views
Broken Path Detection
Challenge
Given a plot with broken paths, return the plot with all paths connected in the minimum number of changes.
Explanation
This problem deals with graphs on the Cartesian plane. Every node ...
23
votes
1answer
669 views
Is it a Cactus?
In graph theory, a Cactus is a connected graph such that any distinct two simple cycles in the graph share at most one vertex.
Here is a Cactus with 3 simple cycles outlined with dashed lines.
The ...
9
votes
6answers
963 views
Given a Tree generate its Prüfer Code
In graph-theory a Prüfer code is a unique sequence of integers that denotes a specific tree.
You can find the Prüfer code of a tree with the following algorithm taken from Wikipedia:
Consider a ...
10
votes
2answers
271 views
The von Koch conjecture
You may know the mathematician von Koch by his famous snowflake. However he has more interesting computer science problems up his sleeves.
Indeed, let's take a look at this conjecture:
Given a tree ...
14
votes
7answers
458 views
Find a set of maximal matching edges
Consider a connected undirected graph. A matching set of edges on this graph is defined as a set of edges such that no two edges in the set share a common vertex. For example, the left figure denotes ...
30
votes
2answers
737 views
Help Pac-Man count the Pac-Dots
On the advice of Ms. Pac-Man who's worried about him getting overweight, Pac-Man has decided to keep track of his daily Pac-Dot intake. Help him count the number of Pac-Dots on a given path in the ...
30
votes
8answers
5k views
Should we be friends?
Note this is a question primarily focusing on data-structures
Introduction
Bacefook wants people to be friendlier! As such, they are implementing a new system to suggest friends! Your task is to ...
18
votes
2answers
246 views
Island Golf #2: The Eccentric Hermits
This is the second in a series of Island Golf challenges. Previous challenge
Two hermits have arrived on a desert island. Since they came seeking solitude, they wish to live as far away from each ...
20
votes
9answers
1k views
Enumerate binary trees
Binary trees
A binary tree is a tree with nodes of three types:
terminal nodes, which have no children
unary nodes, which have one child each
binary nodes, which have two children each
We can ...
13
votes
3answers
575 views
Grids can be curvy. How long is yours?
Consider depicting a simple, open, two-dimensional curve on a W wide by H high grid of text where X represents part of the curve and ...
22
votes
10answers
2k views
Two-Coloring Overlapping Circles
Write a program or function that takes in the following input in a reasonable format of your choice:
Two positive integers W and H that define the width and height of the image you'll be generating.
...
9
votes
2answers
281 views
Is my Graph Graceful?
A Graceful Graph is a type of Simple Graph. Graceful graphs are special because there is a way to label all their nodes with positive integers so that when the edges are also labeled with the ...
15
votes
6answers
548 views
Is this Sequence Graphic?
A graphic sequence is a sequence of positive integers each denoting the number of edges for a node in a simple graph. For example the sequence 2 1 1 denotes a ...
13
votes
4answers
376 views
Negative Space Graphs
Task
You will be given a positive integer and you must output a "self-complementary graph" with that many nodes. If you don't know what a self-complementary graph is the wikipedia article wont help ...
19
votes
7answers
581 views
Longest Cycle in a Graph
Given a directed graph, output the longest cycle.
Rules
Any reasonable input format is allowed (e.g. list of edges, connectivity matrix).
The labels are not important, so you may impose any ...
26
votes
3answers
779 views
Arranging Bubbles
Note, challenge copied from question asked at math.stackexchange.
Recently, I attained quite some skill at blowing bubbles. At first I would blow bubbles like this:
But then things started getting ...
-3
votes
1answer
195 views
Find an Eulerian Circuit
Challenge
You have been assigned a task to write a program which takes a multigraph as its input and if it contains an Eularian circuit to return one. Otherwise, the program's behavior is undefined, ...
28
votes
2answers
978 views
