stanford-oval/wikipedia huggingface dataset:
גרף הידע

גרף הידע (באנגלית: The Knowledge Graph) הוא בסיס ידע (Knowledge base) המשמש את חברת גוגל על מנת לשפר את תוצאות החיפוש של מנוע החיפוש שלה באמצעות מידע סמנטי שנאסף ממגוון רחב של מקורות. זהו מאגר מידע המבוסס על ישויות ולא על מילות מפתח ושאילתות. אלו תשובות מלאות המראות הבנה, ולא רק תשובה אחת קצרה. מכיוון שהשאילתא אינה
רק תשובה למה ששואלים אלא כוללת הקשר רחב יותר, גוגל החליטו ליצור גרף שמבין את הישויות מהעולם האמיתי ואת היחסים שלהן עם דברים אחרים. תצוגת גרף הידע התווספה למנוע החיפוש של גוגל ב-4 במאי 2012, בתחילה רק למשתמשים הנמצאים בארצות הברית, ב-4 בדצמבר 2012 גרף הידע הושק בעוד שבע שפות: ספרדית, צרפתית, גרמנית, פורטוגזית, יפנית, רוסית ואיטלקית. גרף הידע מספק מידע מובנה ומפורט על הנושא, בנוסף לרשימה של קישורים לאתרים אחרים. המטרה היא שמשתמשים יוכלו להשתמש במידע זה על מנת לפתור את השאילתא שלהם ללא צורך להיכנס לאתרי אינטרנט אחרים על מנת לאתר את פריט המידע הרלוונטי בעצמם ועל מנת לקצר את זמן החיפוש תוך הבאת התשובה בדף החיפוש. בסיכום הקצר המוצג בגרף הידע נעשה לרוב שימוש כתשובה מדוברת במאגרי Google Now.
בסיס הנתונים של גרף הידע מהווה אוסף של ישויות כמו אנשים, מקומות, מדינות, ערים, יצירות אמנות ומוזיאונים, קבוצות ספורט, מבנים מפורסמים, סרטים, שחקנים ובמאים, זמרים, להקות ואלבומי מוזיקה וכיוצא באלו והוא מכיל את רשימת הישויות, את הסיווג שלהן, מידע המתאר אותן ואת הקשרים ביניהן. לדוגמה, "גרף הידע" עשוי להבין ש"מאזדה" זה סוג של "רכב".
ב-2013, כתב ראש "גוגל חיפוש", אמית סינגל (Amit Singhal) על היכולות החדשות של מנוע החיפוש של גוגל, וסיפר שבגוגל עבדו מאוד קשה על מנת לאפשר למנוע להתמודד עם שאלות הנשאלות על ידי בני אדם. סינגל ציין שלוש פונקציות עיקריות שצריכות להתפתח בעתיד החיפוש: מענה, שיחה וצפייה מראש. ברצונם ליצור מנוע חיפוש המבוסס של שיח בין האדם למחשב. חיפוש מסוג זה הודגם על ידי ג'ואנה רייט בכנס גוגל I/O ‏2013, גוגל נשאל שאלה "הראה לי מה ניתן לעשות בסנטה קרוז", גוגל ענה בעזרתו של גרף הידע, הראה מידע על המקום ואת המקומות הקשורים לסנטה קרוז. כעת נשאלת השאלה הבאה, כיצד לגרום למידע להישאר רלוונטי למשתמשים, איך ינצלו את החיפוש החדש לרף הידע ואיך תוכן האיחזור ישתנה בעקבות כך.
רקע

