סֵמֶל
יוניונפדיה
תִקשׁוֹרֶת
 Google Play כעת ב-
חָדָשׁ! הורד יוניונפדיה במכשיר אנדרואיד שלך!
חופשי
גישה מהירה יותר מאשר בדפדפן!
 

תורת הגרפים

מַדָד תורת הגרפים

תורת הגרפים היא ענף של המתמטיקה העוסק בתכונותיהם של גרפים. [1]

50 יחסים: מסלול (תורת הגרפים), מעגל (תורת הגרפים), מקרה פרטי, משפט ארבעת הצבעים, משפט רמזי, משפט זרימה מקסימלית - חתך מינימלי, משפט החתונה, מתמטיקה, מטריצת שכנות, מטריצה, מדעי המחשב, מולטיגרף, אלגוריתם, אלגוריתם פלויד-וורשאל, אלגוריתם חיפוש לעומק, אלגוריתם חיפוש לרוחב, אלגוריתם בלמן-פורד, אלגוריתם דייקסטרה, אדם, אינסוף, נוסחת קיילי, סיבוכיות, סיבית, עץ (תורת הגרפים), עץ פורש מינימלי, עיר, קבוצה (מתמטיקה), קודקוד, רשימה מקושרת, תת-קבוצה, לאונרד אוילר, טופולוגיה, חקר רשתות חברתיות, בעיית הסוכן הנוסע, בעיית הדוור הסיני, גאומטריה, גרף (תורת הגרפים), גרף n-צביע, גרף מקרי, גרף מישורי, גרף קשיר, גרף רגולרי, גרף דו-צדדי, דרגה (תורת הגרפים), האלגוריתם של פרים, האלגוריתם של קרוסקל, הגשרים של קניגסברג, היפרגרף, ויקיפדיה, כביש.

מסלול (תורת הגרפים)

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

חָדָשׁ!!: תורת הגרפים ומסלול (תורת הגרפים) · ראה עוד »

מעגל (תורת הגרפים)

בתורת הגרפים, מעגל (באנגלית: Cycle graph או Circular graph) הוא גרף המורכב ממסלול לא-ריק המתחיל ומסתיים באותו צומת, ללא צמתים נוספים. באופן פורמלי, מעגל הוא גרף בעל צמתים \ v_0,\dots,v_, עם הקשתות \ v_i, v_. נהוג לסמן גרף מעגל המורכב מ-\ n קשתות כך: Cn. בגרף Cn מספר הקשתות שווה למספר הצמתים (שווה ל-\ n) ודרגת כל צומת שווה ל-2. כלומר, מכל צומת יוצאות שתי קשתות.

חָדָשׁ!!: תורת הגרפים ומעגל (תורת הגרפים) · ראה עוד »

מקרה פרטי

המונח מקרה פרטי מתייחס לשני מצבים:;מקרה יחיד זהו מצב בו נתונות שתי טענות מהתבנית הבאה.

חָדָשׁ!!: תורת הגרפים ומקרה פרטי · ראה עוד »

משפט ארבעת הצבעים

משפט ארבעת הצבעים הוא תוצאה בולטת בהיסטוריה של הטופולוגיה הקומבינטורית ושל תורת הגרפים.

חָדָשׁ!!: תורת הגרפים ומשפט ארבעת הצבעים · ראה עוד »

משפט רמזי

