|
|
עמוד:219
דוגמה 5 . 6 להלן גרף ו נמנה את הרכיבים הקשירים בגרף : רכיב קשיר אחד הוא הקבוצה , { A , B , C , D ) מאחר שבקבוצה זו יש מסלול פשוט בין כל שני קדקודים בגרף . לקבוצה הזאת לא ניתן לצרף אף אחד מן הקדקודים E , F , G מאחר שלדוגמה אין מסלול מקדקוד A £ -ל או irtf או ל-ס . הרכיב הקשיר השני הוא הקבוצה ו , { £ , F ] והרכיב הקשיר השלישי הוא ו , { 0 } כיוון שעלפי ההגדרה , קדקוד בודד יכול להיקרא גם כן רכיב קשיר , בתנאי שהקבוצה הזאת היא מקסימלית , כלומר אי-אפשר להוסיף לקבוצה הזאת צמתים נוספים בגרף כך שבקבוצה החדשה שתתקבל יהיה מסלול בין כל שני קדקודים בקבוצה . מסקנה : בתרשים ישנם שלושה רכיבים קשירים . גרף קשיר — ( connected graph ) גרף לא מכוון בעל רכיב קשיר אחד בלבד . כלומר , קיים מסלול פשוט בין כל שני קדקודים בגרף . גרף קשיר מכוון בחחקה - ( strongly connected directed graph ) גרף מכוון שבו יש מסלול פשוט ומכוון בין כל שני קדקודים בגרף . בתרשים הבא נתון גרף קשיר מכוון בחוזקה , שכן יש מסלול מכוון מכל קדקוד לכל קדקוד אחר בגרף . אייר 5 . 6 גרף עם שלושה רכיבים קשיריס
|
|