# Questions tagged [graph-theory]

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

155 questions
Filter by
Sorted by
Tagged with
57 views

### Find the number of edge in a graph [closed]

In graph theory, you can describe a graph using a letter and its number of vertices. For example, the complete graph with 5 vertices is denoted by K5 There are many identifiers for many family of ...
2k 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 ...
242 views

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$ ...
685 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 ...
360 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 ...
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 ...
208 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 ...
449 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: ...
316 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. ...
195 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 ...
228 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 ...
88 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). ...
235 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 ...
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 ...
299 views

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 ...
378 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 ...
232 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 ...
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 ...
116 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 ...
197 views

### Find equally-weighted complete graphs

Graph theory is used to study the relations between objects. A graph is composed of vertices and edges in a diagram such as this: ...
1k 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 ...
332 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 ...
716 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 ...
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 ...
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): ...
582 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 ...
786 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 ...
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 ...
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 ...
716 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 ...
415 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 ...
498 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 ...
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 ...
2k 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 ...
553 views

### Biggest square in a grid [closed]

Challenge Given a grid like this, ...
374 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! ...
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. ...
460 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 ...
320 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 ...
306 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 ...
1k 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 ...
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" ...
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 ...
790 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, ...
764 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 ...
201 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 ...
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 ...
772 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 ...