晚会节目安排

晓晓

最近學校要举办晚会，舞蹈社的张、王、李、赵、刘、孙6名同学报名参加了A、B、C、D、E、F 6个节目，他们参加节目的情况如表1所示。

每位同学都参加了两个或3个节目，那么如何安排晚会的节目顺序，让同学们有充足的休息时间，不用连续进行两场表演呢？

答案解析

如果两个节目没有同一位同学参加，则表明它们在演出顺序上可以相邻，这时我们将它们用线段相连。

从表1可以看出，A节目与C节目没有同一位同学参加，它们之间可以用线段相连。类似地，以下节目之间也可以用线段相连：A与F，B与C，B与F，C与D，C与F，D与E，E与F。如图1所示。

从中找出一条连接全部节目的折线，即可安排晚会节目顺序。这种折线共有8条（括号内的路线表示反向），所以晚会的节目顺序有8种方案，只需从中选取1种即可：

A→F→E→D→C→B

（B→C→D→E→F→A）

A→F→B→C→D→E

（E→D→C→B→F→A）

A→C→B→F→E→D

（D→E→F→B→C→A）

A→C→D→E→F→B

（B→F→E→D→C→A）