גרף קשיר – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
מ תיקון טעות
אין תקציר עריכה
שורה 13:
יש לשים לב כי ההגדרה הנ"ל משתנה קלות כאשר מדובר בגרפים לא מכוונים או ב[[גרף מכוון|גרפים מכוונים]]. במקרה הראשון, קשת היא [[קבוצה (מתמטיקה)|קבוצה]] בת שני צמתים, ואילו במקרה השני, קשת היא [[זוג סדור]] של שני צמתים.
 
במתמטיקה באופן כללי, ובעיקר ב[[טופולוגיה]], [[קשירות (טופולוגיה)|קשירות]] של קבוצה מציינת שכל הקבוצה היא "בחתיכה אחת". בתורת הגרפים קשירות מתבטאת בכך שכל צומתי הגרף מחוברים יחד, במובן זה שניתן להגיע מכל צומת לכל צומת אחר. קשירות היא דרישה בסיסית מגרפים, על מנת שיקיימו תכונות נוספות. למשל, כדי שיהיה בגרף [[מסלול אוילרי]], הכרחי שהוא יהיה קשיר (פרט אולי לצמתים שאינם מחוברים כלל לקשתות). קשירות היא גם דרישה בסיסית מ[[עץ (תורת הגרפים)|עץ]].
 
==רכיבי קשירות==