Compte tenu d'un tournoi avec des sommets de 2 $ ^ N $, montrez qu'il existe un sous-tournoi avec au moins N + 1 $ de sommets d'ACYCLIC

Question

Ainsi, un tournoi est juste un graphique dirigé complet, je crois.

J'ai du mal à prouver ce problème.Je sais que c'est une induction cependant.je pensais Le boîtier de base est 2 ^ 1 $ sommets, et nous avons donc un sous-tournoi de 1 + 1 sommets, qui contient.

Puis dans notre étape d'induction, nous devons montrer 2 ^ {n + 1} $ .Mais je ne sais pas comment aborder cela.Toute idée serait extrêmement appréciée.

Answer 1

Un tournoi est un graphique dirigé sans boucle $ g= (v, e) $ dans lequel, pour chaque paire de sommets distincts $ u, v \ in v $ , exactement l'un des $ (u, v) $ et $ (v, u) $ est dans $ E $ .

La preuve de votre demande est par induction.

pour $ n= 0 $ La réclamation est vraie depuis un tournoi $ g $ avec 2 $ ^ 0= 1 $ Les sommets sont trivialement acycliques et son seul sous-tournoi avec 0 + 1= 1 $ Les sommets sont $ g $ elle-même.

suppose maintenant que la réclamation contient jusqu'à une partie $ n \ ge 0 $ et envisager un tournoi $ g= ( V, e) $ avec $ | v |= 2 ^ {n + 1} $ . Choisissez un sommet arbitraire $ V \ in v $ et partitionnez les sommets de $ v \ setminus \ {v \} $ en deux ensembles $ l={u \ in v \ seminus \ {v \} \ moyen (u, v) \ in e \} $ et $ r={u \ in v \ seminus \ {v \} \ moyen (v, u) \ in e \} $ . Un de $ l $ et $ R $ doit contenir au moins $ \ gaucher \ lceil \ frac {| v \ seminus \ {v \} |} {2} \ droite \ rcil=gaucher \ lceil \ frac {2 ^ {n + 1} - 1} {2} \ droite \ rceil= 2 ^ n $ sommets. Sélectionnez arbitrairement 2 ^ N $ sommets de cet ensemble et appelez l'ensemble des sommets sélectionnés $ S $ . Par hypothèse inductive $ S $ contient un sous-tournoi acyclique $ s '$ de taille $ N + 1 $ , et puisque s '\ sous -éréq s \ sous -éréeq l $ ou $ S '\ Subreteq s \ Substeeq r $ , nous avons que $ s' \ tasse \ {v \} $ est aussi acyclique . Cela prouve la réclamation depuis $ | s '\ tasse \ {v \} |= | S '| + 1= n + 2 $ .