לדלג לתוכן
שינוי מצב סרגל צד
Math-Wiki
חיפוש
יצירת חשבון
כלים אישיים
יצירת חשבון
כניסה לחשבון
דפים לעורכים שלא נכנסו לחשבון
מידע נוסף
שיחה
תרומות
ניווט
עמוד ראשי
שינויים אחרונים
העלאת קובץ
כלים
דפים המקושרים לכאן
שינויים בדפים המקושרים
דפים מיוחדים
מידע על הדף
עריכת הדף "
תקציר תורת הגרפים, סמסטר א תשע״ג
" (פסקה)
דף
שיחה
עברית
קריאה
עריכה
גרסאות קודמות
עוד
קריאה
עריכה
גרסאות קודמות
אזהרה:
אינכם מחוברים לחשבון. כתובת ה־IP שלכם תוצג בפומבי אם תבצעו עריכות כלשהן. אם
תיכנסו לחשבון
או
תיצרו חשבון
, העריכות שלכם תיוחסנה לשם המשתמש שלכם ותקבלו גם יתרונות אחרים.
בדיקת אנטי־ספאם.
אין
למלא שדה זה!
=== גרפים הנוצרים מגרפים אחרים === ==== תת־גרף ==== * '''השמטת צלע''' <math>e\in E</math> מגרף <math>G</math> היא הפיכת הגרף ל־<math>G\setminus\{e\}:=(V,E\setminus\{e\})</math>. * '''השמטת קודקוד''' <math>v\in V</math> מגרף <math>G</math> היא הפיכת הגרף ל־<math>G\setminus\{v\}:=(V\setminus\{v\},E\setminus\{(v,u):\ u\in V\})</math>. * '''תת־גרף''' הוא הגרף המתקבל מסדרה של השמטות קודקודים ו/או צלעות. * '''תת־גרף פורש''' הוא תת־גרף המתקבל מסדרה של השמטות צלעות בלבד. * '''תת־גרף מושרה''' הוא תת־גרף המתקבל מסדרה של השמטות קודקודים בלבד. ==== חלוקה ==== * '''חלוקה אלמנטרית''' של צלע <math>e=(u,v)</math> בגרף <math>G</math> היא <math>G\setminus\{e\}\cup\Big(\{e\},\{(u,e),(v,e)\}\Big)</math>. * '''חלוקה''' של גרף היא היא גרף המתקבל מסדרה של חלוקות אלמנטריות. ==== כיווץ ==== * '''כיווץ''' של גרף <math>G</math> בצלע <math>e=(u,v)</math> הוא <math>G/e:=G\setminus\{u,v\}\cup\Big(\{e\},\{e\}\times(N_G(u)\cup N_G(v))\Big)</math>. * '''מינור''' של גרף פשוט הוא גרף המתקבל ממנו ע״י סדרה של השמטות קודקודים, השמטות צלעות וכיווצי צלעות. * '''תכונה מונוטונית''' של גרף היא תכונה הסגורה תחת מינור, כלומר אם גרף מקיים אותה אז כל מינור שלו מקיים אותה. ==== גרף משלים ==== * '''הגרף המשלים''' של גרף <math>G=(V,E)</math> הוא <math>\overline G:=(V,V^2\setminus E)</math>. ==== גרף הקו ==== * '''גרף הקו''' של גרף פשוט <math>G</math> מסומן <math>L(G)</math> ומוגדר כגרף שקודקודיו הם <math>E(G)</math> וצלעותיו הם זוגות של צלעות שיש להן קודקוד משותף ב־<math>G</math>, כלומר <math>E(L(G)):=\Big\{\Big((u_1,v),(u_2,v)\Big):\ (u_1,v),(u_2,v)\in E(G)\Big\}</math>. ==== מכפלה קרטזית של גרפים ==== * '''המכפלה הקרטזית''' של הגרפים <math>G,H</math> היא גרף המסומן כ־<math>G\times H</math>. קודקודיו הם <math>V(G)\times V(H)</math> (כשהקודקודים הם זוגות סדורים) וצלעותיו <math>\Big((v,u_1),(v,u_2)\Big)</math> כאשר <math>v\in V(G)\ \and\ (u_1,u_2)\in E(H)</math> או <math>\Big((v_1,u),(v_2,u)\Big)</math> כאשר <math>u\in V(H)\ \and\ (v_1,v_2)\in E(G)</math>. * '''קובייה ''n''־מימדית''' היא <math>K_2^{\times n}:=\prod_{i=1}^n K_2</math>.
תקציר:
לתשומת לבך: תורמים אחרים עשויים לערוך או אף להסיר את תרומתך ל־Math-Wiki. אם אינך רוצה שעבודתך תהיה זמינה לעריכה על־ידי אחרים, אין לפרסם אותה פה.
כמו־כן, שמירת העריכה משמעה הבטחה שכתבת את הטקסט הזה בעצמך, או העתקת אותו ממקור שאינו מוגן בזכויות יוצרים (אפשר לעיין בדף
Math-Wiki:זכויות יוצרים
לפרטים נוספים).
אין לעשות שימוש בחומר המוגן בזכויות יוצרים ללא רשות!
ביטול
עזרה בעריכה
(נפתח בחלון חדש)