سوال ۱۱۷ کنکور ارشد علوم کامپیوتر ۱۳۹۹

Reading the graph

The figure is a horizontal chain of $5$ diamonds. Label the $6$ vertices on the middle horizontal line (the spine) as $s_0, s_1, \dots, s_5$. Between each consecutive pair $s_{i-1}, s_i$ sits a top vertex $t_i$ and a bottom vertex $b_i$. Diamond $i$ is the vertex set $\{s_{i-1}, s_i, t_i, b_i\}$, and it is a complete graph $K_4$: the four outer sides $s_{i-1}t_i,\, t_i s_i,\, s_i b_i,\, b_i s_{i-1}$ are present, plus both diagonals — the spine edge $s_{i-1}s_i$ (horizontal diagonal) and the edge $t_i b_i$ (vertical diagonal).

There are $6 + 2\cdot 5 = 16$ vertices, so a perfect matching (a set of edges covering every vertex exactly once) uses $8$ edges.

Key observation: each $t_i, b_i$ is local

The vertices $t_i$ and $b_i$ appear only in diamond $i$ (they touch nothing outside it). So in any perfect matching, $t_i$ and $b_i$ must be matched using edges inside diamond $i$. The only "shared" vertices between adjacent diamonds are the spine vertices.

Process the diamonds left to right and track one bit of state: whether the incoming spine vertex $s_{i-1}$ is already matched (consumed by diamond $i-1$) or still free.

Case A — $s_{i-1}$ is free. Then diamond $i$ must internally cover three vertices $s_{i-1}, t_i, b_i$. Matching an odd number of vertices ($3$) inside $\{s_{i-1}, s_i, t_i, b_i\}$ forces $s_i$ to be used as well. The valid pairings are:

$\{s_{i-1}t_i,\, b_i s_i\},\quad \{s_{i-1}b_i,\, t_i s_i\},\quad \{s_{i-1}s_i,\, t_i b_i\}.$

That is $3$ ways, and in every one of them $s_i$ becomes matched.

Case B — $s_{i-1}$ is already matched. Then only $t_i, b_i$ remain to cover. If either were matched to $s_i$, the other would have to use $s_{i-1}$ — but $s_{i-1}$ is taken. So the only option is the edge $t_i b_i$: $1$ way, and $s_i$ stays free.

Multiply along the chain

Start with $s_0$ free. The state alternates deterministically:

The last spine vertex $s_5$ has no diamond to its right, so it must be matched inside diamond $5$ — which is exactly what Case A delivers, so the count is consistent. Multiplying the independent choices:

$3 \times 1 \times 3 \times 1 \times 3 = 3^{3} = 27.$

The answer is $27$ (option 1).

General pattern

For a chain of $k$ such $K_4$ diamonds there are $3k+1$ vertices, so a perfect matching exists only when $k$ is odd, and then the count is $3^{(k+1)/2}$. Here $k = 5$ gives $3^{3} = 27$.

Exam trick: When a graph is a chain of identical blocks glued at single "cut" vertices, scan it block by block and carry just the cut vertex's matched/free status. The per-block choices multiply, turning a $16$-vertex matching count into a one-line product.