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