גוגל בונה את גרף הידע על בסיס כלל השאילתות של משתמשי מנוע החיפוש ועל בסיס הקשרים בין דפי אינטרנט, על בסיס ניתוח מאגרי מידע כגון ויקיפדיה, ויקימדיה וספר העובדות העולמי של ה-CIA, בנוסף לגוגל יש שני מקורות נוספים בהם הוא משתמש, סימון Schema.org ואתרים בני סמכא. גרף הידע מאפשר להציג כתשובה לשאילתת חיפוש במנוע החיפוש של גוגל, לא רק אוסף של קישורים לדפי אינטרנט, אלא "כרטיס מידע" הכולל מידע רב שקשור סמנטית לישות עליה בוצע החיפוש. גוגל מנסה לאחזר תשובות לפי היסטוריית החיפושים של המשתמש. בגוגל מנסים ליצור רשימת לינקים לתשובות שנשאלות על ידי המשתמשים.
לדוגמה: חיפוש הערך "ירושלים" יגרום להופעה של "כרטיס מידע" משמאל לתוצאות החיפוש (במנוע העברי). כרטיס זה יכלול תמונה של העיר, מפה, תקציר הערך מתוך ויקיפדיה, תאריך הקמה, שטח, מזג אוויר, אוכלוסייה, אתרים מעניינים וקישור לדף האינטרנט או דף הוויקיפדיה שלהם וכיוצא באלו. חברת גוגל, החלה להציג את "כרטיס ההכרות" בדף התוצאות של מנוע החיפוש שלה, החל ממאי 2012, בארצות הברית. גרף הידע מציג את כל המידע הרלוונטי, גם אם קיימת יותר מתשובה אחת לשאילתת החיפוש "הטאג' מהאל", המבנה או הזמר? המשתמש מקבל סיכום של הדברים ולעיתים עובדות חדשות, בסיס נתונים סמנטי מהווה צעד חשוב בהיסטוריה של עולם המחשבים מכיוון שהוא דומה לאופן שבו בני אדם מתייחסים לישויות מההיבט שלכל ישות יש "קשרים והקשרים", תכונות וכיוצא באלו.
בניית רשת סמנטית היא מהלך בעל חשיבות היסטורית, כלל עולמית מכיוון שהיא מאפשרת למחשבים לתקשר ביניהם - ללא קשר לחומרה, מערכות ההפעלה, שפת התכנות וכיוצא באלו. מימוש רשת סמנטית הוגדר על ידי סר טים ברנרס-לי ממכון CERN כבר בשנת 20011 והרעיון עצמו נהגה, אפילו, עוד לפני כן.
המהלך של גוגל הוא חלק מהמאבק על פתיחות הרשת העולמית כאשר סר טים ברנרס-לי דוגל בבניית רשת פתוחה ש"שייכת" למשתמשים בעוד שחברות כמו גוגל ופייסבוק, בסופו של דבר, מנכסות לעצמן את תשתיות הידע העולמיות.
היסטוריה ונתונים

בשנת 2012, גרף הידע הכיל למעלה מ-570 מיליון ישויות ולמעלה מ-18 מיליארד נתונים וקשרים בין הישויות ועליהן, זה נעשה בעזרת רשת סמנטית. בעת החיפוש זה מאפשר למנוע החיפוש לאחזר לי את התשובה שהוא חודש שהתכוונתי אליה על פי המשמעות והקשר המילים שהקלדתי. אם יש מילה בעלת כמה משמעויות מנוע החיפוש יאחזר את כל מה שנמצא בהקשר.
בחודש אוקטובר 2014 הודיעה גוגל שהיא שילבה את ה"אונטולוגיה" של משחקי מחשב - משחקי וידאו ב"גרף הידע". המשמעות הפרקטית העיקרית שאותה המשתמש יכול לראות, זו הופעה של "מסגרת מידע" עם פרטי ידע נוספים, מעבר למילות המפתח שלגביהם הוא שאל - בכל פעם שהוא יעשה חיפוש על מילה ש"בראיית" גרף הידע, מתקשרת לעולם התוכן של משחקי מחשב או משחקי וידאו. גרף הידע מופיע גם בחיפוש שנעשה בסמארטפונים ובטאבלטים.
בסוף חודש אוקטובר 2014, לפי האתר The Verge, גוגל שילבו לתוך גרף הידע את הטקסונומיה של בעלי החיים. כמו כן, על פי המאמר, גוגל עושה "הצלבות" לגבי כל מיני ישויות וקשרים שהיא משלבת לתוך "גרף הידע" כך שבמובנים רבים, "גרף הידע" נשען על סוג של חוכמת המונים. במאמר מופיעה הדוגמה של השאילתה "עז" וציון העובדה שבתשובה מופיע "כרטיס מידע" הכולל את תוחלת החיים של ה"עז" ואת כל סוגי העיזים המוכרים למדע. בפברואר 2016 התירה גוגל לחברות מסחריות לעדכן את גרף הידע שלהם על מנת לספק מידע מדויק ועדכני אודות העסק שלהם. לא כל עסק יכול לעדכן את גרף הידע שלו, רק עסקים שעוברים את התנאים שגוגל הגדירו. יש שדות שאי אפשר לעדכן, כגון כותרת, תמונות ועוד.במרץ 2016 הוסיפו גוגל את כפתור השיתוף, דרכו ניתן לשתף את גרף הידע המוצג לנו ברשתות החברתיות השונות.
תחרות

