晚會節目安排

曉曉

最近學校要舉辦晚會，舞蹈社的張、王、李、趙、劉、孫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）