משפט ארבעת הצבעים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
שורה 32:
בשנת [[1976]] נעזרו [[וולפגאנג האקן]] ו[[קנת אפל]] מ[[אוניברסיטת אילינוי באורבנה-שמפיין]] בשרשראות של קמפ, כדי להראות שכל מפה אפשרית שקולה לאחת מבין 1,936 מפות שונות. לאחר מכן הם הריצו תוכנית [[מחשב]] במשך 1,200 שעות כדי להראות שכל אחת ממפות אלה ניתנת לצביעה בארבעה צבעים. בשנת [[1996]] ניתנה הוכחה בעלת אופי דומה על ידי ניל רוברטסון, דניאל סנדרס, [[פול סימור]] ורובין תומס שבה היה די בבדיקה של 633 מפות. גם בדיקה זו דרשה הסתייעות במחשב.{{הערה|[http://people.math.gatech.edu/~thomas/FC/fourcolor.html The Four Color Theorem],{{כ}} School of Mathematics,{{כ}} באתר Georgia Tech,{{כ}} 8 בנובמבר 2007}}
רוברטסון וחבריו אף מצאו אלגוריתם ריבועי (שזמן הריצה שלו פרופורציוני לריבוע מספר הקודקודים) לצביעת גרף מישורי בארבעה צבעים {{הערה|N. Robertson, D. P. Sanders, P. D. Seymour & R. Thomas, E�ciently
four-coloring planar graphs, Proceedings of the ACM Symposium on the
Theory of Computing, 28 (1996), 571{575.}}.
==לקריאה נוספת==
|