גרף מכוון לעומת לא מכוון
גרף הוא מבנה מתמטי המורכב מקבוצה של קודקודים וקצוות. גרף מייצג קבוצה של אובייקטים (מיוצגים על ידי קודקודים) המחוברים דרך כמה קישורים (מיוצגים על ידי קצוות). באמצעות סימונים מתמטיים, ניתן לייצג גרף על ידי G, כאשר G=(V, E) ו-V הוא קבוצת הקודקודים ו-E הוא קבוצת הקצוות. בגרף לא מכוון אין כיוון הקשור לקצוות המחברים את הקודקודים. בגרף מכוון יש כיוון הקשור לקצוות המחברים את הקודקודים.
תרשים לא מכוון
כפי שהוזכר קודם לכן, גרף לא מכוון הוא גרף שבו אין כיוון בקצוות המקשרים בין הקודקודים בגרף.איור 1 מתאר גרף לא מכוון עם קבוצת קודקודים V={V1, V2, V3}. ניתן לכתוב קבוצת קצוות בגרף לעיל כ-V={(V1, V2), (V2, V3), (V1, V3)}. ניתן גם לציין שאין שום דבר שמונע את כתיבת קבוצת הקצוות כ-V={(V2, V1), (V3, V2), (V3, V1)} שכן לקצוות אין כיוון. לכן קצוות בגרף לא מכוון אינם זוגות מסודרים. זהו המאפיין העיקרי של גרף לא מכוון. ניתן להשתמש בגרפים לא מכוונים כדי לייצג יחסים סימטריים בין אובייקטים שמיוצגים על ידי קודקודים. לדוגמה, רשת כבישים דו-כיוונית המחברת קבוצה של ערים יכולה להיות מיוצגת באמצעות גרף לא מכוון. ניתן לייצג את הערים על ידי הקודקודים בגרף והקצוות מייצגים את הדרכים הדו-כיווניות המחברים בין הערים.
גרף מכוון
גרף מכוון הוא גרף שבו לקצוות בגרף המקשרים בין הקודקודים יש כיוון. איור 2 מתאר גרף מכוון עם קבוצת קודקודים V={V1, V2, V3}. ניתן לכתוב קבוצת קצוות בגרף לעיל כ-V={(V1, V2), (V2, V3), (V1, V3)}. קצוות בגרף לא מכוון הם זוגות מסודרים. באופן פורמלי, קצה e בגרף מכוון יכול להיות מיוצג על ידי הזוג המסודר e=(x, y) כאשר x הוא הקודקוד שנקרא המקור, המקור או הנקודה הראשונית של הקצה e, וקודקוד y נקרא הקצה, קודקוד מסיים או נקודת קצה. לדוגמה, רשת כבישים המחברת קבוצה של ערים באמצעות כבישים חד כיווניים יכולה להיות מיוצגת באמצעות גרף לא מכוון. הערים יכולות להיות מיוצגות על ידי הקודקודים בגרף והקצוות המכוונים מייצגים את הדרכים המקשרות בין הערים בהתחשב בכיוון שהתנועה זורמת בכביש.
מה ההבדל בין גרף מכוון לגרף לא מכוון?
בגרף מכוון קצה הוא זוג מסודר, כאשר הצמד המסודר מייצג את כיוון הקצה המקשר בין שני הקודקודים. מצד שני, בגרף לא מכוון, קצה הוא זוג לא מסודר, מכיוון שאין כיוון הקשור לקצה. ניתן להשתמש בגרפים לא מכוונים כדי לייצג יחסים סימטריים בין אובייקטים. מעלות פנימה והחוצה של כל צומת בגרף לא מכוון שווה אבל זה לא נכון עבור גרף מכוון. כאשר משתמשים במטריצה לייצוג גרף לא מכוון, המטריצה תמיד הופכת לגרף סימטרי, אבל זה לא נכון לגבי גרפים מכוונים. ניתן להמיר גרף לא מכוון לגרף מכוון על ידי החלפת כל קצה בשני קצוות מכוונים בכיוון הפוך. עם זאת, לא ניתן להמיר גרף מכוון לגרף לא מכוון.
