הבדלים בין גרסאות בדף "תורת הגרפים"

נוספו 9 בתים ,  לפני שנתיים
תיקון כיווניות הערת שוליים
מ (←‏קישורים חיצוניים: תיקון קישור)
(תיקון כיווניות הערת שוליים)
[[קובץ:6n-graf.svg|שמאל|ממוזער|גרף בעל 6 צמתים ו-7 קשתות]]
 
המונח '''גרף''' (graph) יכול לתאר מספר מבנים מתמטיים דומים. בדרך כלל, ספר או מאמר העוסק בגרפים יגדיר בתחילתו באיזה מן הבאים הוא עוסק. הגדרה כללית, בלתי פורמלית ופשוטה לגרף היא אוסף של נקודות, המכונות צמתים, וקשתות המחברות ביניהם.
 
שתי הבחנות בולטות בתורת הגרפים הן ההבחנה בין גרף מכוון לגרף בלתי מכוון, ובין גרף סופי לגרף אינסופי.
 
==שימושים של גרפים==
 
ישנם מבנים מתחומים רבים שניתן לייצגם באמצעות גרף, ובעיות מעשיות שונות ניתנות לניסוח (ולפתרון) כבעיות העוסקות בגרפים. דוגמה לשימוש בגרף מכוון הוא המבנה של [[ויקיפדיה]]. ניתן לייצג את ויקיפדיה באמצעות גרף מכוון בו כל אחד מהערכים מיוצג על ידי צומת, וקישור המפנה מערך אחד לאחר מיוצג על ידי קשת שיוצאת מהצומת המייצג את הערך המפנה ונכנסת לצומת המייצג את הערך אליו מפנה ההפנייה.
 
 
==משפחות גרפים==
 
'''משפחת גרפים''' (graph class) היא קבוצת כל הגרפים שלהם תכונה משותפת מסוימת.
 
==הכללות של גרף==
* '''[[מולטיגרף]]''' (multigraph) הוא הכללה של גרף, שבה כל זוג צמתים יכולים להיות מחוברים על ידי יותר מקשת אחת.
 
* '''[[היפרגרף]]''' (hypergraph) הוא הכללה של גרף, שבה כל קשת יכולה לחבר יותר משני צמתים (וכך ניתן לחשוב על כל קשת כעל תת-קבוצה של צמתים).
 
==ייצוג גרפים==
 
לצורך ביצוע פעולות על גרפים, שהם גופים מופשטים, יש צורך להשתמש בייצוג כלשהו שלהם. נהוג להציג גרף באופן ויזואלי, כפי שהוצג בראש ערך זה, כך שכל צומת מוצג באמצעות נקודה, וכל קשת מוצגת באמצעות קו. קשת מכוונת מוצגת באמצעות ראש חץ לכיוון הצומת אליו הקשת נכנסת. ההצגה הוויזואלית היא מאוד נוחה וטבעית לעין [[בן אדם|אנושית]]. צורת הצגה זו אינה פורמלית ולכן קשה להגדיר אלגוריתמים שמשתמשים בה.
 
 
==רקע היסטורי==
מאמרו של [[לאונרד אוילר]] על [[הגשרים של קניגסברג]],{{הערה|[http://www.math.dartmouth.edu/~euler/pages/E053.html E53 -- Solutio problematis ad geometriam situs pertinentis]|שמאל=כן}} שהוצג בשנת 1735, נחשב לתוצאה המשמעותית הראשונה בתורת הגרפים. הוא גם נחשב לאחת מהתוצאות ה[[טופולוגיה|טופולוגיות]] הראשונות ב[[גאומטריה]]; כלומר, הוא לא תלוי במדידות כלשהן.
 
==משפטים חשובים בתורת הגרפים==