טורניר הוא גרף מכוון שבו לכל שני קודקודים שונים u,v קיימת בדיוק אחת מן הקשתות (u,v) או (v,u). 1. הוכיחו שאם בט…

טורניר הוא גרף מכוון שבו לכל שני קודקודים שונים $u,v$ קיימת בדיוק אחת מן הקשתות $(u,v)$ או $(v,u)$.

1. הוכיחו שאם בטורניר אין מעגל מכוון באורך $3$, אז אין בו מעגל מכוון כלל.
2. בבעיית המינימיזציה נדרש להסיר מספר מינימלי של קודקודים מטורניר כך שהגרף הנותר יהיה חסר מעגלים. תנו אלגוריתם פולינומי בעל יחס קירוב $3$ והוכיחו את יחס הקירוב.