חברות נוספות שיצרו גרף ידע משלהם:
גרף הידע של Bing – הושק ביוני 2013 בשם "Satori". מבוסס על ישויות, ניתן לחפש בו מידע על אנשים, מפורסמים, מקומות ועוד. בזכות גרף הידע של Bing ניתן לשאול את מנוע החיפוש שאלות כדוגמת "מהו ההר הכי גבוה בעולם?".
גרף הידע של LinkedIn – הושק ב-6 באוקטובר 2016. מבוסס על ישויות כגון אנשים, עבודות, כותרות, מקומות, חברות וכו'. המידע של גרף הידע הזה נלקח מתוכן מבוסס משתמש ממשווקים, יועצי חברות, משתמשים ומגויסים, את המידע הזה מוסיפים למידע שאוחזר מהאינטרנט. על גרף הידע לדרג משתמשים חדשים, מתפרסמות בו עבודות חדשות, חברות חדשות וישנן כותרות המופיעות בפרופילים של משתמשים ותיאורי עבודה.
גרף הידע של Baidu – מאחזר את התוכן ממקורות רבים ולאחר מכן מסווג תכנים אלו ישויות שונות. גרף הידע מציג ריבוע תוכן בצד ובו מידע על שאילתת החיפוש, בנוסף דרך הידע מאחזר מידע הקשור לנושא שחיפשנו עליו.
גרף הידע של Yahoo – יאהו מפעילה גרף ידע עצמאי בתוך מנוע החיפוש שלה.
ראו גם

ויקינתונים
רשת סמנטית
נתונים מקושרים
הערות שוליים

