Słownik

Wybierz jedno ze słów kluczowych po lewej stronie…

Graphs and NetworksHandshakes and Dating

Czas czytania: ~15 min

You have been invited to a wonderful birthday party with your friends. Including yourself and the host, there are ${hnd} people present.

In the evening, as the guests get ready to leave, everyone shakes hands with everyone else. How many handshakes are there in total?

We can represent the handshakes using a graph: every person is , and every handshake is .

Now it is easy to count the number of edges in the graph. We find that with ${hnd} people, there are ${hnd*(hnd-1)/2} handshakes.

Rather than counting all the edges in large graphs, we could also try to find a simple formula that tells us the result for any number of guests.

Each of the ${n} people at the party shakes hands with ${n-1} others. That makes ${n} × ${n-1} = ${n×(n-1)} handshakes in total. For n people, the number of handshakes would be .

Unfortunately this answer is not quite right. Notice how the first two entries on the top row are actually the same, just flipped around.

In fact, we have counted every handshake , once for each of the two people involved. This means that the correct number of handshakes for ${n} guests is ${n}×${n-1}2=${n*(n-1)/2}.

The handshake graphs are special because every vertex is connected to every other vertex. Graphs with this property are called complete graphs. The complete graph with 4 vertices is often abbreviated as K4, the complete graph with 5 vertices is known as K5, and so on.

We have just shown that a complete graph with n vertices, Kn, has n×n12 edges.

On a different day, you are invited to a speed dating event for ${m} boys and ${f} girls. There are many small tables and every boy spends 5 minutes with each of the girls. How many individual “dates” are there in total?

In this case, the corresponding graph consists of two separate sets of vertices. Every vertex is connected to all the vertices in set, but none of the vertices in set. Graphs which have this layout are called bipartite graphs.

The bipartite graph with two sets of size x and y is often written as Kx,y. It has edges, which means that in the above example there are ${m} × ${f} = ${m×f} dates.

Archie