Questions tagged [graph-theory]

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

Filter by
Sorted by
Tagged with
19 votes
12 answers
901 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. ...
user avatar
  • 1,581
21 votes
1 answer
529 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 ...
user avatar
  • 3,605
13 votes
8 answers
674 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 ...
user avatar
  • 32.7k
8 votes
4 answers
219 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", ...
user avatar
  • 84.5k
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 ...
user avatar
  • 18.3k
9 votes
7 answers
386 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 ...
user avatar
  • 18.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 ...
user avatar
  • 62.1k
13 votes
2 answers
500 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 ...
user avatar
  • 62.1k
10 votes
4 answers
197 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 ...
user avatar
  • 62.1k
12 votes
2 answers
274 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 ...
user avatar
  • 40.1k
10 votes
0 answers
134 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 ...
user avatar
  • 62.1k
13 votes
9 answers
405 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 ...
user avatar
  • 311
8 votes
3 answers
378 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 ...
user avatar
8 votes
7 answers
289 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 ...
user avatar
  • 1,131
20 votes
1 answer
388 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 ...
user avatar
  • 62.1k
18 votes
5 answers
953 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 ...
user avatar
  • 8,097
11 votes
3 answers
399 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 ...
user avatar
  • 62.1k
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 ...
user avatar
  • 451
7 votes
8 answers
659 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, ...
user avatar
  • 40.1k
2 votes
0 answers
593 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 ...
user avatar
  • 29
15 votes
4 answers
582 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, ...
user avatar
10 votes
11 answers
802 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 ...
user avatar
  • 62.1k
12 votes
1 answer
494 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, <...
user avatar
  • 1,979
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 ...
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 \$ \...
user avatar
  • 16.9k
5 votes
0 answers
321 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 ...
user avatar
  • 8,126
5 votes
1 answer
249 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 ...
user avatar
11 votes
2 answers
407 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\$ ...
user avatar
  • 8,097
1 vote
0 answers
121 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 ...
user avatar
19 votes
3 answers
1k 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 ...
user avatar
  • 13.8k
23 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 ...
user avatar
  • 13.8k
13 votes
1 answer
400 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\$ ...
user avatar
  • 615
16 votes
10 answers
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 ...
user avatar
  • 62.1k
16 votes
2 answers
451 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 ...
user avatar
17 votes
2 answers
561 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 ...
user avatar
26 votes
3 answers
791 views

Can this village have a wedding?

The quaint hamlet of Кодгольф in the Russian far east has a problem: their population is low (below 66), and no new people have arrived for years. Moreover, after centuries of near-isolation, just ...
user avatar
15 votes
11 answers
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 ...
user avatar
  • 62.1k
8 votes
3 answers
246 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 ...
user avatar
  • 8,097
19 votes
1 answer
913 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: ...
user avatar
20 votes
1 answer
366 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. ...
user avatar
  • 5,535
9 votes
2 answers
219 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 ...
user avatar
  • 40.1k
-1 votes
1 answer
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 ...
user avatar
  • 253
2 votes
0 answers
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). ...
user avatar
1 vote
3 answers
252 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 ...
user avatar
  • 784
22 votes
7 answers
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 ...
user avatar
  • 35.8k
12 votes
4 answers
327 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 ...
user avatar
  • 9,791
13 votes
3 answers
402 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 ...
user avatar
  • 8,097
9 votes
3 answers
463 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 ...
user avatar
22 votes
23 answers
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 ...
user avatar
  • 16.3k
9 votes
0 answers
120 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 ...
user avatar
  • 42.9k