مقاطع تحصیلی
جستجو در منظومه
مسئله: سؤال دیگری مطرح کنید که با دیدن نمودار ِ گراف مثال قبل بتوان به آن جواب داد.همان طور که دیدیم یک گراف متشکل است از مجموعه ای از نقاطو مجموعه ای از پاره خط ها، که به هر یک از این نقاط رأس و به هریک از پاره خط ها یال می‌گوییم. توجه کنید که یال ها الزم نیست حتماًپاره خط راست باشند و می‌توانند به صورت منحنی نیز باشند و در هرِ سر یال باید رأسی قرار داشته باشد. همان طور که دیدیم یک گراف رامی‌توان با رسم ِ نمودار آن نشان داد و نیز می‌توان آن را با نمادهای Gریاضی معرفی کرد. در ادامه به شکلی ساده چند تعریف مقدماتی و شکل 5ٔ نحوه نمایش یک گراف را بررسی می‌کنیم.گراف G را با 9 رأس و 10 یال، مانند شکل ،5 در نظر می‌گیریم و با بررسی آن برخی تعاریف را نیز مطرح می‌نماییم.با توجه به اینکه یک گراف مجموعه ای از رئوس 1 و یال هاست می‌توان به جای نمایش آن با شکل باال، با نمادهای ریاضیٔ مجموعه یال ها و رئوس آن را به صورت زیر نمایش داد.} 9 v, 8 v, ..., 2 v, 1 v { = 2 V(G) ٔ مجموعه رأس های گراف G} 8 v 7 v, 8 v 6 v, 7 v 5 v, 6 v 4 v, 5 v 4 v, 5 v 2 v, 3 v 2 v, 8 v 1 v, 4 v 1 v, 2 v 1 v { = 3 E(G) ٔ مجموعه یال های گراف Gبه وضوح، با داشتن ِ شکل گراف، شما می‌توانید مجموعه های V(G) و E(G) را بنویسید و همچنین با داشتن دو ٔ مجموعهV(G) و E(G) می‌توانید ابتدا به تعداد n(V(G) ()تعداد اعضای ٔ مجموعه V(G) که آن را با V(G) نیز نمایش می‌دهیم)نقطه (رأس) مشخص نمایید و سپس با توجه به E(G) رأس های متناظر را به هم وصل نمایید.همان طور که در مثال تیم های فوتبال مالحظه کردید گاهی اوقات الزم است برای یال ها جهت تعیین کنیم.به گرافی که برای یال های آن جهت تعیین شده باشد، گراف جهت دار می‌گوییم. در این حالتبرای نمایش اینکه جهت یک یال از سمت کدام رأس به سمت کدام رأس است یال ها را با زوج مرتبنمایش می‌دهیم. به طور مثال ٔ مجموعه رئوس و یال های گراف جهت دار شکل 6 را این گونه نمایشمی‌دهیم.} V = { a, b, c, d } E { (a, b(, ) a, c(, ) c, a() d, b) شکل 6کار در کالســ دو ٔ مجموعه V(G) و E(G) به صورت زیر داده شده اند. با توجه به آنها شکل گراف مورد نظر را بکشید.} d, c, b, a { = V(G()ب } 6 v, ..., 2 v, 1 v { = V(G()الف} E(G) = { v 1 v 4, v 2 v 5, v 6 v 1, v 5 v 1 } E(G(= {)a, b(, )b, c(, )c, b(, )c, d(, )d, a)ــ1 مجموعه رئوس گراف همواره ناتهی در نظر گرفته می‌شود.Edge 3 ــ Vertex 2 ــفصل دوم: گراف و مدل سازی 34