בקומבינטוריקה, משפט רמזי (באנגלית: Ramsey's theorem) עוסק במבנים המוכרחים להופיע בגרף שלם שהקשתות שלו צבועות בשני צבעים, נאמר אדום וכחול.

חָדָשׁ!!: תורת הגרפים ומשפט רמזי · ראה עוד »

משפט זרימה מקסימלית - חתך מינימלי

בתורת הגרפים, משפט זרימה מקסימלית - חתך מינימלי (Max-flow min-cut) עוסק בזרימה המקסימלית שניתן להעביר ברשת זרימה.

חָדָשׁ!!: תורת הגרפים ומשפט זרימה מקסימלית - חתך מינימלי · ראה עוד »

משפט החתונה

בקומבינטוריקה, משפט החתונה, שמיוחס למתמטיקאי האנגלי פיליפ הול (1935), הוא משפט שמגדיר תנאי הכרחי ומספיק לבחירת נציגים ייחודיים עבור משפחה של קבוצות.

חָדָשׁ!!: תורת הגרפים ומשפט החתונה · ראה עוד »

מתמטיקה

לוח אופייני להרצאה בטופולוגיה אלגברית. מָתֵמָטִיקָה היא תחום דעת העוסק במושגים כגון כמות, מבנה, מרחב ושינוי.

חָדָשׁ!!: תורת הגרפים ומתמטיקה · ראה עוד »

מטריצת שכנות

דוגמה למטריצת שכנות של גרף לא מכוון מטריצת שכנוּת (גם מטריצת סמיכויות או מטריצת שכנויות) היא שיטה לייצוג גרף מכוון בעל n צמתים בעזרת מטריצה ריבועית בגודל n \times n, שערכי תאיה הם 0 או 1.

חָדָשׁ!!: תורת הגרפים ומטריצת שכנות · ראה עוד »

מטריצה

במתמטיקה, מַטְרִיצָה היא מערך דו-ממדי, שרכיביו הם סקלרים, לרוב מספרים, או איברים בחוג כללי יותר.

חָדָשׁ!!: תורת הגרפים ומטריצה · ראה עוד »

מדעי המחשב

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

חָדָשׁ!!: תורת הגרפים ומדעי המחשב · ראה עוד »

מולטיגרף

מולטיגרף בו קיימים שני קודקודים, אשר ביניהן יש שלוש קשתות (אדומות). בתורת הגרפים, מולטיגרף (multigraph, גרף מוכלל) הוא הכללה של גרף, שבה כל זוג צמתים יכולים להיות מחוברים על ידי יותר מקשת אחת.

חָדָשׁ!!: תורת הגרפים ומולטיגרף · ראה עוד »

אלגוריתם

אלגוריתם הוא דרך שיטתית וחד-משמעית לביצוע של משימה מסוימת, במספר סופי של צעדים.

חָדָשׁ!!: תורת הגרפים ואלגוריתם · ראה עוד »

אלגוריתם פלויד-וורשאל

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

חָדָשׁ!!: תורת הגרפים ואלגוריתם פלויד-וורשאל · ראה עוד »

אלגוריתם חיפוש לעומק

סדר סריקת הקודקודים בחיפוש לעומק במדעי המחשב, אלגוריתם חיפוש לעומק (באנגלית: Depth-first search, ראשי תיבות: DFS) הוא אלגוריתם המשמש למעבר על גרף או לחיפוש בו.

חָדָשׁ!!: תורת הגרפים ואלגוריתם חיפוש לעומק · ראה עוד »

אלגוריתם חיפוש לרוחב

סדר סריקת הקודקודים בחיפוש לרוחב אלגוריתם חיפוש לרוחב (אנגלית: Breadth-first search, ראשי תיבות: BFS) הוא אלגוריתם המשמש למעבר על צומתי גרף, לרוב תוך חיפוש צומת המקיים תכונה מסוימת.

חָדָשׁ!!: תורת הגרפים ואלגוריתם חיפוש לרוחב · ראה עוד »

אלגוריתם בלמן-פורד

אלגוריתם בלמן-פורד הוא אלגוריתם הפועל על גרף מכוון וממושקל, ומשמש למציאת המסלול הקל ביותר מצומת אחד מסוים אל כל אחד משאר הצמתים בגרף.

חָדָשׁ!!: תורת הגרפים ואלגוריתם בלמן-פורד · ראה עוד »

אלגוריתם דייקסטרה

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

חָדָשׁ!!: תורת הגרפים ואלגוריתם דייקסטרה · ראה עוד »

אדם

אדם או אדם נבון (שם מדעי: Homo sapiens, בלטינית: "הומו" – אדם, "סָפִּיֶינס" – חושב או תבוני) הוא מין של יונק במשפחת ההומינידיים והמין היחיד שנותר כיום בתת-שבט ההומינינים.

חָדָשׁ!!: תורת הגרפים ואדם · ראה עוד »

אינסוף

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

חָדָשׁ!!: תורת הגרפים ואינסוף · ראה עוד »

נוסחת קיילי

רשימה מלאה של העצים המסומנים על 3,2 ו-4 צמתים נוסחת קיילי היא נוסחה בתורת הגרפים הקובעת שמספר העצים הפורשים של גרף שלם בעל n צמתים הוא \ n^.

חָדָשׁ!!: תורת הגרפים ונוסחת קיילי · ראה עוד »

סיבוכיות

מחלקות סיבוכיות במדעי המחשב, סיבוכיות (complexity) היא כלי מדד מתמטי של משאבי המערכת הנחוצים לפתרון בעיה נתונה באמצעות מחשב.

חָדָשׁ!!: תורת הגרפים וסיבוכיות · ראה עוד »

סיבית

סִבִּית (קיצור של סִפְרָה בִּינָרִית באנגלית bit או בִּיט, מתוך השם "binary digit") היא ספרה בינארית – יחידת הנתונים הקטנה ביותר שבה משתמש המחשב.

חָדָשׁ!!: תורת הגרפים וסיבית · ראה עוד »

עץ (תורת הגרפים)

בעץ שבתמונה יש 6 צמתים, ולכן 5.

חָדָשׁ!!: תורת הגרפים ועץ (תורת הגרפים) · ראה עוד »

עץ פורש מינימלי

left עץ פורש מינימלי (אנגלית: Minimum spanning tree) הוא עץ המורכב מתת-קבוצה של קשתות בגרף נתון ומקיים את התכונות.

חָדָשׁ!!: תורת הגרפים ועץ פורש מינימלי · ראה עוד »

עיר

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

חָדָשׁ!!: תורת הגרפים ועיר · ראה עוד »

קבוצה (מתמטיקה)

קבוצה היא מושג יסודי במתמטיקה.

חָדָשׁ!!: תורת הגרפים וקבוצה (מתמטיקה) · ראה עוד »

קודקוד

בזווית הזאת, הקודקוד הוא הנקודה A בגאומטריית המישור קודקוד הוא נקודה משותפת לשני קצות קטעים או קרניים היוצרים זווית ביניהם.

חָדָשׁ!!: תורת הגרפים וקודקוד · ראה עוד »

רשימה מקושרת

רשימה מקושרת (אנגלית: Linked list) היא אחד ממבני הנתונים הבסיסיים ביותר הנמצאים בשימוש במדעי המחשב, כשמטרתה אחסון נתונים בצורה יעילה.

חָדָשׁ!!: תורת הגרפים ורשימה מקושרת · ראה עוד »

תת-קבוצה

דיאגרמת ון של קבוצה עם תת-קבוצה המוכלת בה בתורת הקבוצות, אומרים שהקבוצה הנתונה \ B היא תת-קבוצה של הקבוצה הנתונה \ A אם כל איבר של הקבוצה \ B שייך גם לקבוצה \ A. (בניסוח פורמלי: לכל \ x\in B מתקיים \ x \in A).

חָדָשׁ!!: תורת הגרפים ותת-קבוצה · ראה עוד »

לאונרד אוילר

לאונרד אוֹילֶר (בגרמנית:; 15 באפריל 1707 - 18 בספטמבר 1783) היה מתמטיקאי ופיזיקאי שווייצרי דגול, שבילה את רוב חייו ברוסיה ובגרמניה.

חָדָשׁ!!: תורת הגרפים ולאונרד אוילר · ראה עוד »

טופולוגיה

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

חָדָשׁ!!: תורת הגרפים וטופולוגיה · ראה עוד »

חקר רשתות חברתיות

חקר רשתות חברתיות היא גישה מדעית לחקר מבנים של יחסים הדדיים בין ישויות.

חָדָשׁ!!: תורת הגרפים וחקר רשתות חברתיות · ראה עוד »

בעיית הסוכן הנוסע

בעיית הסוכן הנוסע - מסלולים קצרים בעיית הסוכן הנוסע (באנגלית: Travelling Salesman Problem ובראשי תיבות: TSP) היא בעיה ידועה בתורת הגרפים ובתורת הסיבוכיות, המעלה את השאלה הבאה: "בהינתן רשימת ערים והמרחק בין כל שתי ערים, מהו המסלול הקצר ביותר, אשר יעבור בכל עיר פעם אחת, ויחזור לעיר ממנה התחיל?". הבעיה נכללת במחלקת הסיבוכיות NP-קשיות, והיא אחת מהבעיות המרכזיות בתחום האופטימיזציה.

חָדָשׁ!!: תורת הגרפים ובעיית הסוכן הנוסע · ראה עוד »

בעיית הדוור הסיני

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

חָדָשׁ!!: תורת הגרפים ובעיית הדוור הסיני · ראה עוד »

גאומטריה

גאומטריה (מיוונית עתיקה: geo.

חָדָשׁ!!: תורת הגרפים וגאומטריה · ראה עוד »

גרף (תורת הגרפים)

גרף לא מכוון בעל 6 קודקודים ו-7 קשתות גרף מכוון בעל 4 קודקודים ו-5 קשתות בתורת הגרפים, גרף הוא ייצוג מופשט של קבוצה של אובייקטים, כאשר כל תת-קבוצה של אובייקטים בקבוצה עשויים להיות מקושרים זה לזה.

חָדָשׁ!!: תורת הגרפים וגרף (תורת הגרפים) · ראה עוד »

גרף n-צביע

בתורת הגרפים, גרף \ n-צביע הוא גרף שאפשר לצבוע את הקודקודים שלו ב-n צבעים, כך ששני קודקודים סמוכים אינם צבועים באותו צבע.

חָדָשׁ!!: תורת הגרפים וגרף n-צביע · ראה עוד »

גרף מקרי

בתורת הגרפים, גרף מקרי הוא גרף הנוצר על ידי תהליך אקראי, או נבחר מתוך התפלגות על מרחב הגרפים.

חָדָשׁ!!: תורת הגרפים וגרף מקרי · ראה עוד »

גרף מישורי

ייצוג גרפי של גרף מישורי בתורת הגרפים, גרף מישורי הוא גרף שניתן לצייר במישור מבלי שהקשתות יחתכו זו את זו (חוץ מאשר בצומתי הגרף).

חָדָשׁ!!: תורת הגרפים וגרף מישורי · ראה עוד »

גרף קשיר

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

חָדָשׁ!!: תורת הגרפים וגרף קשיר · ראה עוד »

גרף רגולרי

גרף 2-רגולרי בתורת הגרפים, גרף רגולרי הוא גרף סופי שבו הדרגה, כלומר מספר הקשתות היוצאות מכל קודקוד, היא קבוע.

חָדָשׁ!!: תורת הגרפים וגרף רגולרי · ראה עוד »

גרף דו-צדדי

דוגמה לגרף דו-צדדי בתורת הגרפים, גרף דו-צדדי (נקרא גם גרף דו-חלקי) הוא גרף שבו ניתן לחלק את הקודקודים לשתי קבוצות זרות, כך שלא קיימת קשת בין שני קודקודים השייכים לאותה הקבוצה.

חָדָשׁ!!: תורת הגרפים וגרף דו-צדדי · ראה עוד »

דרגה (תורת הגרפים)

גרף לא מכוון בו מצוינות דרגות הקודקודים בתורת הגרפים, דרגה של צומת מתארת את מספר הקשתות המקושרות לצומת מסוים.

חָדָשׁ!!: תורת הגרפים ודרגה (תורת הגרפים) · ראה עוד »

האלגוריתם של פרים

דוגמת הרצה של האלגוריתם של פרים האלגוריתם של פרים הוא אלגוריתם חמדן המשמש למציאת עץ פורש מינימלי בגרף ממושקל לא מכוון.

חָדָשׁ!!: תורת הגרפים והאלגוריתם של פרים · ראה עוד »

האלגוריתם של קרוסקל

האלגוריתם של קרוסקל הוא אלגוריתם חמדן לפתרון בעיית מציאת עץ פורש מינימלי בגרף ממושקל קשיר לא מכוון, שתואר לראשונה במאמר של ג'וזף קרוסקל בשנת 1956.

חָדָשׁ!!: תורת הגרפים והאלגוריתם של קרוסקל · ראה עוד »

הגשרים של קניגסברג

בעיית הגשרים של קניגסברג היא חידה מפורסמת עם השפעה מכרעת על ההיסטוריה של המתמטיקה.

חָדָשׁ!!: תורת הגרפים והגשרים של קניגסברג · ראה עוד »

היפרגרף

היפרגרף (אנגלית: Hypergraph) הוא הכללה של גרף, שבה כל קשת יכולה לחבר יותר משני צמתים.

חָדָשׁ!!: תורת הגרפים והיפרגרף · ראה עוד »

ויקיפדיה

ויקיפדיה (באנגלית: Wikipedia) היא אנציקלופדיה מקוונת המבוססת על תוכן חופשי ומשתמשת בטכנולוגיית ויקי.

חָדָשׁ!!: תורת הגרפים וויקיפדיה · ראה עוד »

כביש

כביש רומי בעמק האלה ("דרך הקיסר") סלילת כביש בתחילת שנות ה-30 של המאה ה-20 בהוד השרון כבישים במרכז תל אביב כביש הוא נתיב תחבורה סלול - לרוב באספלט או בטון - המשמש לתנועת כלי תחבורה.

חָדָשׁ!!: תורת הגרפים וכביש · ראה עוד »

מפנה מחדש כאן:

קשת (תורת הגרפים), גרף פשוט.

אזכור

[1] https://he.wikipedia.org/wiki/תורת_הגרפים

יוֹצֵאנִכנָס
היי! אנחנו בפייסבוק עכשיו! »