Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-theory]

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

12
votes
10answers
946 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
249 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
642 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 ...
13
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 ...
15
votes
5answers
953 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): ...
15
votes
4answers
460 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 ...
15
votes
7answers
636 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), (x+2, y+1) in one step. Imagine an infinite chessboard with only a ...
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 ...
16
votes
14answers
587 views

Transitive Equality

The Challenge Your program should take 3 inputs: A positive integer which is the number of variables, A set of unordered pairs of nonnegative integers, where each pair represents an equality between ...
13
votes
7answers
347 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 ...
10
votes
5answers
382 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 ...
19
votes
13answers
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 ...
13
votes
3answers
1k views

Hexcellent Minesweeping

Hexcells is a game based off of Minesweeper played on hexagons. (Full disclosure: I have nothing to do with Hexcells. In fact I don't really like the game.) Most of Hexcells rules can be pretty ...
10
votes
2answers
423 views

Biggest square in a grid [closed]

Challenge Given a grid like this, ...
9
votes
1answer
354 views

Advent Challenge 2: The Present Vault Raid!

<< Prev Next >> Challenge Now that Santa has finally figured out how to get into his present vault, he realises that somehow the elves got in there before him and stole some of his presents! ...
13
votes
4answers
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. ...
8
votes
5answers
437 views

Demonstrate a lower bound for the Ramsey number R(4,4)

A special case of Ramsey's theorem says the following: whenever we color the edges of the complete graph on 18 vertices red and blue, there is a monochromatic clique of size 4. In language that ...
10
votes
3answers
313 views

What's assignable to what?

related What's assignable to what? In this challenge you will be given two types, A and B and determine if ...
6
votes
4answers
299 views

Who's Going? Can you help me?

If Abe goes, then Beth and Diana go. If Beth goes, then Catherine goes. If Catherine goes, then Diana goes. If Diana goes, then Ezra goes. Only three people go. Who goes? Challenge Given a list of ...
18
votes
7answers
945 views

Longest hypercube path

Challenge You are given two distinct bit strings of the same length. (For example, 000 and 111.) Your goal is to find a path ...
26
votes
8answers
2k views

Somewhere On The Tube …But On Which Lines?

The London Underground A.K.A. The Tube is the oldest underground railway in the world, it currently consists of eleven lines* servicing 267 named stations (strictly 269** stations since "Edgware Road" ...
22
votes
13answers
2k views

Do the NP: find the largest clique

Background At the time of writing this, the P vs NP problem is still unsolved, but you might have heard of Norbert Blum's new paper claiming proof that P != NP, which is already suspected to be ...
13
votes
0answers
405 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, ...
19
votes
8answers
663 views

Optimal path through a matrix

Given a matrix consisting of positive integers, output the path with the lowest sum when traversing from the upper left element to the bottom right. You may move vertically, horizontally and ...
7
votes
1answer
193 views

How related are two relatives?

The coefficient of relationship refers to how much DNA two persons have in common. A parent has 50% common DNA with their child (unless the parents are related), so to calculate it we have to find all ...
10
votes
2answers
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 ...
14
votes
3answers
627 views

Calculate Treewidth

The treewidth of an undirected graph is a very important concept in Graph Theory. Tons of graph algorithms have been invented which run fast if you have a decomposition of the graph with small ...
7
votes
4answers
902 views

Burning Bridges

Note: When I refer to a bridge, I mean it in the non-mathematical sense Introduction You are on a network of islands which are connected by wooden bridges and you want to see if you can burn every ...
7
votes
3answers
124 views

Rooting for Trees With the Right Nodes

Background A rooted tree is an acyclic graph such that there is exactly one path from one node, called the root, to each other node. A node v is called the parent ...
7
votes
8answers
846 views

Is the graph acyclic?

A Directed Acyclic Graph (DAG) is a type of graph that has no cycles in it. In other words, if there is a link from node A to node B, there exists no path from B to A (via any nodes). Challenge ...
7
votes
0answers
300 views

Don't break the bridges!

Introduction: You are a worker, who is in charge of managing a set of bridges, connecting a square grid of "nodes": ...
5
votes
1answer
204 views

Broken Path Detection

Challenge Given a plot with broken paths, return the plot with all paths connected in the minimum number of changes. Explanation This problem deals with graphs on the Cartesian plane. Every node ...
23
votes
1answer
669 views

Is it a Cactus?

In graph theory, a Cactus is a connected graph such that any distinct two simple cycles in the graph share at most one vertex. Here is a Cactus with 3 simple cycles outlined with dashed lines. The ...
9
votes
6answers
963 views

Given a Tree generate its Prüfer Code

In graph-theory a Prüfer code is a unique sequence of integers that denotes a specific tree. You can find the Prüfer code of a tree with the following algorithm taken from Wikipedia: Consider a ...
10
votes
2answers
271 views

The von Koch conjecture

You may know the mathematician von Koch by his famous snowflake. However he has more interesting computer science problems up his sleeves. Indeed, let's take a look at this conjecture: Given a tree ...
14
votes
7answers
458 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 ...
30
votes
2answers
737 views

Help Pac-Man count the Pac-Dots

On the advice of Ms. Pac-Man who's worried about him getting overweight, Pac-Man has decided to keep track of his daily Pac-Dot intake. Help him count the number of Pac-Dots on a given path in the ...
30
votes
8answers
5k views

Should we be friends?

Note this is a question primarily focusing on data-structures Introduction Bacefook wants people to be friendlier! As such, they are implementing a new system to suggest friends! Your task is to ...
18
votes
2answers
246 views

Island Golf #2: The Eccentric Hermits

This is the second in a series of Island Golf challenges. Previous challenge Two hermits have arrived on a desert island. Since they came seeking solitude, they wish to live as far away from each ...
20
votes
9answers
1k views

Enumerate binary trees

Binary trees A binary tree is a tree with nodes of three types: terminal nodes, which have no children unary nodes, which have one child each binary nodes, which have two children each We can ...
13
votes
3answers
575 views

Grids can be curvy. How long is yours?

Consider depicting a simple, open, two-dimensional curve on a W wide by H high grid of text where X represents part of the curve and ...
22
votes
10answers
2k views

Two-Coloring Overlapping Circles

Write a program or function that takes in the following input in a reasonable format of your choice: Two positive integers W and H that define the width and height of the image you'll be generating. ...
9
votes
2answers
281 views

Is my Graph Graceful?

A Graceful Graph is a type of Simple Graph. Graceful graphs are special because there is a way to label all their nodes with positive integers so that when the edges are also labeled with the ...
15
votes
6answers
548 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 ...
13
votes
4answers
376 views

Negative Space Graphs

Task You will be given a positive integer and you must output a "self-complementary graph" with that many nodes. If you don't know what a self-complementary graph is the wikipedia article wont help ...
19
votes
7answers
581 views

Longest Cycle in a Graph

Given a directed graph, output the longest cycle. Rules Any reasonable input format is allowed (e.g. list of edges, connectivity matrix). The labels are not important, so you may impose any ...
26
votes
3answers
779 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 ...
-3
votes
1answer
195 views

Find an Eulerian Circuit

Challenge You have been assigned a task to write a program which takes a multigraph as its input and if it contains an Eularian circuit to return one. Otherwise, the program's behavior is undefined, ...
28
votes
2answers
978 views

2D Maze Minus 1D

This challenge is about converting 2D mazes into 1D mazes. Overview ...