1
$\begingroup$

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)

enter image description here

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: enter image description here enter image description here

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)
$\endgroup$
5
  • 1
    $\begingroup$ Two graphs? It rather looks like you want one graph, but a directed one. $\endgroup$ Nov 21, 2018 at 18:14
  • 1
    $\begingroup$ If ordinary Christmas gifts in your culture are not labeled with the name of the giver (which sounds strange to me, but it's a large world) you can try searching the site for "secret santa" algorithms and see if some of them will scale up to $m>1$. $\endgroup$ Nov 21, 2018 at 18:17
  • $\begingroup$ Thank you for the secret santa suggestion. That's what we are doing. I suppose it could work in one directed graph, but the implementation would be harder to understand. For the example given, you would have to make each node have 6 edges, with 3 outgoing and 3 incoming. I figured it would be simpler to implement just making it 2 separate ?*somewhat*-regular graphs? (i.e. a graph with as close to 3 edges per node as possible) $\endgroup$
    – chase
    Nov 21, 2018 at 18:18
  • $\begingroup$ I don't see how you can model what you say you're modeling with two separate undirected graphs. For example, your illustration shows one edge between C and D. Does that mean that D gives a gift to C or that C gives a gift to D? Or both? In either case, each time a gift changes hands, there will be someone giving AND someone receiving it, and if the gift is represented by an edge in the graph, that edge is necessarily going to encode both that someone is a giver and that someone is a receiver. $\endgroup$ Nov 21, 2018 at 18:24
  • $\begingroup$ Oh wow - I don't know what happened to my brain there. You're obviously absolutely right and that is an embarrassingly large whoosh moment for me $\endgroup$
    – chase
    Nov 21, 2018 at 18:27

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .