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