محاسبات نرم

محاسبات نرم

۱ مطلب با کلمه‌ی کلیدی «مجموعه مرتب» ثبت شده است

 نمودار هاسه Hasse Diagram

 فرض کنید (A,≤) یک مجموعه ی مرتب جزئی باشد. نمودار هاسه این مجموعه به صورت زیر ساخته می‌شود:


1.      به ازای هر یک از اعضای A یک نقطه در صفحه در نظر می‌گیریم. اگر a و b دو عضو متمایز از A باشند که a≤b ارتفاع b بیشتر از a باشد.

2.      اگر a و b دو عضو متمایز باشند و a≤b آنگاه با یک منحنی صعودی نقطه نظیر a را به نقطه نظیر b وصل می‌کنیم.

3.      تمام منحنی‌های رسم شده در گام 2 را برای خواص تعدی حذف می‌کنیم.

یعنی اگر a≤b نقطه نظیر a را به نقطه نظیر b با یک منحنی وصل می‌کنیم هرگاه عنصر c متمایز از a و b نداشته باشیم که a≤c≤b.


مثال: زوج های مرتب روی مجموعه اعداد طبیعی را با رابطه ی زیر در نظر بگیریم:

  (a,b) ≤ (c,d) if a ≤ c and b ≤d                                                                          

  نمودار هاسه به شکل زیر خواهد بود:


                                           


توجه1: برای رسم نمودار هاسه روش های متعددی وجود دارد، اما معمولا برای رسم ابتدا نقطه مینیمم (در صورت وجود) را قرار می دهند و باتوجه به رابطه ترتیب، نقاط و خطوط دیگر را اضافه می کنند. بنابراین نمودار هاسه هر مجموعه مرتب جزئی یکتا نیست.


توجه2: در نمودار هاسه دور و طوقه وجود ندارد. (با توجه به الگوریتم رسم واضح است.)

  • تکراری