Questions tagged [graph-theory]

For challenges regarding graphs, mathematical structures used to model relations between objects.

Filter by
Sorted by
Tagged with
19 votes
13 answers
1k 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 ...
SanguineL's user avatar
  • 471
14 votes
5 answers
814 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 ...
Simd's user avatar
  • 1,812
29 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 ...
mousetail's user avatar
  • 11.8k
3 votes
1 answer
211 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 ...
Parcly Taxel's user avatar
  • 3,707
5 votes
3 answers
276 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 ...
user avatar
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 ...
lyxal's user avatar
  • 32.6k
15 votes
5 answers
942 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 ...
Karl's user avatar
  • 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 ...
Bjop's user avatar
  • 425
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. ...
alephalpha's user avatar
  • 46.5k
23 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 ...
Bjop's user avatar
  • 425
7 votes
4 answers
554 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 ...
user1502040's user avatar
  • 3,599
13 votes
1 answer
204 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 ...
Wheat Wizard's user avatar
  • 96.5k
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 ...
Wheat Wizard's user avatar
  • 96.5k
11 votes
14 answers
699 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 ...
Wheat Wizard's user avatar
  • 96.5k
20 votes
12 answers
972 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. ...
zoomlogo's user avatar
  • 1,645
22 votes
1 answer
711 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 ...
math scat's user avatar
  • 8,467
12 votes
9 answers
825 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 ...
alephalpha's user avatar
  • 46.5k
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 ...
caird coinheringaahin g's user avatar
8 votes
4 answers
237 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", ...
Wheat Wizard's user avatar
  • 96.5k
31 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 ...
pxeger's user avatar
  • 23.3k
9 votes
7 answers
399 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 ...
pxeger's user avatar
  • 23.3k
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 ...
Bubbler's user avatar
  • 73.8k
13 votes
2 answers
528 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 ...
Bubbler's user avatar
  • 73.8k
10 votes
4 answers
201 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 ...
Bubbler's user avatar
  • 73.8k
12 votes
2 answers
306 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 ...
hyper-neutrino's user avatar
  • 41.3k
11 votes
0 answers
218 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 ...
Bubbler's user avatar
  • 73.8k
14 votes
9 answers
429 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 ...
Hack5's user avatar
  • 341
8 votes
3 answers
384 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 ...
Zizy Archer's user avatar
8 votes
7 answers
292 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 ...
user197974's user avatar
  • 1,161
21 votes
1 answer
428 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 ...
Bubbler's user avatar
  • 73.8k
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 ...
Peter Kagey's user avatar
  • 8,659
12 votes
3 answers
438 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 ...
Bubbler's user avatar
  • 73.8k
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 ...
Keba's user avatar
  • 451
7 votes
8 answers
684 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, ...
hyper-neutrino's user avatar
  • 41.3k
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 ...
mthpnk's user avatar
  • 29
15 votes
4 answers
605 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, ...
caird coinheringaahin g's user avatar
10 votes
11 answers
827 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 ...
Bubbler's user avatar
  • 73.8k
12 votes
1 answer
705 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, <...
golf69's user avatar
  • 2,049
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 ...
Jubayer Abdullah Joy's user avatar
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 \$ \...
dingledooper's user avatar
  • 22.3k
5 votes
0 answers
406 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 ...
the default.'s user avatar
  • 8,415
5 votes
1 answer
300 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 ...
subdermatoglyphic's user avatar
11 votes
2 answers
426 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\$ ...
Peter Kagey's user avatar
  • 8,659
1 vote
0 answers
151 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 ...
Viswa's user avatar
  • 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 ...
RGS's user avatar
  • 14k
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 ...
RGS's user avatar
  • 14k
13 votes
1 answer
418 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\$ ...
kyrill's user avatar
  • 615
15 votes
10 answers
2k 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 ...
Bubbler's user avatar
  • 73.8k
16 votes
2 answers
630 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 ...
AlienAtSystem's user avatar
17 votes
2 answers
578 views

Can this Scottish village have a wedding?

This is the exact same question I asked earlier, but without the annoying Cyrillic factor which many found superfluous. I hope this is a better puzzle! The quaint hamlet of North Codetown in the ...
KeizerHarm's user avatar
  • 1,171

1
2 3 4 5