از روی ماتریس مجاورت گراف آیا میشه فهمید...گراف همبند یا نا همبند؟؟؟
بله .
از روی ماتریس گراف رو بکشید ببینید همبند هست یا نه.
البته فقط باید یالهای بین راس ها را از روی گراف رسم کنید ببینیم بین راس ها ارتباط هست یا خیر اگه ارتباط بود همبند است
(۲۰ اردیبهشت ۱۳۹۱ ۰۴:۳۹ ب.ظ)Aurora نوشته شده توسط: بله .
از روی ماتریس گراف رو بکشید ببینید همبند هست یا نه.
فک کنم منظورشون الگوریتمشه. یه الگوریتم تشخیص دور...
(۲۰ اردیبهشت ۱۳۹۱ ۰۴:۴۴ ب.ظ)hkarimi نوشته شده توسط:میتونید گراف رو پیمایش کنید تا بفهمید.(20 اردیبهشت ۱۳۹۱ ۰۴:۳۹ ب.ظ)Aurora نوشته شده توسط: بله .فک کنم منظورشون الگوریتمشه. یه الگوریتم تشخیص دور...
از روی ماتریس گراف رو بکشید ببینید همبند هست یا نه.
یه راه دیگه هم اینه که ترتیب سطر ها(یا ستون ها) رو جابه جا کرد. اگه تونستیم به ماتریسی برسیم که بشه به بلاک هایی تقسیمش کرد که با هم اشتراک ندارن گراف ناهمبند بوده.(تعداد بلاک ها همون تعداد مولفه های همبندیه).
(۲۰ اردیبهشت ۱۳۹۱ ۰۵:۰۹ ب.ظ)blackhalo1989 نوشته شده توسط:(20 اردیبهشت ۱۳۹۱ ۰۴:۴۴ ب.ظ)hkarimi نوشته شده توسط:میتونید گراف رو پیمایش کنید تا بفهمید.(20 اردیبهشت ۱۳۹۱ ۰۴:۳۹ ب.ظ)Aurora نوشته شده توسط: بله .فک کنم منظورشون الگوریتمشه. یه الگوریتم تشخیص دور...
از روی ماتریس گراف رو بکشید ببینید همبند هست یا نه.
یه راه دیگه هم اینه که ترتیب سطر ها(یا ستون ها) رو جابه جا کرد. اگه تونستیم به ماتریسی برسیم که بشه به بلاک هایی تقسیمش کرد که با هم اشتراک ندارن گراف ناهمبند بوده.(تعداد بلاک ها همون تعداد مولفه های همبندیه).
میشه بیشتر توضیح بدین؟ یعنی چی ترتیبشو جابه جا کنم؟ این اشتراک یعنی چی؟؟؟
ماترس مجاورت گراف زیر رو بنویسید تا بفهمید:
گراف شامل ۵ راس و دو مولفه همبندی که رئوس ۱و۲و۳ همه با هم یال دارند و رئوس ۴و۵ هم همینطور و ۱،۲،۳ و ۴،۵ به هم یالی ندارن. ماتریس مجاورت این گراف دارای دو بلاکه و بقیه درایه ها هم صفرن.
حالا اگه شماره راس ها رو عوض کنیم دیگه بلاک ها به هم میریزن. ولی میشه باز هم با یه جایشگت مناسب برای سطرها، ماتریس مجاورت رو به شکل بالا تبدیل کرد.
در حقیت هر جایگشتی که در اون راس های مولفه های همبندی کنار هم باشند ماتریس رو به شکل دلخواه تبدیل میکنه.
(۲۰ اردیبهشت ۱۳۹۱ ۰۵:۳۵ ب.ظ)blackhalo1989 نوشته شده توسط: ماترس مجاورت گراف زیر رو بنویسید تا بفهمید:
گراف شامل ۵ راس و دو مولفه همبندی که رئوس ۱و۲و۳ همه با هم یال دارند و رئوس ۴و۵ هم همینطور و ۱،۲،۳ و ۴،۵ به هم یالی ندارن. ماتریس مجاورت این گراف دارای دو بلاکه و بقیه درایه ها هم صفرن.
حالا اگه شماره راس ها رو عوض کنیم دیگه بلاک ها به هم میریزن. ولی میشه باز هم با یه جایشگت مناسب برای سطرها، ماتریس مجاورت رو به شکل بالا تبدیل کرد.
ببخشید منظور شما اینه که انقدر سطرها رو جابجا کنیم تا مثلا یک های بیشتری کنار هم قرار بگیرند؟
[tex]\begin{vmatrix}1 & 1 &0 \\ 0 &0 &1 \\ 0 & 1 & 0 \end{vmatrix}[/tex]
سطر ۲ رو با ۳ جابجا می کنیم تا یک های بیشتری کنار هم باشند.
[tex]\begin{vmatrix} 1 &1 &0 \\ 0& 1 &0 \\ 0&0 &1 \end{vmatrix}[/tex]
۰ ۱ ۱
۰ ۱ ۰
۰ ۰ ۱
الان اونایی که با قرمز مشخص کردم چون اشتراک دارند یک مولفه هستند و یک پایین هم چون هیچ اشتراکی نداره یک مولفه ست پس گراف ناهم بنده؟ درسته؟
شکل پیوست شده رو نگاه کنید. این شکل مربوط به ماتریسی هست که ۳ تا مولفه همبندی داره که با A,B,C نشون داده شدن. ماتریس مجاورت این گراف در صورتی که شماره گذاری راس ها طوری که ما میخوایم باشه (یا شماره راس ها رو جا به جا کنیم) به شکل زیر میشه:
[tex]\begin{pmatrix} A &0 &0 \\ 0&B &0 \\ 0& 0 & C \end{pmatrix}[/tex]
که تو این ماتریس A,B,Cنماد یه بلاک هستن(یعنی یه عدد نیسن بلکه هر کدوم نماد یه بلاک از ۰ ها و ۱ ها هستن. ۰ هایی که تو ماتریس هستن هم نماینده ماتریس ۰ با اندازه مناسب هستن.)
البته ممکنه شماره گذاری راس ها طوری باشن که جای A,B,C عوض بشه.
صورت قضیه اینه: هر ماتریس مجاورت معتبری رو میشه به شکلی که گفتم تبدیل کرد.
حالا اینکه عکس قضیه درسته یا نه و اینکه چجوری به الگوریتم تبدیلش کنیم رو شما روش فکر کنید.
سلام ماتریس های زیر رو درنظر بگیرید:
[tex]\begin{bmatrix} 1 & 0 & 0 & 1\\ 0 & 1 & 1 & 0\\ 0 & 1 & 1 & 0\\ 1 & 0 & 0 & 1 \end{bmatrix}[/tex]
ترتیب رئوسش به ترتیب a,b,c,d هست. چه توی سط و چه ستون. میشه به این فرم البته با ترتیب adbc نوشت:
[tex]\begin{bmatrix} 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 1 \end{bmatrix}[/tex]
دقت کنید که اگه مثل شکل ضمیمه دوتا خط روی این ماتریس به فرمی بکشیم که از پایین سمت راست دزایه [tex]a_{i,i}}[/tex] بگذره و ماتریس رو به چهار بخش تقسیم کنه که قسمت های بالا سمت راست و پایین سمت چپ فقط صفر باشن مشخص میکنه که گراف همبند نیست. صفرهای آبی رنگ قسمت های جداشده هستن.
هر ماتریسی رو که خواستید امتحان کنید باید ترتیب رئوس ماتریس رو عوض کنید به فرمی که بشه با کشیدن خطی مشابه خط قرمز، صفرهای آبی رو مشخص کرد. توجه کنید که با کشیرن خط قرمز، تکه ماتریس هایی که روی قطر اصلی هستن حتماً باید مربعی باشن ولی تکه ماتریس های کناری لزومی نداره که مربعی باشن.