תורת הגרפים

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

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

מושגי יסוד של תורת הגרפים

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

במינוח של התיאוריה וכך גם את המושגים הבאים:

Subgraph הוא הגרף, כל הקצוות הקודקודים הם בין הקודקודים וקצוות.

גרף Connected - אחד שיש לו שני שיאים שונים קיימים שרשרת קושרות אותם.

גרף מחובר משוקלל - אחד להגדיר את פונקצית השקלול.

עץ - מחובר גרף בלי מחזורים.

שלד - A subgraph שהינה עץ.

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

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

בין כמה משימות של תורת הגרפים נבדלים:

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

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

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

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