Question

下图中的二十个点各代表 Sarah 的一位同学。互为朋友的同学之间用线段连接。Sarah 生日聚会只邀请以下同学：她所有的朋友，以及至少和她某个朋友是朋友的同学。有多少位同学不会被邀请参加 Sarah 的聚会？

Each of the twenty dots on the graph below represents one of Sarah's classmates. Classmates who are friends are connected with a line segment. For her birthday party, Sarah is inviting only the following: all of her friends and all of those classmates who are friends with at least one of her friends. How many classmates will not be invited to Sarah's party?

$1$

$4$

$5$

$6$

$7$

答案：D

知识点：图论补集计数

难度评级：1400

解答：

Sarah 邀请她的朋友，以及至少和她某个朋友是朋友的同学。用图论语言说，她邀请距离 Sarah 为 $1$ 或 $2$ 条线段的点。

从图中可见，有 $4$ 个点与 Sarah 所在连通分量断开，另外还有 $2$ 个点在 Sarah 所在连通分量中但距离为 $3$ 条线段。

因此不会被邀请的同学有 $4+2=6$ 位。

所以正确答案是 D。

Sarah invites her friends and the classmates who are friends with at least one of her friends. In graph terms, she invites dots that are $1$ or $2$ line segments away from Sarah.

From the graph, $4$ dots are disconnected from Sarah’s component, and $2$ more dots in Sarah’s component are $3$ segments away.

Those $4+2=6$ classmates will not be invited.

Thus, D is the correct answer.

2003 AMC 8 第 18 题

答案：D

难度评级：1400

解答：

其他年份的第 18 题