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