TechCodeview

זהו כלי שימושי, שמתאר לחלוטין את הסדר החלקי הקשור. לכן, זה נקרא גם דיאגרמת הזמנה. קל מאוד להמיר גרף מכוון של יחס על קבוצה A לתרשים האסה שווה ערך. לכן, בעת ציור דיאגרמת האסה יש לזכור את הנקודות הבאות.

1. הקודקודים בתרשים האסה מסומנים בנקודות ולא במעגלים.
2. מכיוון שסדר חלקי הוא רפלקסיבי, מכאן שכל קודקוד של A חייב להיות קשור לעצמו, ולכן הקצוות מקודקוד לעצמו נמחקים בתרשים האסה.
3. מכיוון שסדר חלקי הוא טרנזיטיבי, ולכן בכל פעם aRb, bRc, יש לנו aRc. הסר את כל הקצוות המשתמעים מהמאפיין הטרנזיטיבי בתרשים Hasse, כלומר, מחק קצה מ-a ל-c אך שמור על שני הקצוות האחרים.
4. אם קודקוד 'a' מחובר לקודקוד 'b' באמצעות קצה, כלומר, aRb, אז הקודקוד 'b' מופיע מעל קודקוד 'a'. לכן, ניתן להשמיט את החץ מהקצוות בתרשים האסה.

דיאגרמת האסה היא הרבה יותר פשוטה מהגרף המכוון של הסדר החלקי.

בעוד לולאה java

דוגמא: שקול את קבוצת A = {4, 5, 6, 7}. תן R להיות היחס ≦ על A. צייר את הגרף המכוון ואת דיאגרמת האסה של R.

פִּתָרוֹן: היחס ≦ בקבוצה A ניתן על ידי

R = {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {4, 4}, {5, 5} , {6, 6}, {7, 7}}

הגרף המכוון של הקשר R הוא כפי שמוצג באיור:

כדי לצייר את דיאגרמת האסה בסדר חלקי, יישם את הנקודות הבאות:

1. מחק את כל הקצוות המשתמעים על ידי תכונה רפלקסיבית, כלומר.
   (4, 4), (5, 5), (6, 6), (7, 7)
2. מחק את כל הקצוות המשתמעים מנכס טרנזיטיבי, כלומר.
   (4, 7), (5, 7), (4, 6)
3. החלף את העיגולים המייצגים את הקודקודים בנקודות.
4. השמיט את החצים.

דיאגרמת האסה היא כפי שמוצג באיור:

גבול עליון: קח בחשבון ש-B הוא תת-קבוצה של קבוצה מסודרת חלקית A. אלמנט x ∈ A נקרא גבול עליון של B אם y ≦ x עבור כל y ∈ B.

חסם תחתון: קח בחשבון ש-B הוא תת-קבוצה של קבוצה מסודרת חלקית A. אלמנט z ∈ A נקרא גבול תחתון של B אם z ≦ x עבור כל x ∈ B.

דוגמא: שקול את המונח A = {a, b, c, d, e, f, g} שמוצג באיור. תן גם B = {c, d, e}. קבע את הגבול העליון והתחתון של B.

פִּתָרוֹן: הגבול העליון של B הוא e, f ו-g מכיוון שכל רכיב של B הוא '≦' e, f ו-g.

הגבולות התחתונים של B הם a ו-b מכיוון ש-a ו-b הם '≦' כל אלמנטים של B.

סף עליון לפחות (SUPREMUM):

תן ל-A להיות תת-קבוצה של קבוצה S מסודרת חלקית. אלמנט M ב-S נקרא גבול עליון של A אם M ימשיך כל אלמנט של A, כלומר אם, עבור כל x ב-A, יש לנו x<=m< p>

אם גבול עליון של A קודם לכל גבול עליון אחר של A, אז הוא נקרא העליון של A ומסומן ב-Sup (A)

bfs לעומת dfs

הגבול התחתון הגדול ביותר (INFIMUM):

אלמנט m בעמדה S נקרא גבול תחתון של תת-קבוצה A של S אם m קודם לכל אלמנט של A, כלומר אם, עבור כל y ב-A, יש לנו m<=y < p>

אם גבול תחתון של A יחליף כל גבול תחתון אחר של A, אז הוא נקרא ה-infimum של A והוא מסומן ב-Inf (A)

דוגמא: קבע את הגבול העליון והתחתון הגדול ביותר של B = {a, b, c} אם הם קיימים, של הפוזה שתרשים האסה שלה מוצג באיור:

פִּתָרוֹן: הגבול העליון המינימלי הוא c.

הגבול התחתון הגדול ביותר הוא k.