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

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

*{{עוגן|גרף מכוון|'''גרף בלתי מכוון'''}} (undirectedהוא graph[[קבוצה (מתמטיקה),|קבוצה]] ולעיתים בפשטותשל '''גרףצמתים''' הוא(גם: קבוצהקודקודים שלאו צמתיםנקודות) וקבוצה של '''קשתות מכוונות''' (edges). כלכאשר ישנה משמעות לכיוונה של קשת מקשרתמכוונת - היא יוצאת ביןמצומת שניאחד צמתיםונכנסת לצומת אחר. באופן פורמלי, גרף בלתי מכוון <math>GD</math> מוגדר על ידי <math>(V,E)</math> כאשר <math>V</math> היא קבוצת הצמתים ו-<math>E \subseteq \{\{u,v\}V \mid u,v \intimes V\}</math> היא קבוצת הקשתות. ניתן לראות בגרפים בלתי מכוונים [[מקרה פרטי]] של גרפים מכוונים (בהם עבור כל זוג צמתיםקשת <math>e=(u,v)\in E</math> ו-<math>v</math>, הקשתותיוצאת מ-<math>u </math> ונכנסת ל-<math>v</math> ומ-<math>v</math> ל-<math>u </math> קיימות שתיהן, או חסרות שתיהן).

*'''גרף מעורב''' (mixed graph) הוא קבוצה של צמתים, קבוצה של קשתות מכוונות וקבוצה של קשתות לא מכוונות. כל קשת, מכוונת או לא מכוונת, מקשרת בין שני צמתים.

*'''לולאה''' (מכונה גם: '''חוג עצמי''') היא קשת (או קשת מכוונת) שמקשרת צומת עם עצמו. גרף לא מכוון ללא לולאות וללא קשתות מקבילות נקרא '''גרף פשוט'''.

*'''גרף סופי''' (finite graph) הוא גרף שקבוצת הצמתים שלו סופית.
*'''גרף אינסופי''' (infinite graph) הוא גרף שקבוצת הצמתים שלו היא [[אינסוף|אינסופית]].

*'''[[גרף ממושקל]]''' (weighted graph) הוא גרף (מכוון או בלתי מכוון) שבו לכל קשת יש ערך, לרוב מספרי, המכונה '''משקל''', כלומר מספר או ערך שמייצג עלות, אורך או כל מדד אחר. באופן פורמלי, גרף ממושקל (בלתי) מכוון הוא שלשה <math>(V,E,w)</math>, כאשר <math>V</math> ו-<math>E</math> מוגדרים כמקודם, ו-<math>w</math> היא [[פונקציה|פונקציית]] המשקל מ-<math>E</math> ל-<math>\mathbb{N}</math>,לקבוצה כלשהי (למשל ל-<math>\mathbb{R}</math>, או לקבוצת משקולות אחרת).

*'''גרף בלתי מתויג''' (unlabeled graph) הוא גרף שבו לא ניתן להבחין בין הצמתים. כלומר, אין אף מזהה ייחודי (כגון שם או מספר) לצומת בגרף.