2024 מְחַבֵּר: Elizabeth Oswald | [email protected]. שונה לאחרונה: 2024-01-13 00:06
תת-גרף מתפרש הוא תת-גרף שמכיל את כל הקודקודים של הגרף המקורי. עץ פורש הוא תת-גרף מתפרש שלעתים קרובות מעורר עניין. מחזור בגרף המכיל את כל קודקודי הגרף ייקרא מחזור מתח.
כמה תת-גרפי משנה יש?
יש 2n תת-גרפים המושרים (כל תת-קבוצות הקודקודים) ו-2m תת-גרפים פורשים (כל תת-קבוצות הקצוות).
איך אני מוצא תת-גרף מתפרש?
ובהגדרה של תת-גרף משתרע של גרף G הוא תת-גרף המתקבל על ידי מחיקת קצה בלבד. אם ניצור קבוצות משנה של קצוות על ידי מחיקת קצה אחד, שני קצה, שלושה קצוות וכן הלאה. כפי שיש m קצוות כך יש 2^m תת-קבוצות. מכאן שיש ל-G תת-גרפים משתרעים של 2^m.
למה הכוונה בעץ פורש?
העץ המתפרש של גרף (G) הוא תת-קבוצה של G המכסה את כל הקודקודים שלו באמצעות המספר המינימלי של קצוות. ניתן להסיק כמה תכונות של עץ פורש מהגדרה זו: מכיוון ש"עץ פורש מכסה את כל הקודקודים", לא ניתן לנתק אותו.
מהי תורת הגרפים המתפרשת?
עץ פורש הוא תת-קבוצה של גרף G, ש-כוללת את כל הקודקודים במספר מינימלי אפשרי של קצוות. מכאן שלעץ פורש אין מחזורים ולא ניתן לנתק אותו.. לפי הגדרה זו, אנו יכולים להסיק שלכל גרף G מחובר ובלתי מכוון יש לפחות עץ פורש אחד.
