# Questions tagged [graph-theory]

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

191 questions
Filter by
Sorted by
Tagged with
847 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 ...
406 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 ...
191 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 ...
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 ...
644 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 ...
909 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. ...
542 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 ...
700 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 ...
221 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", ...
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 ...
390 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 ...
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 ...
504 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 ...
198 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 ...
279 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 ...
146 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 ...
408 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 ...
381 views

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 ...
290 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 ...
401 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 ...
954 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 ...
402 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 ...
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 ...
662 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, ...
667 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 ...
584 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, ...
807 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 ...
516 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, <...
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 ...
2k views

220 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 ...
519 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 ...
95 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