stanford-oval/wikipedia huggingface dataset:
תחנת הרכבת התחתית ווטרלו
מתחם תחבורה מרכזי

מעל לתחנת התחתית נמצאת תחנת הרכבת ווטרלו, תחנה חשובה המשמשת כתחנת-קצה מרכזית עבור לונדון. עד ל-13 בנובמבר 2007 שימשה התחנה כמסוף בינלאומי לרכבות היוצאות מאנגליה לכיוון יבשת אירופה, לערים מרכזיות כבריסל, ליל ופריז. כיום, יוצא שירות הרכבות הבינלאומי מתחנת סיינט פנקראס.
בנוסף, קיימת תחנת אוטובוס מרכזית לצד תחנת הרכבת.
תחנת ווטרלו התחתית היא אחת מן התחנות העמוסות ברכבת התחתית של לונדון, מאחר שהתחנה משמשת כנקודת מפגש ל-4 קווים שונים, המאפשרים לנוסעים להחליף ביניהם. בשנת 2006 נרשמו כ-68.5 מיליון כניסות ויציאות בתחנה. בתחנה זו, יש 23 דרגנועים ובכך היא שיאנית במספר הדרגנועים הקיים, הגבוה ביותר מבכל תחנת תחתית אחרת.
ראו גם

היסטוריה של הרכבת התחתית של לונדון
הערות שוליים

↑  the old vic tunnels
↑  "סטטיסטיקות באתר Tfl- גוף התחבורה של לונדון". tfl.gov.uk.
תנועת העבודה הציונית העולמית

