نمودار از رئوس و لبه ها تشکیل شده است. رأس ها با توجه به ویژگی خاص - لبه ها به هم متصل می شوند - رابطه بروز ، که مجموعه لبه ها را تعریف می کند. در این حالت ، حلقه ها و رئوس جدا شده می توانند تشکیل شوند.
دستورالعمل ها
مرحله 1
اجازه دهید مجموعه ای از لبه های نمودار داده شود و رابطه ای که در امتداد آن می توان یک لبه را از یک راس به دیگری را ترسیم کرد ، داده می شود. به عنوان نمونه ، مجموعه رئوس {1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7 ، 8} ، دو راس x و y در نسبت x + y <8 قرار دارند.
گام 2
یک ماتریس همجواری راس بسازید. برای این کار یک جدول مربع درست کنید ، تعداد ردیف ها و ستون های جدول با تعداد رئوس همزمان است. سپس اگر رئوس i و j نسبت داده شده را برآورده کنند ، 1 را در تقاطع ردیف i و ستون j-th قرار دهید. اگر نسبت عناصر مربوطه برآورده نشود ، 0 را در تقاطع ردیف i و ستون j-th قرار دهید.
در مثال ما ، خط اول به صورت زیر پر می شود:
1 + 1 <8 ، بنابراین 1 در تقاطع ردیف 1 و ستون 1 وجود دارد
1 + 2 <8 ، دوباره 1
1 + 3 <8 ، دوباره 1
1 + 7 <8 ، نابرابری نادرست ، بنابراین این عنصر جدول 0 خواهد بود
1 + 8 <8 ، دوباره 0
مرحله 3
برای دانستن تعداد لبه ها ، تعداد موارد موجود در ماتریس مجاورت را بدون کپی کردن لبه ها بشمارید.
در مثال ، یک ماتریس متقارن بدست آمده است ، بنابراین ما ابتدا آنهایی را که بالای مورب اصلی ماتریس قرار دارند (با رنگ آبی مشخص شده است) ، و سپس مواردی را که روی مورب اصلی قرار دارند (با رنگ قرمز مشخص شده) شمردیم. تعداد کل دنده ها 12 عدد است.
مرحله 4
یک ماتریس از حوادث (لبه ها) بسازید. برای انجام این کار ، یک جدول رسم کنید ، تعداد ردیف های موجود در آن با تعداد رئوس نمودار و تعداد ستون ها با تعداد لبه ها برابر است. واحدهایی را روی آن خطوط قرار دهید که با یک لبه به هم متصل شوند. لبه های منتهی به راس به آن حلقه گفته می شود و به انتهای ماتریس اضافه می شود. در ستون های مربوط به حلقه ها ، بر خلاف بقیه لبه ها ، فقط یک واحد وجود دارد.
مرحله 5
حالا یک نمودار بکشید. به هر روشی رئوس را روی کاغذ قرار داده و با استفاده از جداول ساخته شده آنها را با لبه ها متصل کنید. راسهایی که با لبه ها به هم متصل نیستند ، جدا شده نامیده می شوند.
