Questions tagged [graph-theory]
For challenges regarding graphs, mathematical structures used to model relations between objects.
167
questions
7
votes
3answers
371 views
Edge Elimination Number
From Erich Friedman's Math Magic, (problem #2 on that page) your challenge is to find the edge elimination number of a connected graph.
A single edge elimination is the removal of an edge from a graph,...
caird coinheringaahing
22.1k5 gold badges51 silver badges157 bronze badges
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 ...
14
votes
9answers
610 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 ...
7
votes
8answers
576 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, ...
22
votes
3answers
1k views
Map of Islands (and a river)
Introduction
For many centuries, there has been a certain river that has never been mapped. The Guild of Cartographers want to produce a map of the river, however, they have never managed to succeed -...
8
votes
14answers
5k views
Find all reachable nodes in a graph
You are given a directed graph in an adjacency dictionary format. This can be whatever format is most natural for your language. For instance, in python, this would be a dictionary with keys of nodes ...
22
votes
10answers
3k views
Can the maze be solved?
Task
Print 0 if an n*m maze cannot be solved
Print 1 if an n*m maze can be solved (in 1 or more ways)
(so I'm not asking for ...
2
votes
0answers
170 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 ...
14
votes
4answers
545 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
777 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 ...
50
votes
3answers
3k views
Help, I'm trapped in a Sierpinski triangle!
Drawing the Sierpinski triangle has been done to death. There's other interesting things we can do with it though. If we squint hard enough at the triangle, we can view upside-down triangles as nodes ...
12
votes
1answer
378 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, <...
22
votes
3answers
646 views
Follow incomplete directions
A friend of yours has given you directions to the best restaurant in town. It's a series of left and right turns. Unfortunately, they forgot to mention for how long you need to go straight ahead ...
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 ...
29
votes
4answers
924 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 ...
13
votes
1answer
382 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\$ ...
19
votes
7answers
1k 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
182 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 ...
3
votes
0answers
222 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 ...
13
votes
5answers
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.
...
19
votes
1answer
885 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: ...
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 ...
11
votes
2answers
380 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\$ ...
13
votes
10answers
960 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 ...
19
votes
3answers
653 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 ...
1
vote
0answers
100 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 ...
15
votes
26answers
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 ...
20
votes
14answers
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 ...
16
votes
2answers
377 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 ...
23
votes
1answer
809 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, ...
13
votes
7answers
432 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 ...
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
223 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 ...
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):
...
20
votes
1answer
346 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. ...
12
votes
5answers
533 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 ...
6
votes
1answer
494 views
Hamilton is coming to town
It's almost Christmas, so Santa has to plan his route. You're helping him, for reasons unknown.
Santa needs help planning the route and wants you to give him a solution, but since you're all ...
9
votes
2answers
208 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
505 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
91 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).
...
17
votes
12answers
766 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 ...
1
vote
3answers
248 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 ...
12
votes
4answers
318 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 ...
19
votes
2answers
3k views
Mastermind strategy
I could only find code-golf challenges for Mastermind, so here's a code-challenge version that I would have liked to take on myself.
An optimal strategy for the normal Mastermind game, MM(4,6), was ...
14
votes
3answers
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 ...
13
votes
3answers
392 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 ...
15
votes
16answers
5k views
Determine if a relation is transitive
Challenge description
Let's start with some definitions:
a relation is a set of ordered pairs of elements (in this challenge, we'll be using integers)
For instance, ...
51
votes
18answers
4k views
Can my 4-note music box play that song?
I have a crank-operated music box that can play a series of four notes. When I turn the crank, it plucks one of four strings, depending on the position of the crank and the direction of the turn. When ...
21
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
3answers
272 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 ...
