גרף קשיר – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט החלפות: תת-; |
מ קישורים |
||
שורה 16:
==רכיבי קשירות==
אם <math>\ H=(W,F)</math> הוא [[תת-גרף]] של גרף <math>\ G=(V,E)</math>, אזי <math>\ H</math> יכונה '''רכיב קשירות''' של <math>\ G</math> אם הוא תת-גרף מושרה קשיר מקסימלי (כלומר, כל [[תת-גרף מושרה]] שיכיל אותו כבר לא יהיה קשיר). פורמלית ניתן לתאר זאת באמצעות התנאים הבאים:
* <math>\ W=\emptyset\iff V=\emptyset</math>.
* לכל <math>\ w\in W</math> ולכל <math>\ v\in V</math>, אם קיים ב-<math>\ G</math> מסלול מ-<math>\ w</math> ל-<math>\ v</math>, אזי <math>\ v\in W</math>.
| |||