محاسبات نرم

محاسبات نرم

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

نظرات (۰)

هیچ نظری هنوز ثبت نشده است
ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی