Questions tagged [graph-theory]
For challenges regarding graphs, mathematical structures used to model relations between objects.
203
questions
5
votes
5
answers
301
views
Calculating Graph Powers
Calculating Graph Powers
(very similar to my other question asked here)
According to Wikipedia, "the \$k\$th power \$G^k\$ of an undirected graph \$G\$ is another graph that has the same set of ...
- 738
6
votes
2
answers
217
views
Pareto-optimal shortest paths
Given a directed graph on the nodes 0, 1, ..n, where each edge has two non-negative integer costs, return the set of all possible Pareto Optimal path costs between ...
- 3,839
21
votes
13
answers
2k
views
Calculating Transitive Closure
First attempt at a question.
Calculating Transitive Closure
According to Wikipedia, "the transitive closure \$R^*\$ of a homogeneous binary relation \$R\$ on a set \$X\$ is the smallest ...
- 738
15
votes
5
answers
845
views
Compute the chromatic number of special graphs
This challenge is about computing the chromatic number of special types of graphs.
Input
The input will consist of two integers.
A positive integer \$n > 1\$.
A distance \$d < n\$.
Task
The ...
- 3,114
30
votes
13
answers
3k
views
Is it a valid chemical?
Non-metals typically* have a fixed number of covalent bonds in every chemical they are part of. Given the number of bonds every element requires, output whether it's possible to construct a single ...
- 12.8k
4
votes
1
answer
232
views
Triangularly embed a graph on a surface
This challenge arises from a claim made in a MathOverflow answer and a paper linked in that answer which seems to back up the claim:
Searching for triangular embeddings is much quicker than ...
- 3,845
5
votes
3
answers
360
views
Minimum Cut finder
Write a program that takes an undirected graph and finds the minimum cut, i.e., the set of edges that, if removed, would disconnect the graph into two or more connected components. The program should ...
user116868
9
votes
14
answers
1k
views
Simplify a Cycle
Alternatively: That one challenge I forgot I had in the sandbox and is about stuff from Discrete Mathematics I learned like 5-6 months ago and kinda don't remember
Given a path of vertices that form a ...
- 33.8k
15
votes
5
answers
952
views
Detect round trips on a dodecahedron
An ant starts on an edge of a dodecahedron, facing parallel to it. At each step, it walks forward to the next vertex and turns either left or right to continue onto one of the other two edges that ...
- 621
9
votes
3
answers
1k
views
The smallest number of steps for a chess piece to reach a position
I have previously posted a challenge, smallest number of steps for a knight in chess.
Now I would like to go a step further by adding the possibility to choose your piece.
If you place a piece on any ...
- 435
19
votes
14
answers
3k
views
Is this graph a tree?
Given an undirected graph, find out if it is a tree.
A tree is an undirected graph in which there is exactly one path between any two vertices. In other word, the graph is both acyclic and connected.
...
- 48.7k
24
votes
15
answers
3k
views
smallest number of steps for a knight in chess
If you place a knight on any square of a chessboard, what is the smallest amount of steps to reach every position?
Rules
It is an 8 by 8 board.
The knight starts at an arbitrary position, taken as ...
- 435
7
votes
4
answers
567
views
Train Route Planning
We can model a rail network as a directed graph, where each node is a train station and each edge is a train connecting two train stations. We'll assume that each train travels between its ...
- 3,839
13
votes
1
answer
206
views
Is this a strange pond?
In this challenge we considered a frog hopping around a lily pond. To recap the lily pond was represented as a finite list of positive integers. The frog can only jump forward or backwards by a ...
- 99.1k
30
votes
5
answers
5k
views
Can the 🐸 visit all the 🪷?
In this challenge you will be simulating a frog jumping from lily-pad to lily-pad in a pond. A frog's jump distance is uniquely determined by the size of the lily pad it jumps from. So for example ...
- 99.1k