آمار پرسش:
- پرسیده شده: 2020-03-30 17:15:51 -0600
- مشاهده شده: 98 بار
- بروز شده: 2020-04-02 02:41:44 -0600
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
شرایط عدم وجود دور در یک ماتریس
سلام. میخواستم بدونم شرط کافی برای عدم وجود دور در یک گراف ساده از روی ماتریس مجاورت آن چیست؟ با تشکر
1 پاسخ
سلام
وجود یک دور در یک گراف ساده معادل با این شرط است:
$k$ عدد $ a_1, a_2 , ... ,a_k$ موجود باشند $ ( 1 \leq a_1 \lt a_2 \lt .. \lt a_k \leq n,k\leq n )$ به طوریکه جدول $ k\times k$ حاصل از برخورد $k$ سطر با شماره‌های $a_1$ تا $a_k$ با $k$ ستون با شماره‌های $a_1$ تا $a_k$ در هر سطر و ستونش دقیقا $2$ درایه $1$ موجود باشه.
پس برای اینکه نشون بدیم یک گراف دور نداره، باید بگیم که نمیشه هیچ $k$ تاعددی انتخاب کرد ($k$ دلخواه) که محل برخورد سطرها وستونهای باشماره های این $k$ تا عدد این ویژگی رو داشته باشند که در هر سطر و ستونشون دقیقا دو تا درایه $1$ موجود باشه.
البته معمولا براورده کردن این شرط اسون نیست واقعا!
و اینکه میشه برای چک کردن این که یک گراف دور داره یا نه از الگوریتم های پیمایش گراف مثل DFS و BFS هم استفاده کرد.
