גרף קשיר

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

פורמלית, גרף G=\left(V,E\right) ייקרא קשיר אם לכל זוג צמתים V_i\, ו-V_j\, ב-V\, קיימת סדרה של קשתות e_1, e_2, \ldots, e_k ב-E\, כך שאם e_\ell = (v_{a_\ell}, v_{b_\ell}) לכל \ell אז:

א. a_1\,= i. דהיינו, המסלול מתחיל בצומת v_i\,.

ב. b_k\,= j. דהיינו, המסלול מסתיים בצומת v_j\,.

ג. לכל \ell מתקיים b_\ell = a_{\ell+1}. דהיינו, סדרת הקשתות מהווה מסלול בגרף.

יש לשים לב כי ההגדרה הנ"ל משתנה קלות כאשר מדובר בגרפים לא מכוונים או בגרפים מכוונים. במקרה הראשון, קשת היא קבוצה בת שני צמתים, ואילו במקרה השני, קשת היא זוג סדור של שני צמתים.

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


מקור: http://he.wikipedia.org../../../%D7%92/%D7%A8/%D7%A3/%D7%92%D7%A8%D7%A3_%D7%A7%D7%A9%D7%99%D7%A8.html