כאשר בגרף יש מסלול אוילרי, שהוא מסלול בגרף העובר בכל קשת בו בדיוק פעם אחת, מסלול זה הוא כמובן הקצר ביותר.
בגרף שבו יש מסלול אוילרי, כל הצמתים הם מסדר זוגי (כלומר בכל צומת עובר מספר זוגי של קשתות), ולכן כאשר בגרף אין מסלול אוילרי, יש בו צמתים מסדר אי-זוגי. על פי למת לחיצות הידיים, מספר הצמתים הללו הוא זוגי. כדי לעמוד בתנאי הבעיה, יש לעבור פעמיים על קשתות היוצאות מצמתים אלה. לשם כך נכפיל קשתות המחברות בין שני צמתים מסדר אי-זוגי (צעד השקול למעבר פעמיים על אותה קשת), ובכך נהפוך את המסלול לאוילרי. בעת הכפלת הקשתות נבחר את אלה שאורכן הכולל הוא הקצר ביותר, ונקבל מסלול אוילרי הפותר את הבעיה.
וריאציות.
נחקרו גם וריאציות אחדות של הבעיה, שנמצאו כבעיות NP-שלמות:
משושה החורף
משושה החורף הוא מערך דמיוני של שישה כוכבים בהירים בשמי החורף היוצרים צורת משושה. קודקודי המשושה הם הכוכבים (מהקודקוד הצפון מערבי ועם כיוון השעון) קאפלה, אלדברן, ריג'ל, סיריוס, פרוקיון וקסטור או פולוקס, כולם עם בהירות נראית מדרגה מתחת ל-2 (מתחת ל-1.2 אם פולוקס משמש כקודקוד הצפון מזרחי). ששת הכוכבים ניתנים לצפייה כמעט מכל מקום על כדור הארץ, למעט דרום ניו זילנד, דרום צ'ילה וארגנטינה ואזורים מצפון לחוג הארקטי. צורת המשושה בולטת לעין בעיקר בחודשים דצמבר עד מרץ. בתוך המשושה בולט הכוכב ביטלג'וז שאינו מהווה חלק ממנו, אך יוצר עם סיריוס ופרוקיון צורת משולש כמעט שווה-צלעות שמכונה לעיתים משולש החורף.
כל אחד מכוכבי המשושה שייך לקבוצת כוכבים אחרת והקבוצות הן (בהתאמה לסדר הכוכבים לעיל) עגלון, שור, אוריון, כלב גדול, כלב קטן ותאומים.
משולש החורף
שמואל ייבין
שמואל יֵיְבין (2 בספטמבר 1896 – 28 בפברואר 1982) היה ארכאולוג ישראלי, מנהל אגף העתיקות והמוזיאונים (1948–1959), פרופסור באוניברסיטת תל אביב (1955–1969).
חתן פרס ביאליק לחכמת ישראל (1955) ובפרס ישראל למדעי היהדות (1968).
קורות חיים.
ייבין נולד בשנת 1896 בעיר אודסה שבדרום-מערב האימפריה הרוסית (אוקראינה), בנם של ניסן ואסתר ייבין, מורה ולימים עסקנית ביישוב.
בשנת 1905, בעקבות הפרעות, עלה לארץ ישראל עם אמו ושתי אחיותיו (ב-1908 הגיע גם אביו). הוא למד בגימנסיה הרצליה, וסיים לימודיו במחזור השני, בשנת 1914. לאחר תום לימודיו גויס לשרת בצבא האימפריה העות'מאנית. הוא שירת במלחמה בדרגת סגן-משנה בחזיתות ארץ ישראל ומקדוניה, וזכה על שירותו במדליית המלחמה הטורקית ובעיטור מטעם גרמניה (שאותו החזיר ב-1933, עם עליית הנאצים לשלטון). בשנים 1920–1923 למד ארכאולוגיה וערבית באוניברסיטת לונדון, ובתום לימודיו יצא לערוך חפירות ארכאולוגיות במצרים, בעיראק ובארץ ישראל. בשנים 1933–1935 השתתף בחפירות של יהודית מרקה-קראוזה בא-תל, שזוהתה עם העי.
עיסוקיו של ייבין בחפירות ארכאולוגיות נמשך באופן רציף עד 1933, לצד השלמת לימודים נוספים באוניברסיטת ברלין (1928–1929) וראשית פעילותו הציבורית. בשנת 1930 מונה לחבר בוועדת הכותל היהודית. בשנת 1935 התמנה לכהן כמזכיר מדעי של ועד הלשון, בתל אביב, תפקיד שבו החזיק עד 1942. בין השנים 1936–1939 עסק פעם נוספת בחפירות ארכאולוגיות בארץ ישראל ובעיראק. בשנים 1942–1944 שימש כמזכיר מערכת האנציקלופדיה המקראית, ולאחר מכן שימש עד קום המדינה בתפקיד המתרגם הראשי של ממשלת ארץ ישראל.
ייבין היה הראשון ששיער, על פי מסורות כתובות מהתקופה ומעט לאחריה, שמורדי בר כוכבא חידשו את עבודת הקרבנות והטקסים בבית מקדש זמני בירושלים. ספרו פורסם ב-1946 תוך כדי פרסומים בחו"ל על מכתבי בר כוכבא, שאיששו לכאורה את עמדתו. מאוחר יותר חנן אשל בעקבות חוקר המטבעות ליאו מלדנברג טען שמיעוט ממצא המטבעות בירושלים מורה על כך שירושלים כלל לא נכבשה בימי בר כוכבא, ושבדיקות כימיות לבקשתו הוכיחו שתעודות שונות עליהם סמכו היו מתקופה הקודמת למרד בר כוכבא. בשנת 2006 פרסם חוקר המטבעות יהושע זלוטניק מאמר ממצה המגן על עמדת ייבין, לפחות לגבי כיבוש ירושלים, והנוטה לאשר גם את עניין כינון המקדש
מקום מדינת ישראל ועד 1959 כיהן ייבין כמנהל אגף העתיקות והמוזיאונים. במסגרת תפקידו נאבק לשמר מבנים עתיקים, מסגדים ושכונות עתיקות שיושבו על ידי ערבים לפני מלחמת העצמאות ולאחר המלחמה יועדו להריסה, אך ללא הצלחה רבה. במקביל הוא המשיך בעבודה ארכאולוגית וחפר בקיסריה.
בשנת 1955 הצטרף לסגל אוניברסיטת תל אביב שנוסדה אז. בשנים 1961–1969 עמד בראש החוג ללימודי המזרח התיכון הקדום, ובסיום תפקידו זה פרש מהאוניברסיטה. במקביל נמשכה פעילותו בוועד הלשון ומשנת 1953 במסגרת האקדמיה ללשון העברית, שבה היה משנת 1973 חבר הנהלה ושימש לאורך השנים חבר מערכת האנציקלופדיה העברית. כמו כן הוא היה חבר ועדת השמות הממשלתית (1949–1971).
בשנת 1955 זכה בפרס ביאליק לחכמת ישראל ביחד עם מיכאל אבי-יונה על הספר שחיברו השניים, בהשתתפות משה שטקליס: "קדמוניות ארצנו", שהופיע בהוצאת הקיבוץ המאוחד.
בשנת 1968 זכה בפרס ישראל למדעי היהדות על מפעל חייו.
בשנת 1972 מונה לחבר כבוד בחברה לחקירת ארץ-ישראל ועתיקותיה.
משפחתו.
בשנת תר"פ נישא לבתיה שטרן, שכמוהו עלתה לארץ ישראל (מהעיר קישינב, בירת פלך בסרביה שברוסיה) עם אמה ואחיה בראשית ימיה של תל אביב ולמדה בגימנסיה הרצליה.
בני הזוג היו הורים לשניים: יהודה ואפרת.
בתו אפרת ייבין הייתה ארכאולוגית שעסקה במחקר הפרהיסטורי, ונפטרה בשנת 1975. בשנת 1980 הוציא אביה ספר לזכרה שקיבץ את מחקריה: "ספר אפרת תרצה ייבין ז"ל".
אשתו בתיה הייתה בתו של המורה העברי הציוני אפרים פישל שטרן (1858–1930), שעלה לארץ ישראל אחרי המלחמה, בשנת תר"פ.
אחותה שרה הייתה אשתו של התעשיין והממציא, איש הציבור והנדבן שמואל (סם) בלום.
אחיה דוד שטרן (1889–1962) היה אגרונום, מנהל מחלקת ההתיישבות של הסוכנות היהודית במשך שנים, עד 1945, ולאחר מכן מנהל המחלקה הכלכלית של הסוכנות בניו יורק עד 1954, עת התמנה למנהל מרכז ההשקעות במשרד האוצר, תפקיד שבו שימש עד פרישתו בסוף אותו עשור.
אחותה חמדה הייתה אשתו של המומחה לחקלאות, חוקר תולדות היישוב והסופר עבר הדני (אהרן פלדמן).
מרחב גאודזי
בטופולוגיה, מרחב גאודזי הוא מרחב מטרי formula_1 (עם מטריקה formula_2), שבו כל המרחקים נמדדים על ידי מסילות מתאימות. הדרישה המקובלת היא שלכל שתי נקודות formula_3 במרחב תהיה איזומטריה מן הקטע formula_4 ל-formula_1, המעבירה את נקודות הקצה ל-formula_6 ול-formula_7. מרחב כזה הוא, כמובן, קשיר מסילתית. המסילה המתקבלת מ-formula_6 ל-formula_7 נקראת מסילה גאודזית, והיא מתארת את המרחק הקצר ביותר בין הנקודות.
בין הדוגמאות החשובות למרחבים גאודזיים - יריעת רימן שלמה (ובפרט כל משטח רימן); וגרף שבו מקצים על כל קשת מטריקה של קטע ממשי. כל מרחב מטרי שלם שבו לכל formula_3 יש נקודה formula_11 ביניהן (נקודה formula_12 כך ש-formula_13), הוא גאודזי.
דוגמה למרחב מטרי שאיננו גיאודוזי היא formula_14 (המישור האוקלידי ללא ראשית הצירים) שכן המרחק בין הנקודות formula_15 הוא formula_16, אך אין מסילה באורך formula_16 בין נקודות אלו.
קיימות להגדרה גם וריאציות חזקות יותר, שבהן דורשים קיומה של איזומטריה מהישר הממשי, העוברת בכל זוג נקודות נתון. במרחבים כאלו אפשר להמשיך את הקטעים הגאודזים עד לאינסוף, לשני הכיוונים, ברוח האקסיומה השנייה של אוקלידס. במרחב גאודזי ממלאות המסילות הגאודזיות תפקיד דומה לזה של הקווים הישרים במרחב אוקלידי, ואכן, המרחב האוקלידי (ביחס למטריקה הנורמית) הוא מרחב גאודזי, שבו הגאודזים הם הקווים הישרים.
ריסן
ריסן (שם מדעי: Blepharis) הוא סוג במשפחת הקוציציים. בארץ מיוצג על ידי המין ריסן דק ("Blepharis attenuata").
מאפייני הסוג.
זהו סוג גדול במשפחת הקוציציים, שרוב מיניו גדלים באזורים הטרופיים של העולם הישן (היבשות אסיה, אירופה ואפריקה).
מיני סוג זה הם עשבים רב-שנתיים או בני שיח, שלהם עלים קוצניים.
הפרחים ערוכים בשיבולת כלומר, מסודרים על ציר אחד בעמוד הפריחה, בצורה אופיינית למשפחה. הפרח אופייני למשפחה, ולו חפה קוצני גדול. צבע הפרח כחול. לפרח 'שפה' תחתונה בלבד, והיא מחולקת לאונות.
הפרי הוא מטיפוס הלקט.
הסוג בצמחיית ארץ ישראל.
מין אחד מסוג זה מצוי בארץ ישראל, ריסן דק ("Blepharis attenuata").
צורת חייו היא בן-שיח, והוא קוצני מאוד. פריחתו חלה במשך חודשים רבים בשנה, אך בעיקר בעונת הקיץ. מין זה מצוי בעיקר בחבלים המדבריים של הארץ, כדוגמת הנגב ומדבר יהודה, בערוצים יבשים ובבתות.
בעבר, נחשבו שני מינים מסוג זה למיוצגים בצמחיית ארץ ישראל: המין ריסן נאכל, הגדל בעיקר במדבריות ותפוצתו רחבה; והמין ריסן דק שנחשב לאנדמי לארץ ישראל. המינים נבדלו בחפים שבאמצע התפרחת. במקורות מידע שונים עדיין קיימת חלוקה זו. לעומת זאת, מכליל מחקר עדכני את כל האוכלוסיות בישראל תחת המין ריסן דק.
התאמת הריסן הדק ליובש.
צמח זה המצוי בבתי גידול יובשניים מהווה דוגמה טובה למספר מנגנונים המאפשרים קיום חיים במצבי עקה, אשר התפתחו הודות לתהליכים אבולוציונים.
כצמחי מדבר אחרים, הריסן הוא צמח קוצני מאוד, המונע ממנו להיאכל על ידי אוכלי עשב. כמו כן הקוצניות מצמצמת את שטח הפנים של העלה ובכך מפחיתה את אידוי המים ממנו.
אך עם זאת, ההתאמה המופלאה ביותר היא מנגנון הפצת הזרע והנביטה של הצמח. מנגנון זה נחקר על ידי החוקר הישראלי יצחק גוטרמן.