משפט ארבעת הצבעים – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
בשלני (שיחה | תרומות)
אין תקציר עריכה
בשלני (שיחה | תרומות)
שורה 19:
'הוכחה' ראשונה להשערת ארבעת הצבעים פורסמה לראשונה בשנת [[1879]], על ידי [[אלפרד קמפ]] (Kempe). קמפ הציע שיטה המבוססת על שרשראות של מדינות סמוכות, שאמורה הייתה לאפשר הוספה של מדינה אחר מדינה למפה הצבועה, מבלי להזדקק לצבע חמישי. ההוכחה נבדקה, והתקבלה על-דעת בני זמנו. ואולם, 11 שנה מאוחר יותר הראה [[פרסי ג'ון היווד]] (Heawood) שההוכחה אינה נכונה. בנוסף, היווד הראה שחמישה צבעים מספיקים לצביעת כל מפה.
 
=== השקילות לצביעת קשתות של גרפים מדרגה 3 ===
 
במסגרת עבודתו על הבעיה, הוכיח היווד שצביעת מפות בארבעה צבעים שקולה לטענה הבאה: לכל [[גרף רגולרי|גרף 3-רגולרי]] [[גרף מישורי|מישורי]] [[גרף קשיר|2-קשיר-קשתות]] (כלומר, כזה שנשאר קשיר גם לאחר מחיקת אחת הקשתות) יש [[צביעת קשתות]] (כלומר, התאמה של צבע לכל קשת באופן ששתי קשתות נפגשות מקבלות צבעים שונים) בשלושה צבעים<ref>Louis H. Kauffman, [http://www.math.uic.edu/~kauffman/MapReform.pdf Reformulating the map color theorem], Discrete Mathematics, Volume 302, Issues 1-3, 28 October 2005, Pages 145-172, </ref>.