ماتریس مجاورت
معنی کلمه ماتریس مجاورت در دانشنامه عمومی
در گراف G = ( V , E ) می پنداریم که گره ها از یک تا شمار گره ها ( | V | ) شماره گذاری شده اند. اگر شمار گره های گراف n باشد، ماتریس مجاورت n × n درآیه دارد و هر درآیهٔ a i j شمار یال های میان گره های شماره گذاری با i و j را نشان می دهد. اگر گراف ساده باشد، درآیهٔ a i j تنها می تواند صفر یا یک باشد. ارزش صفر نشان دهندهٔ نبود یال است و ارزش یک نشان دهندهٔ بودن یال.
ماتریس مجاورت گرافی ساده دارای ویژگی های زیر است:
• ماتریس مجاورت همامون ( متقارن ) است.
• در گراف کامل، همهٔ درایه های ماتریس مجاورت جز درایه های قطر یک اند.
• همهٔ درایه های ماتریس مجاورت گرافی تهی صفر اند.
برای گرافی دوبخشی که یک بخش دارای r گره و بخش دیگر دارای s گره است، ماتریس مجاورت A چنین است:
A = ( 0 r , r B B T 0 s , s )
زیرماتریس B دارای r × s درآیه است و ماتریس 0 r , r و 0 s , s به ترتیب ماتریس های صفر با اندازه های r × r و s × s هستند. گاه این ماتریس، ماتریس مجاورت دوبخشی نیز خوانده می شود.
ماتریس مجاورت گرافی سادهٔ بی سو همامون ( متقارن ) است و بنابراین مجموعه ای کامل از مقدار ویژه های حقیقی و یک بردار ویژهٔ متعامد دارد. ( basis ) مجموعهٔ مقدار ویژه های یک گراف، طیف آن گراف را تشکیل می دهند. فرض کنید ۲ گراف ( باسو یا با سو ) G 1 و G 2 با ماتریس مجاورت های A 1 و A 2 داده شده اند. G 1 و G 2 هم ریخت ( متناظر/isomorphic ) اند، اگر و فقط اگر وجود داشته باشد ماتریس جایگشت P به طوری که :
معنی کلمه ماتریس مجاورت در ویکی واژه
جملاتی از کاربرد کلمه ماتریس مجاورت
وقتی گراف با استفاده از لیست‌های مجاورت یا ماتریس مجاورت نمایش داده می‌شود، یک عمل یکتای تلفیق یالی را می‌توان با تعدادی بروزرسانی با زمان اجرای خطی روی داده ساختار، با زمان اجرای کل
الگوریتم زیر با گرفتن ماتریس مجاورت، یالهای تطابق بیشینه را به دست میدهد .