טענה על קשתות בעפ"ם
idan_izmirli 11 Feb 2019 16:46
בשיעורי הבית התבקשנו למצוא אלגוריתם שמוצא האם קשת שייכת לעפ"ם כלשהו והאם קשת שייכת לכל עפ"ם. הפתרון (לפחות שלי) כלל להוכיח שיש מסלול בין קצוות של קשת שמורכב רק מקשתות שקלות ממש ממנה אם"ם היא לא מופיעה באף עפ"ם, ויש מסלול בין קצוותיה שמורכב רק מקשתות שקלות או שוות אליה (שאינן היא עצמה) אם ורק אם יש עפ"ם בו היא לא מופיעה. שמתי לב שצריך את הטענה הזאת בשאלות רבות. כיוון שהיה צריך להוכיח אותה כלק משיעורי הבית אך היא לא הייתה מנוסחת ישירות בהם, אני לא בטוח אם מותר להשתמש בלי הוכחה בטענה הזאת. האם אפשר להשתמש בה בלי הוכחה?