1 2  Amit Singhal, Introducing the Knowledge Graph: Things not Strings, (Official Blog (of Google, ‏16/05/2012
↑  Casey Newton, How Google is taking the Knowledge Graph global, Cnet, ‏14/12/2012
1 2  עומר, גרף הידע של גוגל משנה את עולם החיפוש – הכינו את אתרכם למהפכה, באתר Marketing, ‏20/02/2016
↑  Jessica Lee, OK Google: ‘The End of Search as We Know It, Search Watch Engine, ‏16/05/2013
↑  אי-פי, מנוע חיפוש חדש של גוגל: תשובות במקום לינקים, באתר הארץ, 16 במאי 2012
↑  John Koetsier, [”. http://venturebeat.com/2013/01/22/larry-page-on-googles-knowledge-graph-were-still-at-1-of-where-we-want-to-be/ Larry Page on Google’s Knowledge Graph: ‘We’re still at 1% of where we want to be’], Venturebeat, ‏22/01/2013
↑  Ed Oswald, Demystifying semantic search, Extreme Tech, ‏09/05/2012
↑  Tony Edward, How to enhance your Google Knowledge Graph result, Search Engine Land, ‏01/04/2016
↑  Greg Finn, Finally! Brands Can Edit Their Knowledge Graph Cards In Google, Marketing Land, ‏10/02/2016
↑  Barry Schwartz, Google adds share feature to Knowledge Graph panel, Search Engine Land, ‏30/03/2016
↑  Richard Qian, Understand Your World with Bing, (Official Blog (of Bing, ‏21/03/2013
↑  Qi He, Building the LinkedIn Knowledge Graph, LinkedIn Engineering, ‏06/10/2016
↑  BAIDU, INC, (Official Blog (of Baidu, ‏28/03/2014 (ארכיון)
↑  Barry Schwartz, [”. http://searchengineland.com/yahoo-has-their-own-knowledge-graph-not-without-their-own-embarrassing-issues-218538 Yahoo Has Their Own Knowledge Graph, Not Without Their Own Embarrassing Issues], Search Engine Land, ‏14/04/2015
דוד צבי אורדנטליך

הרב דוד צבי אורדנטליך (ט"ו באדר ה'תרצ"ז, פברואר 1937 – כ"ט בחשוון ה'תש"ף, 27 בנובמבר 2019) היה רבה האשכנזי של ביתר עילית.
ביוגרפיה

נולד בבודפשט, הונגריה לרייזל מלכה ולרבי זאב. בשנת ה'תשי"א עלה עם הוריו לישראל. למד בישיבת לומז'ה בפתח תקווה שם כתב וערך את שיעורי ראש הישיבה רבי אהרון כץ, ובישיבת סלבודקה בבני ברק.
לאחר נישואיו לברכה ברזל התגורר בבני ברק ולמד בכולל חזון איש. הוסמך להוראה על ידי הרב יצחק יעקב וייס. מספר שנים לאחר נישואיו מונה לר"מ בישיבת חכמי לובלין בבני ברק.
בשנת ה'תשכ"ז עם הקמת ישיבת אוהל יעקב מונה לשמש כר"מ בישיבה, במקביל מסר שיעורים גם בישיבת רוז'ין בירושלים.
עם ייסוד בית דין צדק בני ברק של הרב נסים קרליץ מונה לכהן כדיין בהרכב הראשון של בית הדין יחד עם הרב פינחס שרייבר.
במשך תקופה כיהן כרב קהילת 'שובה ישראל' בארגנטינה וכראש כולל אברכים במרסיי צרפת. על אף שיוכו למגזר הליטאי, עמד בקשרים טובים עם אדמו"רים ורבנים חסידים.
ביוגרפיה > רבנות העיר ביתר

לאחר הקמת היישוב ביתר עילית, הוקמה ועדה מיוחדת לאיתור רב ליישוב, חברי הוועדה היו ראש הכולל הראשון ביישוב, נציג הציבור הליטאי ונציג הציבור הספרדי, חסידי בויאן שהיו מראשוני המתיישבים המליצו על הרב אורדנטליך שאותו הכיר מתפקידו בישיבת בויאן. הרב אורדנטליך נבחר לכהן כרב היישוב ואב בית הדין המקומי. לצדו, נבחר הרב יעקב תופיק אביעזרי כרב הספרדי.
לאחר הכרזתה כעיר, פרש באופן רשמי מתפקידו, אך המשיך לשאת בתפקיד באופן לא רשמי. בשנותיו האחרונות כוחו נחלש, והוא התנייד בכיסא גלגלים, וחלק מתפקידיו המעשיים הועברו לידי הרב צבי ברוורמן.
נפטר בכ"ט בחשוון ה'תשע"ט, 27 בנובמבר 2019, ונקבר בבית הקברות של נציבי ישיבת פוניבז' בבני ברק.
הערות שוליים

↑  מנחם הירשמן, הודה, זיווה והדרה: הרב אורדנטליך זצ"ל, באתר כל הזמן, ‏30 בנובמבר 2019
דורותי דל

| --- | --- |

 לידה:  30 בינואר 1915 האטיסבורג, ארצות הברית 
 פטירה:  8 ביוני 1934 (בגיל 19) אלטדנה, ארצות הברית 
 מקום קבורה:  Metairie Cemetery 
 מדינה:  ארצות הברית 
 תקופת הפעילות:  מ-1932 
 פרופיל ב-IMDb
 
דורותי דל (באנגלית: Dorothy Dell;‏ 30 בינואר 1915 - 8 ביוני 1934) הייתה שחקנית אמריקאית שנהרגה בתאונת דרכים, בגיל 19.
ביוגרפיה

דל נולדה במדינת מיסיסיפי ובגיל שלוש עשרה עברה עם הוריה לניו אורלינס, היא רצתה בתחילה להיות זמרת והתגלתה על ידי המלחין ווסלי לורד, מיד לאחר מכן היא חתמה חוזה בהפקת רדיו.
בגיל חמש עשרה זכתה בתואר "מיס ניו אורלינס", אחר כך השתתפה בתחרות היופי הבינלאומית שנערכה בטקסס שם הוכתרה כמיס תבל. לאחר ההצלחה בתחרויות אלו היא לקחה חלק במופעי וודוויל.
ב-1931 עברה לניו יורק ולילה אחד גילה אותה פלורנץ זיגפלד והזמין אותה לבוא להופיע בברודוויי, שם לקחה חלק במופעים, ב-1933 עברה להוליווד וחתמה חוזה סרטי פרמאונט, הופעתה הקולנועית הראשונה הייתה בסרט "Wharf Angel", הסרט זכה להצלחה ומשחקה זכה לביקורות משבחות, ב-1934 שיחקה בסרט "מיס מארקר הקטנה", ב-1934 גם שיחקה בסרט "Shoot the Works" דבר שהוביל להשוואות בינה לבין מיי וסט.
ב-8 ביוני 1934 נהרגה בתאונת דרכים.
דוד צבי אליאך

רבי דוד צבי אליאך 

תמונה זו מוצגת בוויקיפדיה בשימוש הוגן.
נשמח להחליפה בתמונה חופשית.
הרב דוד צבי אליאך (י"ב באדר תרצ"א, 1931 – ט"ז בניסן תשע"ד, אפריל 2014) היה המשגיח של ישיבת איתרי בירושלים וישיבת נחלת דוד בפתח תקווה.
תולדותיו

נולד בירושלים, דור שישי בארץ ישראל, בנם של אברהם אשר אליאך, מחסידי קרלין, והנדיל-פייגה, בת ישראל יצחק לוי, מחסידי סטריקוב. דודו הוא הרב חיים יעקב גולדוויכט. בגיל חמש מתה אמו ובגיל אחת עשרה מת אביו והוא גדל עם אחיו הגדול ושתי אחיותיו אצל אבי סבו שלמה יוסף אליאך ובבית היתומים דיסקין, שם למד אצל הרב צבי קופשיץ. זמן קצר לפני גיל הבר מצווה עבר ללמוד בישיבת תפארת ישראל בחיפה. לאחר מכן נמנה עם "קיבוץ" הבחורים שארגן הרב מרדכי שמואל קרול בכפר חסידים.
בשנת תש"ז (1947) החל את לימודיו בישיבת חברון בירושלים. כעבור זמן עבר ללמוד בישיבת סלבודקה בבני ברק שנוסדה באותה תקופה. בתקופת מלחמת העצמאות שהה ברחובות, שם התוודע לראשונה לרב שך, שכיהן אז כר"מ בישיבת קלצק בעיר.
נמנה עם הקבוצה הראשונה של תלמידי ישיבת כנסת חזקיהו שנוסדה בזכרון יעקב בשנת תש"ט (1949), ובמשך תקופה למד בחברותא עם ראש הישיבה ומייסדה, הרב נח שימנוביץ. כעבור זמן שב ללימודיו בישיבת חברון. בתקופה זו היה מקורב לגדולי המוסר הרב צמח שלומוביץ, הרב שמואל הלל שינקר והרב אליהו לופיאן, והיה נכנס לוועדי המוסר שהיו מוסרים הרב יחזקאל לוינשטיין והרב אליהו אליעזר דסלר ב"בית המוסר" בירושלים.
באמצע שנות ה-50 נישא לרחל, בתו של הרב אליהו מאיר קובנר, ראש ישיבת "פורת יוסף" ברחובות. לאחר נישואיו כיהן כר"מ בישיבתו של חותנו ברחובות. כעבור זמן עבר להתגורר בבני ברק וכיהן כר"מ בישיבת ברסלב בעיר. במשך תקופה כיהן כראש ישיבה ביד בנימין.
בשנת תשל"ב (1972) התמנה למשגיח של ישיבת איתרי בירושלים. בתקופה זו חיבר את ספרו "דרך אמונה" על ענייני אמונה. הספר קיבל את הסכמת הרב שך, שכתב: "הראני כבוד ידידי הרה"ג יקר היקרים, גדול בתורה וירא אלוקים מרבים... העלה על הכתב ממה שחידש במחשבת היראה... וכל המעיין בהם ימצא טעם וחיזוק להוסיף ביראה ותורה, כי הדברים נאמרו בדעת תורה". בשנת תשמ"ד (1984) עבר לכהן כמשגיח של ישיבת נחלת דוד בפתח תקווה ושימש בתפקידו שלושים שנה.
חיבר ספרים בענייני מחשבה ומוסר. לאורך השנים מסר שיעורי תורה ומוסר בקהילות ובבתי מדרש רבים, ובעיקר בשכונת מגוריו עזרת תורה בירושלים.
נפטר למחרת חג הפסח תשע"ד, ונקבר בהר המנוחות בירושלים.
משפחתו

אבי המשפחה בארץ ישראל היה הרב שלמה יוסף מסטולין ואחיינו של רבי אהרן הגדול מקרלין (בן אחיו ר' יצחק). הוא עלה לארץ ישראל בשנת ת"ר. בנו היה הרב אברהם אשר אליאך, שהיה מחשובי חסידות קרלין בטבריה ומחנכו של האדמו"ר הינוקא רבי ישראל פרלוב, עלה לארץ ישראל בשנת תרי"ז. בנו היה העסקן שלמה יוסף אליאך, אבי סבו של הרב דוד צבי.
בנו הוא הסופר דב אליאך, מחבר הספרים "פנינים משלחן גבוה", "אבי הישיבות" ו"הגאון".
שלוש אחיותיה של אשתו נישאו לרבנים: יובל-יוסף אורדנטליך, שהיה רב בית הכנסת איצקוביץ' בבני ברק, מרדכי קוקיס (בנו של הרב פסח קוקיס) ונח חפץ, המכהן כמשגיח בישיבת כנסת מרדכי במבשרת ציון.
ספריו

דרך אמונה – ענייני מוסר ומחשבה
דרך המועדים – על מועדי ישראל
ברכת דוד – חידושים על מסכת ברכות
דרך עליה - בירור סוגיות בגמרא ומדרש בקנייני תורה ועבודה
חידושי דוד - ביאורים וחידושים בענייני הלל ושירה
מסורת התורה - יסודות ודורות ותקופות במסירת התורה וחיבור וכתיבת תורה שבעל פה
גרף מישורי

ייצוג גרפי של גרף מישורי
בתורת הגרפים, גרף מישורי הוא גרף שניתן לצייר במישור מבלי שהקשתות תחתוכנה זו את זו (חוץ מאשר בצומתי הגרף). לגרפים כאלה יש חשיבות מיוחדת באלגוריתמים הקשורים בראייה ממוחשבת וביישומים של תורת הגרפים בתעשייה, למשל לתכנון מעגלים חשמליים.
הגדרות פורמליות

גרף מישורי הוא גרף שאפשר לשכן במישור. שיכון של גרף במישור הוא מודל גאומטרי שלו, שבו הצמתים הם נקודות במישור והקשתות הן עקומות שלא חותכות את עצמן או אף עקומה אחרת (חוץ מאשר בקודקודי הגרף). כל גרף ניתן לשיכון במרחב האוקלידי התלת-ממדי  \mathbb {R} ^{3}.
פאות של גרף משוכן במישור הן רכיבי הקשירות (הטופולוגיים) שנקבל במישור אם נסיר את הצלעות (האזורים שנתחמים על ידי הקשתות). האזור שמחוץ לצורה שיוצר הגרף הוא הפאה היחידה שאינה חסומה. מקובל לסמן את מספר הצמתים (vertices) של הגרף באות v, את מספר הקשתות (edges) ב- e, ואת מספר הפאות (faces) באות f.
נוסחת אוילר

גרף מישורי קשיר מקיים:
\ f=e-v+2
הוכחה: באינדוקציה על מספר הפאות, אם f = 1 אז אין בגרף מעגלים, לכן (הגרף קשיר) מדובר בעץ ומתקיים e = v - 1. אם f > 1 יש בגרף מעגל. כל קשת במעגל מהווה שפה לשתי פיאות בדיוק ואם נסיר אחת נקטין את מספר הקשתות והפאות באחת.
עבור גרף מישורי עם k רכיבי קשירות נכליל:
\ f=e-v+k+1
הוכחה: (שימו לב שהפאה החיצונית משותפת לכל רכיבי הקשירות)
 f=\sum _{i=1}^{k}(e_{i}-v_{i}+2)-(k-1)=e-v+k+1
באופן כללי יותר, אם במקום לצייר את הגרף במישור מציירים אותו על-פני משטח קומפקטי כלשהו, הצירוף  \ f-e+v הוא קבוע, השווה למאפיין אוילר של המשטח. לנוסחה זו יש גם פירוש הומולוגי.
אפיון של גרפים מישוריים

הגרף השלם  \ K_{5} והגרף הדו-צדדי השלם  \ K_{3,3} אינם מישוריים (ראו הוכחה להלן), ואם כך גם החלוקות שלהם אינן מישוריות. מתברר שזהו ההסבר היחיד לאי-מישוריות: כל גרף שאין לו תת-גרף שהוא חלוקה של אחד משני הגרפים הבעייתיים, הוא גרף מישורי. זהו תוכנו של משפט קורטובסקי (Kuratowsky). ניסוח שקול של התנאי שניתן בידי וגנר (Wagner) מדבר על מינורים של הגרף (גרפים המתקבלים מהגרף המקורי על ידי סדרה של מחיקת צמתים ואיחוד זוגות צמתים המחוברים בקשת) - גרף הוא מישורי אם אין לו מינור שהוא אחד משני הגרפים הבעייתיים.
משפט קורטובסקי מדגים את משפט המינורים (Robertson-Seymour), שלפיו כל תכונה של גרפים הנשמרת במעבר ממינור לגרף מוסברת בכך שגרף מקיים את התכונה אם ורק אם אין לו מינורים בקבוצה סופית מתאימה של תת-גרפים "בעייתיים". לדוגמה, אפשר לומר שגרף הוא k-מישורי אם אפשר לשכן אותו במישור, באופן שיש לכל היותר k חיתוכים בין קשתות (גרף 0-מישורי הוא גרף מישורי במובן שהוגדר לעיל). אז לכל k קיימת קבוצה סופית של גרפים 'אסורים', כך שכל גרף שאינו k-מישורי מכיל תת-גרף אסור.
אפיון של גרפים מישוריים > תנאים הכרחיים למישוריות

נציג כמה תנאים הכרחיים למישוריות, הנובעים משיקולים פשוטים יחסית.
משפט: בגרף מישורי פשוט וקשיר בעל  v\geq 3 מתקיים   e\leq 3v-6
הוכחה: כל קשת גובלת בשתי פאות לכל היותר ופאה נתחמת על ידי שלוש קשתות לפחות, כלומר  f\leq {\frac {2e}{3}} ויחד עם נוסחת אוילר יתקבל:  \ e-v+2\leq {\frac {2e}{3}}.
מסקנה: הגרף השלם בן חמישה קודקודים  \ K_{5} אינו מישורי ( \ e=10\ v=5).
מסקנה נוספת: בגרף מישורי  \delta (G)\leq 5 כאשר  \ \delta (G) הוא הדרגה המינימלית של קודקוד בגרף.
הוכחה: אחרת  \ e={\frac {1}{2}}\cdot \sum _{x\in V}^{}d(x)\geq {\frac {6\cdot v}{2}}=3\cdot v.
משפט: בגרף מישורי  \ e\leq {\frac {g}{g-2}}\cdot (v-2) כאשר g הוא מותן הגרף (אורך המעגל הפשוט הקצר ביותר בגרף).
הוכחה: זהו חידוד של המשפט הקודם, כאשר הפעם כל פאה נתחמת על ידי g קשתות לפחות.
מסקנה: הגרף הדו צדדי השלם  \ K_{3,3} אינו מישורי (כאן המותן שווה ל-4).
הוכחה נוספת לכך ש  \ K_{3,3} אינו מישורי:
נניח בשלילה ש  \ K_{3,3} מישורי. לגרף 6 קודקודים ו9 צלעות. לפי נוסחת אוילר:
\ v-e+f=2
לכן יש לגרף 5 פאות. לכל פאה יש לפחות שלוש צלעות, וכל צלע יכולה להשתתף בשתי פאות לכל היותר. מכאן:
\ {\frac {2\,e}{5}}=3.6 מספר הצלעות הממוצע בכל פאה.
לכן חייבת להיות פאה עם לכל הפחות 3 צלעות ולכל היותר 3.6 צלעות - כלומר פאה בעלת 3 צלעות.
קיבלנו סתירה מאחר ש  \ K_{3,3} הוא גרף דו צדדי שלא מכיל משולשים מאחר שכל מעגליו באורך זוגי.
דוגמה לשימוש בתנאים למישוריות

ניתן לפתור את הבעיה הגאומטרית: לכמה שטחים אפשר לחלק מעגל באמצעות פיזור n נקודות על פניו במרחקים שווים, וחיבור כל זוג נקודות בקו. כאשר 
אם  \displaystyle n אי זוגי.
אם  \displaystyle n אי-זוגי לא ייתכן שנחתכים יותר משני אלכסונים בנקודה. נתייחס לכל נקודת חיתוך כאל קודקוד. הגרף המתקבל הוא מישורי ומכאן מקיים את נוסחת אוילר. יש  \displaystyle n קודקודים על שפת המעגל ו  \displaystyle {\binom {n}{4}} קודקודים בתוך המעגל. (בין כל 2 צלעות זרות יש נקודת חיתוך) נשתמש בנוסחת אוילר:
\displaystyle f=e-n-{\binom {n}{4}}+2
מספר הצלעות שווה לסכום הדרגות של כל הקודקודים לחלק ל - 2. על שפת המעגל דרגת כל קודקוד היא  \displaystyle n-1 ובתוך המעגל - 4.
ומכאן:
\displaystyle f={\frac {n(n-1)+4\,{\binom {n}{4}}}{2}}-n-{\binom {n}{4}}+2
\displaystyle f={\binom {n}{2}}+{\binom {n}{4}}+1
גרפים מישוריים ומפות

כשקרטוגרף מצייר מפה מדינית, הוא משתדל לצבוע מדינות שכנות בצבעים שונים, כדי להקל על ההבחנה ביניהן. הדרך הטבעית לחקור מצבים כאלה בתורת הגרפים היא להגדיר את הגרף הדואלי למפה, שבו הצמתים הם המדינות, וזוג צמתים מחוברים בקשת רק כאשר המדינות המתאימות שכנות זו לזו. מכיוון שהמפה המקורית היא מישורית (או כדורית, אם מדובר במפה כלל-עולמית), הגרף המתקבל הוא גרף מישורי.
המשימה של הגאוגרף היא לצבוע את צומתי הגרף, באופן שזוג צמתים מחוברים ייצבעו בצבעים שונים. משפט ארבעת הצבעים מבטיח שתמיד ניתן לעשות זאת בארבעה צבעים או פחות. בלשון אחרת, המשפט מבטיח שלכל גרף מישורי יש 4-צביעה.
הגרף  K_{5}
הגרף  K_{3,3}
גרף n-צביע

בתורת הגרפים, גרף  n-צביע הוא גרף שאפשר לצבוע את הקודקודים שלו ב-n צבעים, כך ששני קודקודים סמוכים אינם צבועים באותו צבע.
עבור גרף  G, מסמנים ב- \chi (G) את המספר הקטן ביותר של צבעים הדרוש לצביעת הקודקודים שלו. מספר זה נקרא מספר הצביעה (או המספר הכרומטי) של הגרף.
עבור  k>2, ההכרעה האם  \chi (G)=k היא בעיה NP שלמה. לגרף יש מספר כרומטי 2 אם ורק אם אין בו מעגל באורך אי זוגי.
היסטוריה

הקשר נפוץ שבו הופיעה בעיית צביעת גרף היא בעיית צביעה של גרפים מישוריים בדמות של צביעת מפות. בשנת 1852 בעת שניסה לצבוע מפה של מחוזות אנגליה, העלה פרנסיס גאת'רי את השערת ארבעת הצבעים, על פיה די בארבעה צבעים לצביעת מפה כך שאף אזור שגובל באזור אחר לא יחלוק עימו את אותו הצבע. אחיו של גאת'רי נועץ עם מורו למתמטיקה אוגוסטוס דה-מורגן בקולג' האוניברסיטאי של לונדון שהזכיר את הבעיה במכתב לויליאם המילטון. ב-1878 הובאה הבעיה לתשומת לבו של ארתור קיילי, שהציג אותה בפני החברה המלכותית הבריטית. אלפרד קמפ (Kempe) פרסם הוכחה למשפט, שהתקבלה על המתמטיקאים בני זמנו, אך התבררה כשגויה 11 שנה מאוחר יותר כשפרסי ג'ון היווד (Heawood) הצביע על טעות בהוכחה, אך הצליח להוכיח כי די בחמישה צבעים. ההוכחה לכך שאפשר להסתפק בארבעה נמצאה רק ב-1976 על ידי קנת' אפל (Appel) ווולפגנג האקן (Haken), והיא כרוכה בחיפוש ממוחשב על-פני אלפי מקרים.
השערה מפורסמת אחרת בהקשר לצביעת גרפים הועלתה ב-1960 על ידי המתמטיקאי הצרפתי קלוד ברגה (Berge) השערת הגרף המושלם, אשר העלה אותה בהקשר לרעיון מתורת האינפורמציה של קיבול אפס שגיאה (zero-error capacity) בגרף. השערת המשפט הייתה פתוחה במשך שנים רבות עד שהוכחה על ידי צ'ודנובסקי, רוברטסון, סימור ותומאס ב-2006.
חסמים על מספר הצביעה

עבור גרף  G עם  n צמתים מקבלים טריוויאלית ש- 1\leq \chi (G)\leq n.
אם מסמנים ב  \triangle (G) את הדרגה המקסימלית של צומת ב- G אז  \chi (G)\leq \triangle (G)+1. תוצאה זאת ניתן לשפר בצורה הבאה: אם עבור  k\in \mathbb {N}  בכל תת-גרף מושרה  H של  G קיים צומת  v\in H כך ש- d_{H}(v)\leq k אז  \chi (G)\leq k+1. עבור  k=\triangle (G) תנאי זה נכון ולכן האי-שוויון גורר את החסם הקודם. עבור גרף שלם על n צמתים  \triangle (G)=n-1 ו- \chi (G)=n ועבור מעגל אי-זוגי  \triangle (G)=2 ו  \chi (G)=3 ומכאן שאי אפשר לשפר את המשפט באופן כללי. אולם משפט ברוקס קובע כי לכל שאר הגרפים הקשירים  \chi (G)\leq \triangle (G).
נסמן ב- \omega (G) את גודל הקליקה המקסימלית ב- G אז  \chi (G)\geq \omega (G). אם אי-שוויון זה הדוק עבור הגרף ועבור כל אחד מתתי הגרפים המושרים שלו, אז הגרף נקרא גרף מושלם.
נסמן ב- \alpha (G) את גודל תת-הקבוצה הבלתי תלויה הגדולה ביותר, אז  \chi (G)\geq {\frac {n}{\alpha (G)}}.
הפולינום הכרומטי

מספר הדרכים לצבוע גרף נתון G ב- \lambda  צבעים נתון על ידי הצבה של  \lambda  בפולינום  \chi (G,\lambda ), הקרוי הפולינום הכרומטי של הגרף. פולינום זה, שאותו גילה ג'ורג' בירקהוף ב-1912, מקיים את נוסחת הרקורסיה  \chi (G,\lambda )=\chi (G-e,\lambda )-\chi (G/e,\lambda ), לכל קשת e בגרף, כאשר G-e הוא הגרף ללא הקשת האמורה, ו-G/e הוא הגרף המתקבל מכיווץ הקשת לנקודה.
יישומים

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

משפט ארבעת הצבעים
משפט לובאס-קנזר
| נושאים בתורת הגרפים |
| --- | --- | --- |
| הגדרות | צומת • קשת • דרגה • מסלול • מרחק |  |
| מבנים | גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס |  |
| בניות וטיפוסים | גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך |  |
| תכונות | גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי |  |
הערות שוליים

↑  Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics 164 (1): 51–229.
↑  Lewis, R. A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers, 2015.
↑  G. J. Chaitin, G. J. Chaitin, Register allocation & spilling via graph coloring, Register allocation & spilling via graph coloring, ACM SIGPLAN Notices 17, 1982-06-23, עמ' 98, 98–105, 101 doi: 10.1145/800230.806984, 10.1145/872726.806984
| --- | --- |
בקרת זהויות :  NLI: 987007539706505171  LCCN: sh2004000285
גילוח הראש לנשים ביהדות

גילוח הראש לנשים הוא מנהג של חלק מנשות יהדות אשכנז. לפי מנהג זה, נשים נשואות מגלחות לגמרי את שיער ראשן בכל פעם שהן טובלות לנידתן. ככל הידוע, גילוח כזה התפשט בקרב נשים יהודיות באירופה החל מאמצע המאה ה-18, ופסק בחלק מהמקומות במאה ה-19. נכון למאה ה-21, המנהג נפוץ בקרב החסידים והפרושים (בעיקר אלה ממוצא הונגרי), ואינו נהוג בזרם הליטאי ובזרם הדתי לאומי. מנהג זה מעולם לא היה נהוג בקרב יהודי ארצות האסלאם.