بالنظر إلى بطولة مع قمة $ 2 ^ n $، تبين أن هناك بطولة فرعية مع رؤوس $ على الأقل N + 1 $ التي هي أكريك

Question

لذا فإن البطولة هي مجرد رسم بياني موجه بالكامل، وأعتقد.

أواجه مشكلة في إثبات هذه المشكلة.وأنا أعلم أنه الحث ولكن.كنت افكر القضية الأساسية هي $ 2 ^ 1 دولار $ ، وبالتالي لدينا بطولة فرعية من الرأس 1 + 1، والتي تحمل.

ثم في خطوة الحث لدينا لدينا لإظهار $ 2 ^ ^ {n + 1} $ .لكنني لست متأكدا من كيفية الاقتراب من ذلك.ستكون أي أفكار موضع تقدير للغاية.

Answer 1

البطولة هي الرسم البياني الموجه الخالي من الحلقة $ g= (v، e) $ حيث، لكل زوج من القمم المميزة $ u، v \ in v $ ، بالضبط واحد من $ (u، v) $ و $ (v، u) $ هو في $ e $ .

دليل المطالبات الخاصة بك هو الحث.

for $ n= 0 $ ادعاء صحيح منذ البطولة $ g $ مع $ 2 ^ 0= 1 $ thyclic تافهة، وبطولة فرعية فقط مع $ 0 + 1= 1 $ القمم هي $ G $ نفسها.

افترض الآن أن المطالبة تحمل ما يصل إلى بعض $ n \ ge 0 $ والنظر في البطولة $ g= ( V، E) $ مع $ | الخامس |= 2 ^ {n + 1} $ . اختر تقنية الرأس التعسفي $ v \ in v $ ، وقسم رأس $ v \ setminus \ {v \} $ في مجموعتين $ l={u \ in v \ setminus \ {v \} \ mid (u، v) \ in e \} $ و $ r={u \ in v \ setminus \ {v \} \ mid (v، u) \ in e \} $ . واحدة من $ l $ و $ r $ يجب أن تحتوي على ما لا يقل عن $ \ left \ lceil \ frac {| v \ setminus \ {v \} |} {2} \ right \ rceil=left \ lceil \ frac {2 ^ {n + 1} - 1} {2} \ \ rceil= 2 ^ n $ الرأس. حدد بشكل تعسفي $ 2 ^ n $ ، ثم استدعاء مجموعة من القمم المحددة $ s $ وبعد بواسطة فرضية حثي $ S $ يحتوي على البطولة الدرجة الفرعية Acyclic $ s '$ الحجم $ n + 1 $ ، ومنذ إما $ s '\ subseteq s \ subseteq l $ or $ s '\ subseteq s \ subseteq r $ ، لدينا هذا $ s' \ cup \ {v \} $ هو أيضا acyclic وبعد هذا يثبت المطالبة منذ $ | s '\ cup \ {v \} |= | S '| + 1= N + 2 $ .