Question

【題目】奧運會排球預(yù)選賽有支球隊參加，其中每兩隊比賽一場，每場比賽必決出勝負(fù)。如果其中有支球隊滿足：勝，勝，勝，勝，則稱這支球隊組成一個“階連環(huán)套”。證明：若全部支球隊組成一個 階連環(huán)套，則對于每個及每支球隊，必與另外某些球隊組成一個階連環(huán)套。

Answer 1

【答案】見解析

【解析】

以為頂點.如球隊勝，則在兩點間連一有向邊：，如此得階競賽圖.據(jù)條件，的個頂點可以排成一個階有向圈，設(shè)為.則的任兩點可沿箭頭方向相互到達(dá).

首先證明：任一球隊必在某個三階連環(huán)套中.

用分別表示被擊敗了的球隊集合和擊敗了的所有球隊集合.由于雙向連通，必有，使得.于是，組成三階連環(huán)套.

假若已證得，對于，圖中存在以為一頂點的階連環(huán)套，圈之外的點的集合為.

若中有一點，它所表示的球隊既擊敗了圈中的某個隊，又被圈中的另一個隊 所擊敗，點把圈分成兩條有向路，其中一條，例如它與有向路組成有向圈.

依次考慮路上各點與點間的鄰接情況，必有相鄰的兩點滿足，而.現(xiàn)去掉邊，而將路插入其間，便得到一個含有頂點的階連環(huán)套.

若中的任一點，它所表示的球隊要么擊敗了圈中的每個隊，要么被圈中的每個隊所擊敗，則集合可分為兩個不交的子集，其中，中的任一隊?wèi)?zhàn)勝了圈中所有的隊，而中的任一隊負(fù)于圈中所有的隊.由于圖雙向連通，故在集合中必有點 ，集合中有點，使得.在圈中任意去掉一個點，而用路代替，便得到一個含有頂點的階連環(huán)套，故結(jié)論對于成立.

由歸納法，結(jié)論成立.