Christmas gift giving

Question

Problem:

You have a family of $N$ members, which is much too large to provide quality gifts to each individual from each individual. Therefore, your family decides it is more appropriate to buy quality gifts for just a few members from each individual. So each individual $i$ gives 1 present to $m$ number of people from the family. However, you want this to be 'fair', so each person $i$ must receive $m$ gifts.

I'm not entirely certain what class of problem this is, but I'm fairly sure it can be tackled with graph theory.

Here is a small example with $N=9$,$m = 3$, although it doesn't work out exactly right, as $Person G$ is left with just 2 presents (if this is the receiving graph, or buying 2 gifts if this is the purchasing graph)

I would like to construct two of these graphs, one for purchasing and one for receiving, such that no one knows who gets presents from who.

Any suggestions as to how to properly model this, and any decent 'work around' for the problem posed by the instances like $Person G$ (i.e. incomplete regular graphs)?

Answer:

I figured this out shortly after posting. It's a fairly simple problem to solve if you just arrange the nodes in a circle and draw arrows in a sequential manner clockwise:

Code:

import networkx as nx
from networkx.drawing.nx_agraph import graphviz_layout
import pylab as plt

family = range(0,10)
N = len(family)

# number of gifts for each person
m = 3

gifts = {person:[family[ix - gift_ix] for gift_ix in range(1, m+1)] for ix, person in enumerate(family)}
gift_tuple = [(giver, receiver) for giver, receiver_list in gifts.items() for receiver in receiver_list]
G = nx.DiGraph()
G.add_nodes_from(family)
G.add_edges_from(gift_tuple)

nx.draw(G, pos = graphviz_layout(G), node_size = 2000, node_color = 'lightgray',
        prog='dot', with_labels = True)

Answer 1

What you want is a directed graph on $N$ vertices where every vertex has indegree $m$ and outdegree $m$, where $m$ is the number of presents each person receives. It is easy to construct such a graph.

This is one such way. Assign each of the $N$ people in your family a unique number in $\{0,1,\ldots, N-1\}$. Then person $j$ gives gifts to person $j+1$, person $j+2$, $\ldots$ person $j+m$ [all arithmetic done mod $N$], and receives from person $j-m$, $j-m+1$,$\ldots$, person $j-1$.