תורת הגרפים – הבדלי גרסאות

 

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

'''גרף מכוון''' (directed graph, digraph) הוא [[קבוצה (מתמטיקה)|קבוצה]] של '''צמתים''' (נקראים גם נקודות, קודקודים, nodes, vertices) וקבוצה של '''קשתות מכוונות''' (directed edges, arcs). כאשר ישנה משמעות לכיוונה של קשת מכוונת - היא יוצאת מצומת אחד ונכנסת לצומת אחר. באופן פורמלי, גרף מכוון <math>\ D</math> מוגדר על ידי <math>\ (V,E)</math> כאשר <math>\ V</math> היא קבוצת הצמתים ו-<math>\ E \subseteq V \times V</math> היא קבוצת הקשתות. קשת <math>\ e=(u,v)\in E</math> יוצאת מ-<math>\ u </math> ונכנסת ל-<math>\ v</math>.

 

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

 

 

[[חקר רשתות חברתיות]], שהוזכר בפתיחה, הוא דוגמה לשימוש בגרף מעורב וממושקל.

{{תורת הגרפים}}

{{מדעי המחשב}}

 

[[קטגוריה:תורת הגרפים|*]]