Loading AI tools
ענף במתמטיקה מוויקיפדיה, האנציקלופדיה החופשית
תורת הגרפים היא ענף של המתמטיקה העוסק בתכונותיהם של גרפים. גרפים יכולים לייצג מבנים מופשטים בתחומים רבים ומגוונים, ולכן אלגוריתמים לטיפול בגרפים הם נושא מרכזי במדעי המחשב. דוגמה לשימוש בתורת הגרפים, בתחום שאינו מתמטי לכאורה, היא ניתוח מערכות חברתיות הנעשה במסגרת ניתוח רשתות חברתיות. בפשטות, גרף מייצג קבוצת אובייקטים וקשרים ביניהם. לפעמים מחשיבים את תורת הגרפים כענף של מתמטיקה בדידה.
המונח גרף (graph) יכול לתאר מספר מבנים מתמטיים דומים. בדרך כלל, ספר או מאמר העוסק בגרפים יגדיר בתחילתו באיזה מן הבאים הוא עוסק. הגדרה כללית, בלתי פורמלית ופשוטה לגרף היא אוסף של נקודות, המכונות צמתים, וקשתות המחברות ביניהם.
שתי הבחנות בולטות בתורת הגרפים הן ההבחנה בין גרף מכוון לגרף בלתי מכוון, ובין גרף סופי לגרף אינסופי.
גרף מכוון (directed graph, digraph) הוא קבוצה של צמתים (נקראים גם נקודות, קודקודים, nodes, vertices) וקבוצה של קשתות מכוונות (directed edges, arcs). כאשר ישנה משמעות לכיוונה של קשת מכוונת – היא יוצאת מצומת אחד ונכנסת לצומת אחר. באופן פורמלי, גרף מכוון מוגדר על ידי כאשר היא קבוצת הצמתים ו- היא קבוצת הקשתות. קשת יוצאת מ- ונכנסת ל-.
גרף בלתי מכוון (undirected graph), ולעיתים בפשטות גרף הוא קבוצה של צמתים וקבוצה של קשתות (edges). כל קשת מקשרת בין שני צמתים. באופן פורמלי, גרף בלתי מכוון מוגדר על ידי כאשר היא קבוצת הצמתים ו- היא קבוצת הקשתות. ניתן לראות בגרפים בלתי מכוונים מקרה פרטי של גרפים מכוונים, בהם עבור כל זוג צמתים u ו-v, הקשתות מ-u ל-v ומ-v ל-u קיימות שתיהן, או חסרות שתיהן.
גרף תשתית של גרף מכוון הוא גרף לא מכוון, אשר מכיל אותה קבוצת צמתים כמו הגרף המכוון, ומכיל את הקשתות בין זוגות הצמתים אשר היו ביניהם קשתות בגרף המקורי. אם הוא גרף מכוון אז הוא גרף התשתית של .
גרף סופי (finite graph) הוא גרף שקבוצת הצמתים שלו סופית. גרף אינסופי (infinite graph) הוא גרף שקבוצת הצמתים שלו היא אינסופית.
ישנם מבנים מתחומים רבים שניתן לייצגם באמצעות גרף, ובעיות מעשיות שונות ניתנות לניסוח (ולפתרון) כבעיות העוסקות בגרפים. דוגמה לשימוש בגרף מכוון הוא המבנה של ויקיפדיה. ניתן לייצג את ויקיפדיה באמצעות גרף מכוון בו כל אחד מהערכים מיוצג על ידי צומת, וקישור המפנה מערך אחד לאחר מיוצג על ידי קשת שיוצאת מהצומת המייצג את הערך המפנה ונכנסת לצומת המייצג את הערך אליו מפנה ההפנייה.
דוגמה לשימוש בגרף בלתי מכוון ממושקל היא רשת כבישים. כל עיר מיוצגת על ידי צומת, כל כביש בין-עירוני על ידי קשת, ואורכו של כל כביש הוא משקל הקשת המתאימה.
ניתוח רשתות חברתיות, שהוזכר בפתיחה, הוא דוגמה לשימוש בגרף מעורב וממושקל.
באופן כללי, גרפים טובים לייצוג מבנה שבו קיימים מספר אובייקטים המקושרים ביניהם. הגרף מייצג את האובייקטים באמצעות הצמתים ואת הקשרים ביניהם באמצעות הקשתות. כאשר לקשרים יש כיוון או ערך, הם מיוצגים על ידי כיוון הקשת או משקלה.
משפחת גרפים (graph class) היא קבוצת כל הגרפים שלהם תכונה משותפת מסוימת.
דוגמאות:
ניתן להגדיר משפחת גרפים בעבור כל תכונה, ואפילו לפי רשימה פרטנית של גרפים שבמשפחה או של גרפים שאינם במשפחה.
לצורך ביצוע פעולות על גרפים, שהם גופים מופשטים, יש צורך להשתמש בייצוג כלשהו שלהם. נהוג להציג גרף באופן ויזואלי, כפי שהוצג בראש ערך זה, כך שכל צומת מוצג באמצעות נקודה, וכל קשת מוצגת באמצעות קו. קשת מכוונת מוצגת באמצעות ראש חץ לכיוון הצומת אליו הקשת נכנסת. ההצגה הוויזואלית היא מאוד נוחה וטבעית לעין אנושית. צורת הצגה זו אינה פורמלית ולכן קשה להגדיר אלגוריתמים שמשתמשים בה.
גרף, כפי שהוגדר לעיל, הוא קבוצה של צמתים וקבוצה של קשתות ביניהם. שתי הקבוצות הללו יחדיו מייצגות את הגרף. הייצוג הטריוויאלי הזה אינו מקובל, מכיוון שהוא אינו מקל על ביצוע פעולות על הגרף. סיבוכיות זמן הריצה ומקום האחסון של אלגוריתם הפועל על גרפים תלויה ביעילות יצוג הגרפים והפעולות עליהם. לכן, יש חשיבות לבחירת יצוג גרפים לפי אופי האלגוריתם, כלומר לפי סוג הגרפים עליהם הוא פועל ולפי הפעולות על הגרפים אותם הוא מבצע.
מטריצת סמיכויות (adjacency matrix) היא שיטת יצוג מקובלת לגרף כללי. בשיטה זו, הגרף מיוצג כמטריצה בגודל כאשר כל צומת מיוצג על ידי שורה ועל ידי עמודה. תא במטריצה מכיל "1" אם ישנה בגרף קשת מהצומת של לצומת של , ו-"0" אחרת. היתרון של מטריצת סמיכויות הוא שניתן לענות על שאלות מסוג "האם u הוא שכן של v?" בזמן קבוע. במטריצת סמיכויות, כל זוג צמתים מיוצג על ידי סיבית בודדות במטריצה, בין אם קיימת קשת ביניהם ובין אם הקשת אינה קיימת. לכן, המקום שנדרש לייצוג כזה הוא כריבוע מספר הצמתים, כלומר סיביות. גודל מקום זה הוא אופטימלי עבור גרף כללי וגרף אקראי, אבל עלול להיות גבוה עבור גרף דליל.
רשימת סמיכויות (adjacency list) גם היא שיטת יצוג מקובלת לגרף כללי. בשיטה זו, הגרף מיוצג כקבוצה של רשימות מקושרות של השכנים של כל צומת. היתרון של רשימות סמיכויות הוא תשובה בזמן קבוע על פעולות מסוג "הבא את רשימת השכנים של v", "הבא שכן כלשהו של v" ו"הבא את השכן הבא של v". לצורך כך דרושים ראשי רשימות ו- צמתים, כלומר סה"כ מקום, פחות מזה של מטריצת סמיכויות עבור גרף שאינו צפוף.
את שתי השיטות הנ"ל ניתן להכליל גם עבור גרפים בלתי מכוונים וגרפים ממושקלים.
פרט לשתי השיטות שהוזכרו, המקובלת לגרף כללי, קיימות שיטות יצוג שונות עבור גרפים מסוימים. כאשר ידוע לנו שהגרפים עליהם האלגוריתם פועל שייכים למשפחת גרפים מסוימת, כלומר מקיימים תכונה מסוימת, ניתן למצוא יצוג שיינצל את התכונה כדי לקבל זמן ריצה יעיל עבור פעולות הקשורות בה, או נפח אחסון נמוך. למשל, עץ ניתן לייצוג על ידי קביעת צומת כלשהו לשורש, ואחסון מצביע לאב (הצומת השכן שהמסלול היחיד לשורש עובר דרכו) עבור כל צומת אחר. יצוג כזה של עץ דורש מקום.
מאמרו של לאונרד אוילר על הגשרים של קניגסברג,[1] שהוצג בשנת 1735, נחשב לתוצאה המשמעותית הראשונה בתורת הגרפים. הוא גם נחשב לאחת מהתוצאות הטופולוגיות הראשונות בגאומטריה; כלומר, הוא לא תלוי במדידות כלשהן.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.