All Questions
Tagged with graphs or graph-theory
205 questions
8
votes
5
answers
904
views
Pólya trees counted efficiently
The number of unlabeled rooted trees with n nodes is a fundamental sequence in graph theory and in discrete mathematics in general.
Some authors call these trees 'Polya trees'. The number of these ...
- 1,502
18
votes
5
answers
1k
views
Ways to paint a backbone on a tree
Say I have some unlabelled tree graph:
I'll define a "backbone" as a path on a graph that can't be extended - both its ends are at terminal vertices. There are three ways to overlay a ...
- 44.2k
5
votes
5
answers
309
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
222
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,864
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
16
votes
5
answers
862
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,275
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 ...
- 13.5k
5
votes
1
answer
369
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,945
5
votes
3
answers
378
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 ...
- 34.3k
15
votes
5
answers
961
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 ...
- 841
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.
...
- 50k
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
573
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,864
13
votes
1
answer
210
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 ...
- 100k
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 ...
- 100k
11
votes
14
answers
728
views
Increasing permutation trees
For this challenge a "binary tree" is a rooted tree where each node has 0 children (leaf) or 2. The children of a node are unordered, meaning that while you might draw the tree with left ...
- 100k
20
votes
12
answers
985
views
Convert between graph representations
What?
Let's say I have this graph:
1
\
\
2 3
\ /
\ /
4
I can represent it in 2 ways:
A list of connected vertices. ...
- 1,665
22
votes
1
answer
733
views
Can you draw this in one stroke?
Related | Related
Given an ASCII art with |, _, and , check if you can draw the art in one ...
- 9,468
12
votes
9
answers
951
views
Chromatic polynomial of a graph
Given a undirected graph \$G\$ and a integer \$k\$, how many \$k\$-coloring does the graph have?
Here by a \$k\$-coloring, we mean assigning one of the \$k\$ colors to each vertex of the graph, such ...
- 50k
18
votes
20
answers
1k
views
Generate a regular graph
Inspired by this Mathematica.SE post
Given two positive integers \$n, k\$ with \$n > k \ge 1\$, output a binary \$n\times n\$ matrix such that every row and column contains exactly \$k\$ 1s, and ...
- 50.3k
8
votes
4
answers
268
views
Your trees need to be rerooted
In graph theory a tree is just any graph with no cycles. But in computer science we often use rooted trees. Rooted trees are like trees except they have one specific node as the "root", ...
- 100k
32
votes
10
answers
5k
views
Who Is Kevin Bacon?
You may know the game The Six Degrees of Kevin Bacon, based on the conjecture that every actor in Hollywood can be connected to Kevin Bacon by no more than 6 "co-star" relations, so Kevin ...
- 24.6k
9
votes
7
answers
404
views
AoCG2021 Day 19: To Hire or To Fire
Part of Advent of Code Golf 2021 event. See the linked meta post for details.
The story continues from AoC2018 Day 7, Part 2.
Why I'm pxeger, not Bubbler
As soon as you and a few Elves successfully ...
- 24.6k
12
votes
9
answers
1k
views
AoCG2021 Day 13: Defrag in action!
Part of Advent of Code Golf 2021 event. See the linked meta post for details.
The story continues from AoC2017 Day 14.
To recap: The disk is a rectangular grid with \$r\$ rows and \$c\$ columns. Each ...
- 78.4k
14
votes
3
answers
583
views
Is this an interval graph?
Background
An interval graph (Wikipedia, MathWorld, GraphClasses) is an undirected graph derived from a set of intervals on a line. Each vertex represents an interval, and an edge is present between ...
- 78.4k
10
votes
4
answers
208
views
Hamiltonian levencycle of 1-dup permutations
The word "levencycle" is inspired by cyclic levenquine challenge.
Definitions
A 1-dup permutation of order \$n\$ is some permutation of \$1, \cdots, n\$ plus one duplicate number in the ...
- 78.4k
12
votes
2
answers
318
views
Classify a graph
Challenge
Given a graph (a structure consisting of nodes and vertices), classify it according to a few categories.
Specifically, you will be given an unweighted directed graph, which is a set of nodes ...
- 42.6k
12
votes
0
answers
256
views
NP-complete reduction: (grid-)Hamiltonian circuit
Background
Hamiltonian circuit problem is a decision problem which asks whether a given graph has a Hamiltonian circuit, i.e. a cycle that visits every vertex exactly once. This problem is one of the ...
- 78.4k
14
votes
9
answers
437
views
Taking the long route
Challenge
Your goal is to find the furthest point on a graph (from a provided start node). Your code doesn't need to handle cycles in the graph properly, but it might pose a fun challenge. For this ...
- 341
8
votes
3
answers
389
views
Radio station hopping
Introduction
You are listening to a car radio. You are pressing seek up/down, moving you to the next frequency some radio station broadcasts on, to avoid all this pointless music and listen to all the ...
- 255
8
votes
7
answers
299
views
Find the Best Set of Adapters
I'm trying to plug this really old phone into my computer but the phone seems to use a very obscure plug. Luckily I have some adapters. Unfortunately, I can't figure out which of them to use to ...
- 1,161
22
votes
1
answer
439
views
Is this Game of Go configuration fully alive?
Background
This challenge is about the Game of Go. Here are some rules and terminology relevant to this challenge:
Game of Go is a two-player game, played over a square board of size 19x19.
One of ...
- 78.4k
18
votes
5
answers
1k
views
Count all binary relations
A binary relation on a set \$X\$ is simply a subset \$S \subseteq X \times X\$; in other words, a relation is a collection of pairs \$(x,y)\$ such that both \$x\$ and \$y\$ are in \$X\$. The number of ...
- 9,001
12
votes
3
answers
456
views
A graph and its seven closures
Background
A little while ago, someone posted an interesting puzzle on Math.SE:
What is the smallest digraph (directed graph) G where the following eight graphs are all distinct:
G, the original ...
- 78.4k
24
votes
7
answers
2k
views
Are these states connected?
With the US election going on right now, I noticed that there is one (completely meaningless, but still) thing which Trump can still achieve and which is out of reach for Biden: Having the won states ...
- 451
7
votes
8
answers
697
views
Count Euler's Tours
Leonhard Euler wants to visit a few friends who live in houses 2, 3, ..., N (he lives in house 1). However, because of how his city is laid out, none of the paths between any houses form a loop (so, ...
- 42.6k
2
votes
0
answers
1k
views
Solve the Trolley Problem with Multitrack Drifting [closed]
Introduction
Programmers have already solved the trolley problem (a classical problem in philosophy). In the usual trolley problem, we have a directed graph and each edge is weighted by the number of ...
- 29
15
votes
4
answers
627
views
Find the maximum flow
Given a directed network, with a single source and a single sink, it is possible to find the maximum flow through this network, from source to sink. For example, take the below network, \$G\$:
Here, ...
- 50.3k
10
votes
11
answers
849
views
Counting King's Hamiltonian Paths through 3-by-N grid
Background
A Hamiltonian path is a path on a graph that steps through its vertices exactly once. On a grid, this means stepping through every cell exactly once.
On a square grid, a Chess King can move ...
- 78.4k
13
votes
1
answer
919
views
Scoring Quantum Tic-Tac-Toe
In the description of this challenge, the following board will be used as a reference for positions:
ABC
DEF
GHI
For instance, in a game of ordinary tic-tac-toe, <...
- 2,059
20
votes
14
answers
2k
views
Get to the Zone!
You are playing a famous game called \$1\text{D Array BattleGround}\$. In the game, the player can be stationed in any position from \$0\$ to \$10^5\$.
You are a Paratrooper in the game and have the ...
20
votes
7
answers
2k
views
Break The Chain
You are given an \$ 25 \times 25 \$ square lattice graph. You are to remove certain nodes from the graph as to minimize your score, based on the following scoring system:
Your score will be the \$ \...
- 22.9k
5
votes
0
answers
458
views
Hamming distance traveling salesman problem
The Hamming distance between two strings is the number of positions they differ at.
You are given a set of binary strings. The task is to find the length of the shortest route that visits all of them ...
- 8,445
5
votes
1
answer
312
views
How annoying is my Euler diagram?
Challenge
Premise
Euler diagrams consist of simple closed shapes in a 2-D plane that each depict a set or category. How or whether these shapes overlap demonstrates the relationships between the ...
11
votes
3
answers
462
views
Spanning paths in a tournament on n nodes
The goal of this challenge is to extend the On-Line Encyclopedia of Integer Sequences (OEIS) sequence A038375.
Maximal number of spanning paths in tournament on n nodes.
A tournament on \$n\$ ...
- 9,001
1
vote
0
answers
169
views
Minimum Hop Count in Directed Graph based on Conditional Statement [closed]
A directed graph G is given with Vertices V and Edges E, representing train stations and unidirectional train routes respectively.
Trains of different train numbers move in between pairs of Vertices ...
- 173
19
votes
3
answers
2k
views
All roads lead to Rome
"All roads lead to Rome" is a saying that essentially means there are plenty of different ways of achieving an objective.
Task
Your task is to write a program that finds a set of link connections ...
- 14.1k
24
votes
32
answers
3k
views
Drawing one-liner
CodeDrawing one-liner
Teaser
Behold this formidable drawing:
Can you draw this in a single stroke? Give it a try.
Can you do this one, now:
Give it a try.
How it works
These "make this drawing ...
- 14.1k