גרף (תורת הגרפים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
חידוד |
הנדב הנכון (שיחה | תרומות) מאין תקציר עריכה |
||
שורה 13:
==סוגי גרפים==
*{{עוגן|גרף מכוון|'''גרף מכוון'''}} (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>.
*'''גרף בלתי מכוון''' (undirected graph), ולעיתים בפשטות '''גרף''' הוא קבוצה של צמתים וקבוצה של '''קשתות''' (edges). כל קשת מקשרת בין שני צמתים. באופן פורמלי, גרף בלתי מכוון <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> קיימות שתיהן, או חסרות שתיהן), או לחילופין, ניתן לראות בגרף מכוון מקרה פרטי של גרף בלתי מכוון, מהיותו קבוצה קטנה יותר של זוגות סדורים מהגרף הבלתי מכוון, דהיינו - גרף מכוון
*'''גרף מעורב''' (mixed graph) הוא קבוצה של צמתים, קבוצה של קשתות מכוונות וקבוצה של קשתות לא מכוונות. כל קשת, מכוונת או לא מכוונת, מקשרת בין שני צמתים.
*'''לולאה''' (מכונה גם '''חוג עצמי''') היא קשת (או קשת מכוונת) שמקשרת צומת עם עצמו. גרף לא מכוון ללא לולאות וללא קשתות מקבילות נקרא '''גרף פשוט'''.
| |||