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

 نمودار هاسه 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: در نمودار هاسه دور و طوقه وجود ندارد. (با توجه به الگوریتم رسم واضح است.)

مجموعه ی مرتب جزئی Partial Order Set

مجموعه مرتب جزئی Partial Order Set (poset)

رابطه ی ≥  را مرتب جزئی گوییم هرگاه به ازای هر x و y و z در A داشته باشیم:

خودتوان باشد:

پادتقارنی باشد:

تعدی باشد:

مجموعه ی A همراه با رابطه ترتیب ≥ را مجموعه مرتب جزئی گوییم.

مثال: مجموعه ی اعداد طبیعی همراه با رابطه ی عاد کردن، مجموعه ای جزئی مرتب است.

 

اگر هر دو عضو در مجموعه ی A قابل مقایسه باشند، آنگاه مجموعه A را کلی مرتب (Total Order) می نامیم. به عبارتی به ازای هر x و y در A، داشته باشیم:

مثال: مجموعه ی اعداد طبیعی با رابطه ی ترتیب معمولی، مجموعه ای کلی مرتب است.

مثال: عاد کردن رابطه ای کلی مرتب نیست، زیرا مثلا 2 و 3 هیچ یک برهم بخش پذیر نیستند، بنابراین در رابطه ی عاد کردن صدق نمی کنند.