Questions tagged [graph-theory]
For challenges regarding graphs, mathematical structures used to model relations between objects.
176
questions
8
votes
4answers
177 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 ...
11
votes
2answers
243 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 ...
8
votes
0answers
104 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 ...
12
votes
9answers
363 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 ...
8
votes
3answers
369 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 ...
8
votes
7answers
279 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 ...
20
votes
1answer
365 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 ...
18
votes
5answers
940 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 ...
11
votes
3answers
374 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 ...
24
votes
7answers
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 ...
7
votes
8answers
630 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, ...
2
votes
0answers
273 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 ...
15
votes
4answers
563 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, ...
9
votes
11answers
785 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 ...
12
votes
1answer
441 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, <...
20
votes
14answers
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
7answers
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 \$ \...
4
votes
0answers
267 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 ...
5
votes
1answer
247 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
2answers
393 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\$ ...
1
vote
0answers
112 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 ...
19
votes
3answers
885 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 ...
18
votes
27answers
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 ...
13
votes
1answer
389 views
Gossipping ladies
Problem description
Vertices \$V\$ of directed graph \$G=(V,E)\$ represent gossipping ladies; edge \$(u,v) \in E\$ signifies that lady \$u\$ knows of lady \$v\$ (which does not imply that lady \$v\$ ...
13
votes
10answers
1k views
Random spanning tree of a rectangular grid
Significantly harder version of Spanning tree of a rectangular grid.
Background
A spanning tree (Wikipedia) of an undirected graph is a subgraph that is a tree which includes all of the vertices of ...
16
votes
2answers
413 views
Calculate Coefficient of Inbreeding
Your task is, given a family tree, to calculate the Coefficient of Inbreeding for a given person in it.
Definition
The Coefficient of Inbreeding is equal to the Coefficient of Relationship of the ...
14
votes
11answers
1k views
Spanning tree of a rectangular grid
Background
A spanning tree (Wikipedia) of an undirected graph is a subgraph that is a tree which includes all of the vertices of the original graph. The following is an example of a spanning tree of ...
8
votes
3answers
236 views
Multigraphs with a given degree sequence
This challenge will give you an input of a degree sequence in the form of a partition of an even number. Your goal will be to write a program that will output the number of loop-free labeled ...
19
votes
1answer
897 views
Gerrymander North Carolina
The challenge
How well can you gerrymander North Carolina into 13 voting districts?
In this challenge, you use the following files to draw different maps for Republicans and Democrats.
File 1: ...
20
votes
1answer
355 views
Complete the grid-filling meander
A grid-filling meander is a closed path that visits every cell of a square \$N \times N\$ grid at least once, never crossing any edge between adjacent cells more than once and never crossing itself. ...
9
votes
2answers
213 views
Reroute the Path
Given a grid of directions and a start and end position, determine the minimum number of substitutions in the direction grid that needs to be made to complete the path between the two points. The grid ...
-2
votes
1answer
510 views
Pandemic Outbreak Calculator [closed]
In the board game Pandemic, an outbreak occurs when a city contains more than 3 disease cubes. When the outbreak occurs, any disease cubes in the city in excess of 3 are removed, and each city ...
2
votes
0answers
94 views
Finding row wise sum of transpose of hv-convex binary matrix [closed]
I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m).
...
1
vote
3answers
251 views
Havel-to-da-Hakimi [duplicate]
It was a dark and stormy night. Detective Havel and Detective Hakimi arrived at the scene of the crime.
Other than the detectives, there were 10 people present. They asked the first person, "out of ...
22
votes
7answers
2k views
Surface of the 3x3x3 cube as a graph
Your task is to generate a graph with 54 vertices, each corresponds to a facet on a Rubik's cube. There is an edge between two vertices iff the corresponding facets share a side.
Rules
You may ...
12
votes
4answers
322 views
Ambassadors and Translators
Two ambassadors at a UN conference want to speak to each other, but unfortunately each one only speaks one language- and they're not the same language. Fortunately, they have access to several ...
13
votes
3answers
399 views
Counting the number of restricted forests on the Möbius ladder of length n
OEIS sequence A020872 counts the number of restricted forests on the Möbius ladder Mn.
The Challenge
The challenge is to write a program that takes an integer as an input ...
9
votes
3answers
349 views
Minimum-cost flow problem
A flow network is a directed graph G = (V, E) with a source vertex s ϵ V and a sink vertex ...
22
votes
23answers
3k views
Pointer jumping
Suppose we have an array \$\texttt{ps}\$ of length \$n\$ with pointers pointing to some location in the array: The process of "pointer jumping" will set every pointer to the location the pointer it ...
9
votes
0answers
119 views
Order of Elements of the Rubik's Cube [duplicate]
Introduction
All the possible moves and their combinations of a Rubik's Cube form a group. A group in general is a set with some binary operation defined on it. It must contain a neutral element with ...
7
votes
5answers
203 views
Find equally-weighted complete graphs
Graph theory is used to study the relations between objects. A graph is composed of vertices and edges in a diagram such as this:
...
15
votes
11answers
1k 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
386 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
842 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 ...
14
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 ...
16
votes
5answers
1k 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):
...
17
votes
4answers
607 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 ...
17
votes
7answers
855 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)\$ or \$(x+2, y+1)\$ in one step. Imagine ...
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 ...