תנועת העבודה הציונית העולמית (תע"צ) היא המסגרת העולמית של ציונים בעלי עמדות סוציאל-דמוקרטיות, וכוללת את מפלגת העבודה הישראלית וסניפים של התנועה בחו"ל.
תע"צ פועלת במוסדות הלאומיים, כדוגמת הסוכנות היהודית, ההסתדרות הציונית העולמית וקרן קיימת לישראל. התנועה נוסדה בעקבות הקמתה של מפלגת העבודה הישראלית בינואר 1968, ומאז הקמתה פעלה בקרב הקהילות היהודיות בארצות העולם המערבי, כשהיא נשענת על יוצאי התנועות הסוציאליסטיות ממזרח אירופה ועל פעילים יהודים באיגודים המקצועיים. תע"צ כוללת בתוכה את צעירי התנועה.
ב-15 בפברואר 1978 נבחר יגאל אלון לתפקיד יושב ראש התנועה.
בראש תע"צ עמד יגאל צחור והמזכ"ל הוא מישל חלימי. עם בכירי התנועה נמנים יו"ר קרן קיימת לישראל, גזבר הסוכנות היהודית, ארבעה חברי הנהלת הסוכנות היהודית ובכירים בגופים נוספים.
צעירי תנועת העבודה הציונית העולמית הם המסגרת העולמית של הצעירים והתנועות, הכלולות בתנועת העבודה הציונית העולמית, בשיתוף תנועת "המחנות העולים" ותנועת "הבונים דרור" העולמית. התנועה הצעירה, שהחלה את פעילותה מחדש בשנת 2009, כוללת צעירים יהודים בישראל ובעולם בגילאי 18-35 אשר מזדהים עם ערכי הציונות החברתית-סביבתית. מבנה צעירי התנועה מורכב מהמזכירות, מהוועידה העולמית ומהצוותים הגאוגרפיים, המהווים גשר בין ישראל לבין צעירים בקהילות ברחבי העולם. יו"ר צעירי תע"צ כיום הוא יוני יצחק.
הערות שוליים

↑  אודי מנור, יגאל אלון – ביוגרפיה פוליטית, עמ' 387.
תורת לנדאו

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

פרמטר סדר הוא מדד המייצג את מידת הסדר באזור מעבר הפאזה. במערכת בה יש סימטריה ביחס לפרמטר הסדר ערכו של פרמטר הסדר נע בין אפס עבור הפאזה המתקבלת בטמפרטורות גבוהות (בהן אי הסדר גדול יותר, אין הכרח לטמפרטורה, אלא כל שני פרמטרים, שדה מגנטי, לחץ וכדומה) לערך שונה מאפס בפאזה המתקבלת בטמפרטורות נמוכות. ערכו של פרמטר הסדר יכול להיות מיוצג בדרכים שונות ביניהן סקלר, מספר מרוכב, וקטור וטנזור, כאשר ייצוג פרמטר הסדר תלוי במערכת המדוברת ובסוג מעבר הפאזה. דוגמה מייצגת עבור פרמטר הסדר היא המגנטיזציה במערכת פרומגנטית בסמוך לטמפרטורת קירי.
לנדאו הציע שכאשר מערכת מסוימת נמצאת בטמפרטורה הקרובה לטמפרטורה הקריטית ניתן יהיה לתאר את האנרגיה החופשית של המערכת כטור טיילור בפרמטר הסדר, כאשר בהיעדר שדה מסדר (כלומר כאשר המערכת סימטרית ביחס לפרמטר הסדר) הטור יכלול רק חזקות זוגיות של פרמטר הסדר ומכיוון שקרוב לטמפרטורה הקריטית פרמטר הסדר קטן, ניתן להסתכל רק על האיברים הראשונים בטור:
G(m,t)=a(t)+{\frac {b(t)}{2}}m^{2}+{\frac {c(t)}{4}}m^{4}+{\frac {d(t)}{6}}m^{6}
כאשר  t={\frac {T-T_{c}}{T_{c}}},  |t|<<1,  G היא האנרגיה החופשית,  m הוא פרמטר הסדר,  T היא הטמפרטורה,  T_{c} היא הטמפרטורה הקריטית ו- a,b,c,d הם פרמטרים התלויים במערכת. במצב של שיווי משקל האנרגיה החופשית מינימלית ולכן נוכל למצוא את  m(t) על ידי מציאת נקודות המינימום של המשוואה.
התאוריה הבסיסית ופרמטר הסדר > מעבר פאזה רציף

עבור מודל זה ההנחה של לנדאו הייתה שערכו של  c(t) הוא קבוע חיובי וש-  b(t) פרופורציונלי ל- t, כלומר:
b=b_{0}t\qquad c=c_{o}
כאשר  b_{0} ו- c_{0} קבועים חיוביים.
בעקבות הנחה זו מתקבל כי המינימום הגלובלי של האנרגיה החופשית מתקבל בנקודות (כאשר האיבר  {\frac {d(t)}{6}}m^{6} מוזנח):
|m|={\begin{cases}0&t\geq 0\\({\frac {b_{0}|t|}{c_{0}}})^{1/2}&t<0\end{cases}}
ניתן לראות מהתוצאה הנ"ל כי פרמטר הסדר משתנה בצורה רציפה אך לא גזירה בטמפרטורה הקריטית ולכן מודל זה מתאר מעבר פאזה מסדר שני. מסקנה נוספת המתקבלת מהפיתוח הנ"ל היא כי האקספוננט הקריטי הוא  1/2 ללא תלות בפרמטרים  c_{0},b_{0}, כלומר ישנה אוניברסליות המצביעה על כך שישנה מחלקה של מערכות בעלות אותה התנהגות קריטית למרות ההבדלים המבניים ביניהן. יש לשים לב כי תורת לנדאו מניחה כי ישנו רק רכיב אחד לפרמטר הסדר וכן מתעלמת ממספר הממדים של המערכת ולכן נותנת תיאור של מספר מערכות מצומצם יחסית.
ישנם תופעות רבות (שאינן מתחום הטמפרטורה) אשר מתבצעות בהן מעברי פאזה מסדר שני. כאשר אנו מתעסקים בחומרים, כלל האנרגיות רציפות, כאשר מתקבלת סבירת סימטרייה תחת מעוות (החומר עדיין מוצק) תתקבל שינוי בפונקציית האנרגיה ויתקבל מעבר פאזה.
התאוריה הבסיסית ופרמטר הסדר > מעבר פאזה לא רציף

מעבר פאזה מסוג שונה מתקבל כאשר ההנחה היא כי  c(t) משנה סימן כאשר שאר האיברים חיוביים (מניחים כי  b הוא פונקציה יורדת בטמפרטורה אך הוא מתאפס בטמפרטורה נמוכה יותר מ-  c). עבור מקרה זה מקבלים פרמטר סדר ספונטני:
m_{\pm }^{2}={\frac {-3c\pm 3{\sqrt {c^{2}-16bd/3}}}{4d}}
כאשר על מנת שהפתרון יהיה אפשרי נדרש כי  c<0 וכי  c^{2}>{\frac {16bd}{3}}, כלומר הטמפרטורה הקריטית מתקבלת מהתנאי:
c^{2}(T_{c})={\frac {16b(T_{c})d(T_{c})}{3}}\qquad c(T_{c})<0
עבור ערך זה נקבל כי מעט מתחת לטמפרטורה הקריטית:
m_{\pm }^{2}={\frac {-3c(T_{c})}{4d}}\neq 0
כלומר ישנה קפיצה פתאומית בפרמטר הסדר מאפס לערך סופי, מעבר פאזה מסוג זה נקרא מעבר פאזה לא רציף וזהו מעבר פאזה מסדר ראשון.
קשר לא מקומי

כאשר ישנן תנודות מרחביות בשדה המגנטי תורת לנדאו הסטנדרטית אינה מספיקה והיא מוכללת לתאוריה כללית יותר בעזרת מתן תלות מרחבית לפרמטר הסדר, כלומר  m\to m(r). במצב זה מתייחסים לפרמטר הסדר כפונקציה חלקה במרחב, ניתן לעשות זאת מכיוון שלרוב לתנודות קצרות תווך ישנה עלות אנרגטית גבוהה, ולכן הן נדירות ביותר. המסקנה היא כי השתנות פרמטר הסדר נגרמת בעיקר מקשרים לא מקומיים. בהקבלה לתורה הסטנדרטית האנרגיה החופשית היא:
G(m({\boldsymbol {r}}),T)=\int {\left\{-h({\boldsymbol {r}})m({\boldsymbol {r}})+a(T)+{\frac {b(T)}{2}}m^{2}({\boldsymbol {r}})+{\frac {c(T)}{4}}m^{4}({\boldsymbol {r}})+...+{\frac {f}{2}}[\nabla m({\boldsymbol {r}})]^{2}\right\}}d{\boldsymbol {r}}
כאשר  h({\boldsymbol {r}}) הוא שדה מגנטי חיצוני וכעת נוסף איבר הגרדיאנט של פרמטר הסדר הלוקח בחשבון את הגדלת האנרגיה החופשית בעקבות ההשתנות המרחבית של פרמטר הסדר. כדי למצוא את  m({\boldsymbol {r}}) הממזער את האנרגיה החופשית יש לדרוש שהנגזרת הפונקציונלית של  G תקיים  \delta G=0 לכן נקבל:
\delta G(m({\boldsymbol {r}}),T)=\int {\left\{-h({\boldsymbol {r}})\delta m({\boldsymbol {r}})+b(T)m({\boldsymbol {r}})\delta m({\boldsymbol {r}})+c(T)m^{3}({\boldsymbol {r}})\delta m({\boldsymbol {r}})+...+f\nabla m({\boldsymbol {r}})\nabla \delta m({\boldsymbol {r}})\right\}}d{\boldsymbol {r}}
בעזרת אינטגרציה בחלקים ושימוש בכך ש- \delta m({\boldsymbol {r}})=0 בשפת המערכת מתקבלת המשוואה:
\delta G(m({\boldsymbol {r}}),T)=\int {\left\{-h({\boldsymbol {r}})\delta m({\boldsymbol {r}})+b(T)m({\boldsymbol {r}})\delta m({\boldsymbol {r}})+c(T)m^{3}({\boldsymbol {r}})\delta m({\boldsymbol {r}})+...-f\nabla ^{2}m({\boldsymbol {r}})\delta m({\boldsymbol {r}})\right\}}d{\boldsymbol {r}}
מכיוון שמשוואה זו נכונה לכל  \delta m({\boldsymbol {r}}) נקבל מהתנאי על הנגזרת הפונקציונלית של האנרגיה החופשית את משוואת גינזבורג-לנדאו:
h({\boldsymbol {r}})=b(T)m({\boldsymbol {r}})+c(T)m^{3}({\boldsymbol {r}})+...-f\nabla ^{2}m({\boldsymbol {r}})
כאשר עבור  h(r)=0 נקבל כצפוי את תאוריית לנדאו הסטנדרטית.
פרמטר סדר בעל מספר פרמטרים

במקרים רבים פרמטר סדר סקלרי אינו מספיק כדי לתאר מערכת פיזיקלית. למשל, עבור נוֹזְלוּת-על של הליום-4 וכן עבור מוליכי על נדרש פרמטר סדר בעל שני רכיבים (המיוצג על ידי מספר מרוכב), מודל פוץ (potts model) מסדר  q דורש  q-1 רכיבים ובגבישים נוזליים פרמטר הסדר מיוצג על ידי טנזור סימטרי וחסר עקבה.
בדומה למקרה הסקלרי, הדרישה במקרה זה היא כי האנרגיה החופשית בהיעדר שדה מסדר תשמור על הסימטריה של הבעיה המקורית. כאשר פרמטר הסדר הוא וקטורי וישנה סימטריה ביחס לכיוון הווקטור, נדרש שהאנרגיה החופשית תהיה תלויה רק בגודלו של הווקטור. כלומר ניתן להציב:
m^{2}=\sum _{k=1}^{N}m_{k}^{2}
כאשר  m_{k} הוא הרכיב ה- k של פרמטר הסדר ו- N הוא מספר הרכיבים. עבור פרמטר סדר טנזורי  Q_{\alpha \beta } האנרגיה החופשית תתואר על ידי גדלים הנשמרים תחת טרנספורמציות למערכת הצירים. מכיוון שעקבה של מטריצה נשמרת תחת טרנספורמציות כאלו, נהוג לתאר את האנרגיה החופשית באמצעות:
Tr(Q^{2})=\sum _{\alpha ,\beta }Q_{\alpha \beta }Q_{\beta \alpha }
Tr(Q^{3})=\sum _{\alpha ,\beta ,\gamma }Q_{\alpha \beta }Q_{\beta \gamma }Q_{\gamma \alpha }
עבור פרמטר סדר בעל מספר פרמטרים, מציאת מצב שיווי המשקל תתבצע על ידי מינימיזציה של האנרגיה החופשית ביחס לכל הפרמטרים של פרמטר הסדר.
ראו גם

לב לנדאו
מעבר פאזה
תרמודינמיקה
אקספוננט קריטי
מרחב פאזה
פרומגנטיות
נוזל-על
מוליכות-על
גביש נוזלי
תורת שדה ממוצע
לקריאה נוספת

Landau L.D.(1969). Collected Papers Nauka, Moscow
Michael C. Cross, Landau theory of second order phase transitions, (Caltech statistical mechanics lecture notes)
Yukhnovskii, I R, Phase Transitions of the Second Order - Collective Variables Method, World Scientific, 1987, ISBN 9971-5-0087-6
Landau L.D., Zh. Eksp. Teor. Fiz. 7, pp. 19–32 (1937)
Plischke Michael, Birger Bergersen(1994). Equilibrium statistical physics. 2nd ed. Singapore, World Scientific.
R.K Pathria, Paul D. Beale (1972). Statistical Mechanics 3rd Ed., oxford University Press
Chaikin P. M., Lubensky T. C.(1995). Principles of condensed matter physics, Cambridge University Press
הערות שוליים

↑  R.K Pathria & Paul D. Beale, Statistical Mechanics 3rd Ed. ch 12.9
1 2  Plischke ,Michael, Birger Bergersen(1994). Equilibrium statistical physics. 2nd ed. Singapore, World Scientific p.107-109.
האנרגיה החופשית כפונקציה של פרמטר הסדר עבור טמפרטורות שונות במעבר פאזה רציף
האנרגיה החופשית כפונקציה של פרמטר הסדר עבור טמפרטורות שונות במעבר פאזה לא רציף
תחנת הרכבת התחתית הולבורן

| --- | --- |

 מידע על הבנייה
 חנוכת התחנה:  1906
 אדריכל:  לסלי גרין, צ'ארלס הולדן 
 מיקום
 מיקום:  הולבורן, קמדן, לונדון, הממלכה המאוחדת הממלכה המאוחדת
 מדינה:  הממלכה המאוחדת הממלכה המאוחדת
 אזור נסיעה:  אזור 1
 קואורדינטות:  51°31′02″N 0°07′12″W﻿ / ﻿51.517222°N 0.12°W﻿ / 51.517222; -0.12
 תחנות סמוכות:  Chancery Lane tube station, Covent Garden tube station, Tottenham Court Road station, Russell Square tube station 
 מידע על התחנה
 סוג התחנה:  רכבת תחתית
 קווים העוברים בתחנה:  קו סנטרל קו פיקדילי
 נוסעים בשנה:  30.098 מיליון (2009)
  (למפת לונדון מוגדלת) קנט סארי ברקשייר בקינגהאם הרטפורדשייר אסקסתחנת הרכבת התחתית הולבורן(למפת לונדון רגילה) קנט סארי בר. בקי. הרטפורדשייר אסקסתחנת הרכבת התחתית הולבורן(למפת קמדן רגילה) המוזיאון הבריטי בארנט הארינגיי איזלינגטון הסיטי של וסטמינסטר תחנת הרכבת התחתית הולבורן(למפת קמדן מוגדלת) המוזיאון הבריטי בארנט הארינגיי איזלינגטון הסיטי של וסטמינסטר תחנת הרכבת התחתית הולבורן
 
תחנת הרכבת התחתית הולבורן (באנגלית: Holborn tube station) היא תחנה ברשת הרכבת התחתית של לונדון. התחנה ממוקמת בהולבורן במרכז לונדון ועוברים בה קווי סנטרל ופיקדילי.
היסטוריה > הקמת התחנה ותכנונה בשנת 1906

התחנה הוקמה ב-15 בדצמבר 1906 על ידי החברה "קו הרכבת הצפוני של פיקדילי ברומפטון" (Great Northern, Piccadilly & Brompton Railway), חברה אשר מפעילה את קו פיקדילי. במקור נקראה התחנה בשם "הולבורן (קינגסווי)" אך שם זה קוצר בשנות השישים ל"הולבורן".
התחנה תוכננה כך שתקיים מפגש עם מנהרות חברת "קו הרכבת המרכז-לונדוני" (Central London Railway), אשר מפעילה את קו סנטרל, הפעיל משנת 1900. התחנה הקרובה ביותר למקום, תחנת "בריטיש מיוזיאום" נמצאה במרחק של 250 מטרים מערבה מתחנת הולבורן.
למרות הבנייה וההפעלה של קו הרכבת נפרדות, באותם ימים היה מקובל שמספר של חברות רכבת יתכננו במשותף תחנות, אשר ישרתו מספר רכבות של מספר חברות במקביל, זאת על מנת להקל על תפעולן. אך על אף שיתופי הפעולה שהתקיימו במשך השנים עם "חברת הקו המרכז-לונדוני" בתחנות "אוקספורד סירקוס" ו"טוטנהאם קורט רואד", מיקום תחנת הולבורן לצד תחנת "בריטיש מיוזיאום" גרמה לכך שבשנת 1933 הופסק השימוש בתחנה.
על פי התכנון המקורי של "קו הרכבת הצפוני של פיקדילי ברומפטון", התחנה כללה ארבעה רציפים, שני רציפים יועדו לפעילות השוטפת של הקו ואילו השניים האחרים שירתו את שלוחת אלדוויץ', שהייתה מורכבת מתחנה אחת בשם "אלדוויץ'", שהתחברה לקו דרך תחנת הולבורן. מאחד מהרציפים יצאה תנועה לכיוון צפון ורציף אחר שימש תחנה סופית לחניית רכבות.
בניגוד לתחנות אחרות שתכנן האדריכל לסלי גרין, חזית תחנת הרכבת נבנתה מאבן במקום מטרה קוטה, כמקובל.
היסטוריה > חידוש התחנה בשנת 1933

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

ב-9 ביולי 1980 התרחשה תאונה בתחנת הולבורן כאשר שתי רכבות התנגשו אחת בשנייה וגרמו לפציעת מפעיל אחת הרכבות. חקירת התאונה העלתה שהאחראי לתאונה הוא מפעיל הרכבת הפוגעת אשר לא שלט ברכבת במידה הנחוצה.
ראו גם

היסטוריה של הרכבת התחתית של לונדון
תשעת הקדושים

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

טדסה תמרת, כנסייה ומדינה באתיופיה: 1270 - 1527, ISBN 0-19-821671-8 (אנגלית).
תורת הגרפים

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

המונח גרף (graph) יכול לתאר מספר מבנים מתמטיים דומים. בדרך כלל, ספר או מאמר העוסק בגרפים יגדיר בתחילתו באיזה מן הבאים הוא עוסק. הגדרה כללית, בלתי פורמלית ופשוטה לגרף היא אוסף של נקודות, המכונות צמתים, וקשתות המחברות ביניהם.
שתי הבחנות בולטות בתורת הגרפים הן ההבחנה בין גרף מכוון לגרף בלתי מכוון, ובין גרף סופי לגרף אינסופי.
גרף מכוון (directed graph, digraph) הוא קבוצה של צמתים (נקראים גם נקודות, קודקודים, nodes, vertices) וקבוצה של קשתות מכוונות (directed edges, arcs). כאשר ישנה משמעות לכיוונה של קשת מכוונת – היא יוצאת מצומת אחד ונכנסת לצומת אחר. באופן פורמלי, גרף מכוון  \ D מוגדר על ידי  \ (V,E) כאשר  \ V היא קבוצת הצמתים ו- \ E\subseteq V\times V היא קבוצת הקשתות. קשת  \ e=(u,v)\in E יוצאת מ- \ u ונכנסת ל- \ v.
גרף בלתי מכוון (undirected graph), ולעיתים בפשטות גרף הוא קבוצה של צמתים וקבוצה של קשתות (edges). כל קשת מקשרת בין שני צמתים. באופן פורמלי, גרף בלתי מכוון  \ G מוגדר על ידי  \ (V,E) כאשר  \ V היא קבוצת הצמתים ו- \ E\subseteq \{uv\mid u,v\in V\} היא קבוצת הקשתות. ניתן לראות בגרפים בלתי מכוונים מקרה פרטי של גרפים מכוונים, בהם עבור כל זוג צמתים u ו-v, הקשתות מ-u ל-v ומ-v ל-u קיימות שתיהן, או חסרות שתיהן.
גרף תשתית של גרף מכוון הוא גרף לא מכוון, אשר מכיל אותה קבוצת צמתים כמו הגרף המכוון, ומכיל את הקשתות בין זוגות הצמתים אשר היו ביניהם קשתות בגרף המקורי. אם  G=(V,E)‎ הוא גרף מכוון אז  G'=(V,\{\{u,v\}|(u,v)\in E\}) הוא גרף התשתית של  G.
גרף סופי (finite graph) הוא גרף שקבוצת הצמתים שלו סופית. גרף אינסופי (infinite graph) הוא גרף שקבוצת הצמתים שלו היא אינסופית.
שימושים של גרפים

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

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

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

לצורך ביצוע פעולות על גרפים, שהם גופים מופשטים, יש צורך להשתמש בייצוג כלשהו שלהם. נהוג להציג גרף באופן ויזואלי, כפי שהוצג בראש ערך זה, כך שכל צומת מוצג באמצעות נקודה, וכל קשת מוצגת באמצעות קו. קשת מכוונת מוצגת באמצעות ראש חץ לכיוון הצומת אליו הקשת נכנסת. ההצגה הוויזואלית היא מאוד נוחה וטבעית לעין אנושית. צורת הצגה זו אינה פורמלית ולכן קשה להגדיר אלגוריתמים שמשתמשים בה.
גרף, כפי שהוגדר לעיל, הוא קבוצה של צמתים וקבוצה של קשתות ביניהם. שתי הקבוצות הללו יחדיו מייצגות את הגרף. הייצוג הטריוויאלי הזה אינו מקובל, מכיוון שהוא אינו מקל על ביצוע פעולות על הגרף. סיבוכיות זמן הריצה ומקום האחסון של אלגוריתם הפועל על גרפים תלויה ביעילות יצוג הגרפים והפעולות עליהם. לכן, יש חשיבות לבחירת יצוג גרפים לפי אופי האלגוריתם, כלומר לפי סוג הגרפים עליהם הוא פועל ולפי הפעולות על הגרפים אותם הוא מבצע.
מטריצת סמיכויות (adjacency matrix) היא שיטת יצוג מקובלת לגרף כללי. בשיטה זו, הגרף מיוצג כמטריצה בגודל  \ |V|\times |V| כאשר כל צומת מיוצג על ידי שורה ועל ידי עמודה. תא  \ (i,j) במטריצה מכיל "1" אם ישנה בגרף קשת מהצומת של  i לצומת של  j, ו-"0" אחרת. היתרון של מטריצת סמיכויות הוא שניתן לענות על שאלות מסוג "האם u הוא שכן של v?" בזמן קבוע. במטריצת סמיכויות, כל זוג צמתים מיוצג על ידי סיבית בודדות במטריצה, בין אם קיימת קשת ביניהם ובין אם הקשת אינה קיימת. לכן, המקום שנדרש לייצוג כזה הוא כריבוע מספר הצמתים, כלומר  \ \Theta (|V|^{2}) סיביות. גודל מקום זה הוא אופטימלי עבור גרף כללי וגרף אקראי, אבל עלול להיות גבוה עבור גרף דליל.
רשימת סמיכויות (adjacency list) גם היא שיטת יצוג מקובלת לגרף כללי. בשיטה זו, הגרף מיוצג כקבוצה של רשימות מקושרות של השכנים של כל צומת. היתרון של רשימות סמיכויות הוא תשובה בזמן קבוע על פעולות מסוג "הבא את רשימת השכנים של v", "הבא שכן כלשהו של v" ו"הבא את השכן הבא של v". לצורך כך דרושים  \ |V| ראשי רשימות ו- \ |E| צמתים, כלומר סה"כ  \ \Theta (|V|+|E|) מקום, פחות מזה של מטריצת סמיכויות עבור גרף שאינו צפוף.
את שתי השיטות הנ"ל ניתן להכליל גם עבור גרפים בלתי מכוונים וגרפים ממושקלים.
פרט לשתי השיטות שהוזכרו, המקובלת לגרף כללי, קיימות שיטות יצוג שונות עבור גרפים מסוימים. כאשר ידוע לנו שהגרפים עליהם האלגוריתם פועל שייכים למשפחת גרפים מסוימת, כלומר מקיימים תכונה מסוימת, ניתן למצוא יצוג שיינצל את התכונה כדי לקבל זמן ריצה יעיל עבור פעולות הקשורות בה, או נפח אחסון נמוך. למשל, עץ ניתן לייצוג על ידי קביעת צומת כלשהו לשורש, ואחסון מצביע לאב (הצומת השכן שהמסלול היחיד לשורש עובר דרכו) עבור כל צומת אחר. יצוג כזה של עץ דורש  \ \Theta (|V|\log |V|) מקום.
רקע היסטורי

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

משפט החתונה של הול
משפט רמזי
נוסחת קיילי – נוסחה לחישוב מספר העצים הפורשים בגרף השלם על n קודקודים מסומנים
בעיות מרכזיות בתורת הגרפים

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

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

↑  E53 -- Solutio problematis ad geometriam situs pertinentis
| נושאים בתורת הגרפים |
| --- | --- | --- |
| הגדרות | צומת • קשת • דרגה • מסלול • מרחק |  |
| מבנים | גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס |  |
| בניות וטיפוסים | גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך |  |
| תכונות | גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי |  |
| תחומים במדעי המחשב |
| --- | --- | --- |
| יסודות מתמטים | לוגיקה מתמטית • תורת הקבוצות • תורת המספרים • תורת הגרפים  • תורת הטיפוסים •  תורת הקטגוריות  • אנליזה נומרית • תורת האינפורמציה |  |
| תורת החישוביות | תורת האוטומטים • תורת הרקורסיה • תורת הסיבוכיות • מחשוב קוונטי |  |
| אלגוריתמים ומבנה נתונים | אנליזה של אלגוריתמים • גאומטריה חישובית |  |
| שפות תכנות ומהדרים | מפרש • פרדיגמת תכנות (תכנות פרוצדורלי • תכנות מונחה עצמים • תכנות פונקציונלי • תכנות לוגי) |  |
| חישוב מבוזר ועיבוד מקבילי | עיבוד מקבילי • מחשוב סריגי • בקרת מקביליות |  |
| הנדסת תוכנה | ניתוח מערכות מידע • עיצוב תוכנה • תכנות מחשבים • שיטות פורמליות • בדיקות תוכנה • מתודולוגיית פיתוח תוכנה |  |
| תקשורת | ניתוב • טופולוגיית רשת • קריפטוגרפיה |  |
| מסד נתונים | מסד נתונים יחסי • SQL • תנועה • אינדקסים • כריית מידע • CAP theorem |  |
| בינה מלאכותית | חשיבה אוטומטית • בלשנות חישובית • ראייה ממוחשבת • עיבוד שפה טבעית • בינה חישובית • מערכת מומחה • למידה חישובית • רובוטיקה |  |
| גרפיקה | הדמיה ממוחשבת • הנפשה ממוחשבת • עיבוד תמונה |  |
| שפות פורמליות | שפה רגולרית • שפה חסרת הקשר • שפה תלוית הקשר • ההיררכיה של חומסקי |  |
| שימושים במדע | ביואינפורמטיקה • מדעים קוגניטיביים • כימיה חישובית • פיזיקה חישובית • אנליזה נומרית |  |
| --- | --- |
בקרת זהויות :  NLI: 987007538432705171  BnF: cb119384413 (data)  GND: 4113782-6  LCCN: sh85056471  NDL: 00562641  NKC: ph126555 
גרף בעל 6 צמתים ו-7 קשתות
תרזה, נסיכת ליכטנשטיין

הנרייטה, נסיכת ליכטנשטיין (בגרמנית: Therese von Liechtenstein,‏ 28 ביולי 1850 - 13 במרץ 1938), הייתה בתו של אלויס השני, נסיך ליכטנשטיין ואשתו של ארנולף, נסיך בוואריה.
ביוגרפיה

תרזה נולדה ב-28 ביולי 1850 בטירת ליכטנשטיין, אוסטריה תחתית, לאלויס השני, נסיך ליכטנשטיין ולפרנציסקה קינסקי, רוזנת וצ'יניץ וטטאו, בתם של פרנץ דה פאולה קינסקי, רוזן וצ'יניץ וטטאו ותרזה, רוזנת ורבנה ופרוידנטל.
ב-12 באפריל 1882 התחתנה תרזה עם בן דודה ארנולף, נסיך בוואריה, בנו של לואיטפולד, הנסיך העוצר של בוואריה ואחיו של לודוויג השלישי, מלך בוואריה, ממנו נולד לה בנה היחיד, היינריך, נסיך בוואריה (1884–1916) שנהרג במלחמת העולם הראשונה.
בשנת 1907 מת בעלה, ובשנת 1916 נהרג בנה במהלך מלחמת העולם הראשונה, וב-13 במרץ 1938 מתה תרזה במינכן.