תוצאות החיפוש

==אלגוריתמים לחישוב סגור טרנזיטיבי של גרפים== [[:קטגוריה:אלגוריתמים בתורת הגרפים]] ...

פעמים רבות דנים בתורת הגרפים [[גרף פשוט|בגרפים פשוטים]]{{דרושה הבהרה|למה התכוון המשורר?}}. עבור גרף שבו אין [[תורת הגרפים|לולאות עצמיות]] (כלומר, קשת מקודקוד כלשהו לעצמו), [[אלכסון ראשי|האלכסון הרא ...

...קבוצה בלתי תלויה''' (IS - Independent set) היא קבוצת קודקודים ב[[גרף (תורת הגרפים)|גרף]], אשר אין זוג מביניהם המחוברים ישירות דרך קשת אחת. בצביעה חוקית של קו ...ת]] מ[[בעיית SAT]]. חיפוש של קבוצה בלתי תלויה שקול לחיפוש של [[קליקה (תורת הגרפים)|קליקה]] (תת גרף מלא) בגרף המשלים (שקבוצת הקשתות שלו [[משלים (מתמטיקה)|משלי ...

הניסוח המתמטי המדויק של בעיית מיון טופולוגי נעזר ב[[תורת הגרפים]]: בהינתן [[גרף מכוון חסר מעגלים]] (DAG), מיון טופולוגי שלו הוא מתן מספרים [[קטגוריה:אלגוריתמים בתורת הגרפים]] ...

[[קטגוריה:אלגוריתמים בתורת הגרפים|פרים]] ...

...]. בפשטות, גרף מייצג קבוצת אובייקטים וקשרים ביניהם. לפעמים מחשיבים את תורת הגרפים כענף של [[מתמטיקה בדידה]]. == מושגים יסודיים בתורת הגרפים == ...

...ף קשיר|קשיר]] ללא [[מעגל (תורת הגרפים)|מעגלים]]. מלבד התפקיד של עצים בתורת הגרפים, כגרפים הקשירים המינימליים, ובטופולוגיה כמודל ל[[מרחב היפרבולי]], עצים הנוש * ב-<math>G</math> אין מעגל פשוט, אך אם נוסיף לו [[קשת (תורת הגרפים)|קשת]] אחת, ייווצר בו מעגל פשוט. ...

...ראשי תיבות]]: '''BFS''') הוא [[אלגוריתם]] המשמש למעבר על צומתי [[גרף (תורת הגרפים)|גרף]], למשל לצורך [[אלגוריתם חיפוש|חיפוש]] צומת המקיים תכונה מסוימת. הגרף [[קטגוריה:אלגוריתמים בתורת הגרפים|חיפוש לרוחב]] ...

...]] בשנת [[1956]]. המטרה היא למצוא [[תת קבוצה]] של הקשתות שתיצור [[עץ (תורת הגרפים)|עץ]] המכיל את כל קודקודי הגרף (עץ כזה נקרא עץ פורש) שמשקלו מינימלי. כלומר ...ביותר במשקלה, ומוסיף כל קשת לעץ הפורש כל עוד הוספתה לא יוצרת [[מעגל (תורת הגרפים)|מעגל בגרף]] המתקבל. ...

ב[[תורת הגרפים]], [[גרף בלתי מכוון]] נקרא '''קשיר''' אם קיים [[מסלול (תורת הגרפים)|מסלול]] בין כל שני צמתים בגרף. גרף מכוון נקרא '''קשיר היטב''' (או '''קשיר ...די צמתים שאינם מחוברים כלל לקשתות). קשירות היא גם דרישה בסיסית מ[[עץ (תורת הגרפים)|עץ]]. ...

...ם)|גרף]] או ל[[אלגוריתם חיפוש|חיפוש]] בו. האלגוריתם מוגדר עבור [[גרף (תורת הגרפים)|גרפים בלתי מכוונים ועבור גרפים מכוונים]]. [[קטגוריה:אלגוריתמים בתורת הגרפים|חיפוש לעומק]] ...

...האלגוריתם של ג'ונסון תהיה נמוכה מ-<math>\ O(V^3)</math>, שהיא הסיבוכיות של אלגוריתמים אחרים לפתרון בעיית המסלולים הקצרים ביותר בין כל שני זוגות צמתים, דוגמת [[הא [[קטגוריה:אלגוריתמים בתורת הגרפים]] ...

...וחדת ב[[אלגוריתם|אלגוריתמים]] הקשורים ב[[ראייה ממוחשבת]] וביישומים של תורת הגרפים בתעשייה, למשל לתכנון [[מעגל חשמלי|מעגלים חשמליים]]. '''גרף מישורי''' הוא [[גרף (תורת הגרפים)|גרף]] שאפשר לשכן ב[[מישור (גאומטריה)|מישור]]. שיכון של גרף במישור הוא מודל ...

...אלגוריתם]] חיפוש מונחה [[שיטת חיפוש היוריסטית|היוריסטיקה]] על צומתי [[תורת הגרפים|גרף]] ממושקל, תוך [[אלגוריתם חיפוש|חיפוש]] צומת המקיים תכונה מסוימת (צומת ה [[קטגוריה:אלגוריתמים בתורת הגרפים]] ...

[[קטגוריה:אלגוריתמים בתורת הגרפים|בלמן-פורד]] ...

ב[[תורת הגרפים]], '''רשת זרימה''' היא [[גרף מכוון]], עם שני צמתים מיוחדים: צומת מקור וצומת ...זרימה היא '''[[שיטת פורד-פלקרסון]]'''. השיטה היא סכמה כללית, וקיימים מספר אלגוריתמים, בעלי [[סיבוכיות זמן]] שונה, המממשים אותה. ...

[[קטגוריה:אלגוריתמים בתורת הגרפים|פלויד-וורשאל]] ...

...רימה|זרימה אופטימלית בגרף]]. השיטה היא סכמה כללית, וקיימים מספר [[אלגוריתם|אלגוריתמים]], בעלי [[סיבוכיות זמן]] שונה, המממשים אותה. [[קטגוריה:אלגוריתמים בתורת הגרפים]] ...

...על ידי אנשים רבים. בנוסף למציאת פתרונות לחידה, נחקרו גם מספרם, [[אלגוריתם|אלגוריתמים]] למציאתם וכן [[הכללה (מתמטיקה)|הכללה]] ללוחות שונים. ...רטי של בעיה חשובה ב[[תורת הגרפים]] - מציאת [[מסלול המילטוני]] ב[[גרף (תורת הגרפים)|גרף]]. ...

...קבוצות זרות הוא מימוש של מבנה הנתונים בו כל קבוצה מיוצגת בעזרת [[עץ (תורת הגרפים)|עץ]]. ....1145/62029.62030 |volume=21}}}} שימוש נוסף לדוגמה למימוש אלגוריתמים בתורת הגרפים, הוא מימוש [[האלגוריתם של קרוסקל]] למציאת [[עץ פורש מינימלי]]. ...