הצגת המקור של הדף "גרף (תורת הגרפים)"

[[קובץ:6n-graf.svg|שמאל|ממוזער|150px|גרף לא מכוון בעל 6 קודקודים ו־7 קשתות]]
[[קובץ:Directed graph.svg|ממוזער|שמאל|150px|גרף מכוון בעל 4 קודקודים ו־5 קשתות]]
ב[[תורת הגרפים]], '''גרף''' הוא ייצוג מופשט של [[קבוצה (מתמטיקה)|קבוצה]] של אובייקטים, כאשר כל זוג אובייקטים בקבוצה עשויים להיות מקושרים זה לזה.

האובייקטים הניתנים לקישור מכונים '''קודקודים''' או '''צמתים''' (באנגלית: vertex), וקבוצת הקודקודים מסומנת באות <math>V</math>.

הקישורים בין הקודקודים מכונים '''צלעות''' או '''קשתות''' (באנגלית: edge), וקבוצת הצלעות מסומנת באות <math>E</math>. מתקיים כי קבוצת הצלעות מקיימת: <math>E \sube V\times V</math>, כלומר: כל צלע היא זוג הקודקודים, אותם היא מקשרת (ללא חשיבות לסדר, נהוג לייצג באמצעות [[קבוצה (מתמטיקה)|קבוצה]]).

גרף, אשר קבוצת הקודקודים שלו היא <math>V</math> וקבוצת הצלעות שלו היא <math>E</math> מסומן באופן הבא: <math>G=(V,E)</math>.

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

==סוגי גרפים==
*{{עוגן|גרף בלתי מכוון|'''גרף בלתי מכוון'''}} ולעיתים בפשטות '''גרף''' הוא קבוצה של צמתים וקבוצה של '''קשתות'''. כל קשת מקשרת בין שני צמתים. באופן פורמלי, גרף בלתי מכוון <math>G</math> מוגדר על ידי <math>(V,E)</math> כאשר <math>V</math> היא קבוצת הצמתים ו־<math>E \subseteq \{\{u,v\} \mid u,v \in V\}</math> היא קבוצת הקשתות. ניתן לראות בגרפים בלתי מכוונים [[מקרה פרטי]] של גרפים מכוונים (בהם עבור כל זוג צמתים <math>u </math> ו־<math>v</math>, הקשתות מ־<math>u </math> ל־<math>v</math> ומ־<math>v</math> ל־<math>u </math> קיימות שתיהן, או חסרות שתיהן).
*{{עוגן|גרף מכוון|'''גרף מכוון'''}} הוא [[קבוצה (מתמטיקה)|קבוצה]] של '''צמתים''' (גם: קודקודים או נקודות) וקבוצה של '''קשתות מכוונות'''. כאשר ישנה משמעות לכיוונה של קשת מכוונת – היא יוצאת מצומת אחד ונכנסת לצומת אחר. באופן פורמלי, גרף מכוון <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>.
**'''{{עוגן|גרף תשתית|גרף תשתית}} של גרף מכוון''' הוא גרף בלתי מכוון, אשר מכיל אותה קבוצת צמתים כמו הגרף המכוון, ומכיל את הקשתות בין זוגות הצמתים אשר היו ביניהם קשתות בגרף המקורי (פורמלית, אם <math>D=(V,E)</math>&#x200E; הוא גרף מכוון אז <math>D' =(V,\{\{u,v\}|(u,v)\in E\})</math> הוא גרף התשתית של <math>D</math>).
*'''גרף מעורב''' הוא קבוצה של צמתים, קבוצה של קשתות מכוונות וקבוצה של קשתות לא מכוונות. כל קשת, מכוונת או לא מכוונת, מקשרת בין שני צמתים.
*'''לולאה''' (גם: '''חוג עצמי''') היא קשת (או קשת מכוונת) שמקשרת צומת עם עצמו.
*{{עוגן|גרף פשוט|'''גרף פשוט'''}} הוא גרף לא מכוון ללא לולאות וללא קשתות מקבילות.
*{{עוגן|גרף סופי|'''גרף סופי'''}} הוא גרף ש[[קבוצה סופית|קבוצת הצמתים שלו סופית]].
*{{עוגן|גרף אינסופי|'''גרף אינסופי'''}} הוא גרף ש[[קבוצה אינסופית|קבוצת הצמתים שלו היא אינסופית]].
*'''[[גרף ממושקל]]''' הוא גרף שבו לכל קשת יש ערך, לרוב מספרי, המכונה '''משקל'''. באופן פורמלי, גרף ממושקל בלתי מכוון הוא שלשה <math>(V,E,w)</math>, כאשר <math>V</math> ו־<math>E</math> מוגדרים כמקודם, ו־<math>w</math> היא [[פונקציה|פונקציית]] המשקל מ־<math>E</math> לקבוצה כלשהי (למשל <math>\mathbb{R}</math>).
*'''גרף בלתי מתויג''' הוא גרף שבו לא ניתן להבחין בין הצמתים. כלומר, אין אף מזהה ייחודי (כגון שם או מספר) לצומת בגרף.

==תת־גרף==
'''תת־גרף''' <math>G'=\left(V', E'\right)</math> של גרף <math>G=\left(V, E\right)</math> הוא גרף המורכב משתי תתי־קבוצות של צומתי וקשתות G, דהיינו: <math>V'\subseteq V</math> וכן <math>E'\subseteq E</math> כך שהקשתות <math>E'</math> נפרשות על ידי <math>V'</math>.

או במילים אחרות: אם <math>G=\left(V, E\right)</math> ו־<math>H=\left(W, F\right)</math> הם שני גרפים, אזי <math>H</math> הוא תת־גרף של <math>G</math> אם: <math>W\subseteq V</math> וגם <math>F\subseteq E</math>.

תת־גרף <math>H</math> של גרף <math>G</math> הוא '''תת־גרף מושרה''' אם לכל זוג של צמתים <math>x</math> ו־<math>y</math> ב־<math>H</math>, {{כ}}<math>xy</math> היא קשת של <math>H</math> [[אם ורק אם]] היא קשת של <math>G</math>. במילים אחרות, <math>H</math> הוא תת־גרף מושרה של <math>G</math> אם הוא מכיל את כל הקשתות של <math>G</math> המתאימות לצמתים של <math>H</math> ולא מכיל אף קשת נוספת.

== ראו גם ==
*[[מעגל (תורת הגרפים)|גרף מעגל]]
*[[מבנה נתונים]]

==קישורים חיצוניים==
{{מיזמים|ויקיספר=מבני_נתונים_ואלגוריתמים_-_מחברת_קורס|שם ויקיספר=מבני נתונים ואלגוריתמים - מחברת קורס}}
* {{MathWorld}}

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

== הערות שוליים ==
{{הערות שוליים}}
[[קטגוריה:תורת הגרפים]]