په کمپيوټر ساينس ګراف: تعريف، ډولونه، د غوښتنلیک مثالونه. په کمپيوټر ساينس ګراف تيوري

د ټاکلو اړیکې په کمپيوټر طريقه شمېري دي عناصر ګډو. دا د په مطالعه اساسي شيانو ګراف تيوري.

اساسي تعریفونه

په کمپيوټر ساينس ګراف څه شی دی؟ په دي کې د شيانو په نامه غوټو يا څوکې، د ځينو جوړو یې د M وصل دي زياتره. N. ضلع. د مثال په توګه، په انځور کې (الف) د ګراف د څلورو غوټو څخه جوړه ده، د A، B، C، D، چې د B د ده د نورو درې څوکې ضلع هر نښلول، او د C او D هم سره وصل denoted. دوه غوټې له څنګ نه دي که يوه څنډه له خوا وصل دي. دغه رقم د څنګه په کمپیوټر ساینس د ګرافونو جوړولو عادی لاره په ګوته کوي. کړیو د څوکو او د مزو د هغوی هر جوړې سره نښلوي استازیتوب کوي، دي د سفلی.

په کمپيوټر ساينس څه undirected ګراف دی؟ هغه د سفلی د دواړو تر منځ د اړیکو پای دي symmetrical. ضلع په ساده ډول يې له يو بل سره نښلوي. په ډیرو مواردو کې، که څه هم، دا د نابرابرو اړیکو د څرګندولو ضروري ده - د مثال په توګه، چې د یوه ټکي ته د B، خو نه برعکس. دا موخه په کمپيوټر د ګراف د تعریف دی، تر اوسه د سره د الرښوونه څنډو ټولګه کې د غوټې يوه ټولګه لري. هر لرونکې څنډه ده د څوکې د چا لور لري مانا تر منځ اړیکی. الرښوونه ګراف انځوروي، لکه چې په انځور (ب) کې ښودل شوي، د خپلو څنډو له خوا غشي استازيتوب دي. کله چې تاسو غواړئ چې دې ټینګار کوي چې د غیر directional ګراف، دا په نامه undirected.

شبکې د نمونې

په کمپيوټر ساينس ګرافونه دي محاسبوي مودل د شبکو د جوړښت. لاندې شکل په ګوته کوي چې د انټرنټ د جوړښت، نو د ARPANet، د نوم پيدا شو په دسمبر 1970، کله چې هغې یوازې 13 ټکي وو. د غوټو د پروسس مرکزونه دي او د سفلی د دوه څوکې feedforward therebetween سره ونښلوي. که تاسو پام نه ورکوي چې د متحده ایالاتو د نقشه تحمیل، د انځور پاتې ده یوه 13 غوټه ګراف د تېر یو ته ورته. په دې صورت کې د هغه څوکه چې اصلي مقام ضروري نه ده. دا مهمه ده چې د غوټې له يو بل سره وصل دي.

په کمپيوټر ګراف کاریال ته اجازه ورکوي چې وګوري کارونه څنګه دي یا په فزیکي یا منطقي په شبکې يو جوړښت وصل. 13-غوټه د ARPANet د مخابراتو شبکې د یو مثال په توګه په کوم کې سر ته کمپيوټرونه او یا نورو وسیلو کولای پېغامونه انتقال دی، او د هغې څنډو ته مستقیم مخونه چې معلومات خپرېږي شي استازيتوب وکړي.

لارو

که څه هم د ګراف په ډېرو مختلفو سیمو کې کارول شوي دي، دوی عام ځانګړنې لري. ګراف تيوري (کمپيوټر ساينس) ښايي شامل دي چې د دوی تر ټولو مهم - مفکوره چې کارونه اکثره په څنډو کې حرکت کوي، نښلو له غوټه ته غوټه حرکت، يو مسافر يو څو الوتنې یا معلوماتو په یوه ټولنیز جال د يوه کس څخه بل کس خپرېږي، یا د کارونکي دا وي کمپيوټر، په دوامداره توګه له خوا تړنې لاندې د ويب پاڼو شمېر ليدنه.

دغه مفکوره په توګه د غوټې له خوا څنډو سره وصل د يو لړ د مسير د تعریف هڅوي. کله کله دا ضروري ده چې د لارې چې نه يوازې د برخې لري، بلکې د څنډو په ترتیب د هغوی سره نښلوي په پام کې. د مثال په توګه، د څوکې MIT، BBN، د RAND په ترتیب، UCLA کې د ARPANet انټرنټ ګراف يوه لار ده. د غوټو او څنډو ترهګرو ښايي تکرار شي. د مثال په توګه، SRI، Stan، UCLA، SRI چې، د یوتا، MIT هم يوه لار ده. په لاره کې چې د ضلع تکرار نه شي، يو ځنځير په نامه. که د غوټو په تکرار نه شي، چې دا يوه ساده کړۍ په نامه.

دورو

په کمپيوټر ګراف په ځانګړي ډول مهمې نوعې - دا دورو چې د حلقوي جوړښت استازيتوب کوي، لکه د غوټو LINC، په صورت کې، CARN، HARV، BBN، MIT، LINC يو ترتيب. سره لږ تر لږه درې سفلی، په کوم کې چې د لومړي او تېر غوټه شان دي، او د نورو لارو توپير لري، د کمپیوتر ساینس راڅرګندېدل ګراف استازيتوب وکړي.

مثالونه: SRI دوران، Stan، UCLA، SRI چې په لنډه، او سریلانکا، Stan، UCLA، د RAND، BBN، یوتا، SRI چې د پام وړ زیات.

ريښتيا د ګراف په هره څنډه د ARPANet د دوران پورې اړه لري. دا کار په قصدي ډول، د هغوی هر ډول ونشي که، به له يو غوټه بل ته د انتقال د امکان. په مخابراتو او ترانسپورت د سیستم دورو لپاره اضافي زېرمتونونه حاضر - هغوی د يو بل د دوران لاره د بدیل لارو برابر کړي. د ټولنیزو شبکو اکثرا د پام وړ دورو. کله چې تاسو د موندلو، د مثال په توګه، چې د خپلې ښځې د تره زوی د يوه نږدې ښوونځي ملګري په حقيقت کې له خپل ورور سره کار کوي، چې دا د یوې دورې له چې د تاسو څخه جوړه، ستا ښځه، د هغې د تره زوی، چې له ښوونځي څخه د خپل ملګري، د هغه کارمند (يعنې. E. ستاسو ورور)، او په پای کې تاسو بیا.

Connected په ګراف: تعریف (کمپيوټر ساينس)

دا طبیعي ده چې حيران چې آيا دا ممکنه ده څخه په هره غوټه ته کوم بل غوټه ترلاسه کړي. د ګراف دی وصل که د څوکې هره جوړه تر منځ لاره کې شته. د مثال په توګه، د ARPANet دجال - وصل ګراف. په همدغه شي د مخابراتو او ترانسپورت د شبکې اکثریت په اړه وويل شي، ځکه د هغوی موخه دا ده چې له يو بل غوټه د ترافيکو الرښود کړي.

له بلې خوا، نه شته چې تمه لرو چې په کمپيوټر ساينس ګراف دا ډول دي په پراخه کچه په قیاسي دلیل. د مثال په توګه، په ټولنیز جال د نه دوه کسان چې د يو بل سره تړلي نه تصور ستونزمن دی.

برخې

که د کالم د کمپیوټر سره نه تړل، هغوی په طبيعي ته د اړوندو ټوټې، د غوټو چې ګوښه کیږي او تېرېږي، نه ډلو ټولګه راځي. د مثال په ډول، شکل داسې درې برخو په ګوته کوي: - د A او B، دوهم - د لومړي C، D، E، او دريم د پاتې څوکې لري.

د ګراف برخې استازیتوب د غوټو گنل، چې:

• هر هغه څوکه چې ضمني بل هر يوه لاره لري؛
• گنل د یوه لوی ټولګه کې چې په هره غوټه بل هر يوه لاره لري برخه نه ده.

کله چې په کمپيوټر کې د ګراف په خپلو برخو ویشل شوي دي، چې دا یوازې د خپل جوړښت ميتود لومړنۍ Description. دا برخه ښايي د داخلي جوړښت کې د شتمن وي، دا د دې شبکې د تفسیر مهم دي. د مثال په توګه، د يو غوټه ارزښت ټاکلو رسمي میتود تر څو معلومه برخو څومره به د شمېرنې وېشل شي، که هغه غوټه ده لرې ده.

اعظمي جز

د اتصال برخې کیفي ارزونه يوه طريقه ده. د مثال په توګه، سره دوه د خلکو تر منځ د اړیکو د نړۍ ټولنیز جال د شته دی، که دوی ملګري دي.

آیا دا وصل؟ ښایي نه. د اتصال - بلکې نازک ملکیت، او د یوه غوټه (يا يې د يوه کوچنۍ ټولګه) د چلند کولای شي چې دا هيڅ کم کړي. د مثال په توګه، د ژوند ملګري نه يو نفر د يو جز د يو واحد د څوکې څخه جوړه ده، او له همدې امله، د شمېرنې به نه تړل شي. او له ليرې حاره ټاپو، د خلکو سره د بهرنۍ نړۍ سره اړیکه نه لري شامل دي، به هم د شبکې، چې د خپلو شنونکی تاییدوي يوه کوچنۍ برخه وي.

د دوستانو د نړیوالې شبکې

خو بل څه نشته. د مثال په توګه، د مشهور کتاب يوه لوستونکی ملګري چې په نورو هېوادونو کې کرل پورته لري، او هغوی ته کوي یو جز. که موږ د دغو دوستانو او د خپلو ملګرو سره د مور او پلار په پام کې ونیسي، د دغو ټولو خلکو په همدې برخه هم دي، که څه هم دوی به هیڅکله د لوستونکي په اړه اورېدلي، خبرې بله ژبه، او بل دا هيڅکله هم. په دې ډول، که څه هم د دوستۍ د نړیوالې شبکې - سره نه تړل، لوستونکی به په جز کې شامل شي دي ډير زيات وي، چې د نړۍ، چې له بیلابیلو شالید خلک شامل دي په ټولو برخو کې نفوذ، او په حقیقت کې، لري د نړۍ د نفوس د پام وړ برخه.

همدغه واقع په شبکې ارقامو سټونه - لوی، پیچلې شبکې اکثرا په اعظمي جز، په کوم کې چې د ټولو غوټو د پام وړ تناسب لري. سربیره پردې، کله چې په شبکه کې په اعظمي جز شامل دي، دا تقريبا د تل لپاره یوازې یو دی. پوه شي چې ولې، دا ضروري بېرته د يو د دوستۍ د نړیوالې شبکې د مثال ته لاړ شي او هڅه وکړي چې د دوه اعظمي برخې، چې هر يو د میلیونونو خلکو شامل دي د شتون تصور دی. دا ته اړتيا لري تر څو د لومړي جز ځينو ته د دويمې د يوې واحدې ضلع ته اعظمي دوه برخې ته یو مدغم لري. یوازې یو څنډه راهیسې، په ډيرو مواردو کې دا ناشوني ده چې دا نه وه جوړه، او له همدې امله په دریښتینو شبکو اعظمي دوه برخې نه لیدل کیږي.

په ځينو نادرو قضیو کې، کله چې د دوه برخې د حد اکثر ګډ شتون په يوه رښتينې شبکې د اوږدې مودې لپاره، د هغوی د اتحاديې ناڅاپي، ناببره وه، او، په پای کې، عواقب او پايلې لري.

پيښې جز ديونوي

د مثال په توګه، په اړه یو نیم زر کاله وړاندي د ينګ د تمدن د اروپایی کاشفانو له رارسېدو وروسته، هلته یو نړیوال cataclysm وه. د شبکې د نقطې نظر څخه، داسی ښکاریده لکه: د نړۍ ټولنیز جال د پنځه زره کاله، ښایي د دوه giant برخه جوړه - یو په شمالي او جنوبي امریکا او د نورو - په ایروایشیا کې. د دې امله، چې د ټکنالوژۍ په دوه برخو څخه په خپلواکه توګه وده کړې، او، هم بد، په توګه جوړ او د بشر د ناروغۍ، او داسې نور. D. کله چې د دوه برخې په پای کې په چټکۍ سره په تماس کې تکنالوژي او يوه ناروغۍ ترلاسه او disastrously overflowed دوهم.

د امریکا د عالي لېسه

د اعظمي جز مفهوم لپاره د يوه ډېر کوچني مقیاس د شبکو په اړه استدلال ګټور دي. یوه په زړه پورې بېلګه ده یو ګراف په 18 میاشتو مودې لپاره د امریکا د لوړ ښوونځي د اړیکو انځوروي. حقیقت دا دی چې دا د اعظمي برخه لري اړینه ده کله چې د ناروغیو د خپریدو، جنسي لېږدنده-ناروغيو، چې د ده د مطالعې په موخه راځي. زده کونکي کولي شي چې د وخت په موده کې خو یوازې یو ملګری درلود، خو،، پرته د تحقق په دا، د حد اکثر د برخو او اجزاو برخه شوي دي، او له همدې امله، د انتقال څو د احتمالي لارو يوه برخه ده. د دغو جوړښتونو تعلق چې ښايي د اوږد پای ته منعکس کوي، خو د دوی په ډېر اوږد زنځيرونه افرادو سره نښلوي، چې د سختو کره او خپروی موضوع وي. سره له دې، دوی دریښتینو دي: څنګه ټولنیز حقایق دي پټ، خو اوموقتي macrostructures د انفرادي منځګړیتوب د یوه محصول په توګه راڅرګند شول.

فاصله او پراخه-لومړي لټون

په دې اړه چې ایا د دوو غوټو لارې وصل دي د معلوماتو د پردې برسیره، په کمپيوټر ساينس ګراف تيوري تاسو ته اجازه درکوي خپل د اوږدوالي په اړه زده کړي - په ترانسپورت، ارتباطاتو او یا د خبرونو او د ناروغيو د خپرولو، او همدارنګه که دا څو څوکې يا څو له لارې ځي.

د دې، د يو لاره په اوږدوالي سره برابر د ګامونو شمېر چې له پای پيل لري، يعنې د تعریف کړي. ج په تعاقب چې ده څنډو شمیره. د مثال په توګه، MIT، BBN، د RAND، UCLA په مسیر کې د 3 په اوږدوالي لري، او د MIT، یوتا - 1. د لور د اوږدوالي په کارولو سره، موږ کولای شو، چې که د دوو غوټو کې له يو بل سره او یا تر اوسه واټن د دوه څوکې تر منځ د نږدې کالم ترتيب شوي دي تعریف د اوږدوالي په توګه د دوی تر منځ د ټولو لنډه لاره ده. د مثال په توګه، د LINC او سريلانکا ترمنځ د واټن 3، که څه هم، د دې ډاډ، دا ضروري ده چې د 1 يا 2، therebetween د اوږدوالي مساوي نه شتون تایید کړي ده.

پراخه-لومړی د لټون الګوریتم

د کوچني ګراف واټن د دوو تر منځ د غوټو محاسبه په اسانۍ سره. خو د پیچلې ده د واټن معلومولو يو سيستماتيک ميتود لپاره د اړتيا.

تر ټولو طبيعي لاره دا کار، او له همدې امله، د ټولو اغېزمنه لاندې (د مثال په توګه، د یو نړۍ د دوستانو شبکه) دی:

• ټول ملګري اعلان شوي دي د 1 په واټن پروت دی.
• د ملګرو ټول ملګري (نه د شمېرنې د مخکې ذکر) په واټن 2 اعلان شوي دي.
• خپل ټول ملګري (بيا، د لیبل د خلکو نه د شمېرنې) پر پرتو واټن 3 اعلان کړ.

پر پخواني یو واحد په - په دې لاره د دوام، د لټون په ورپسې طبقو ترسره کړل، چې د هر. هر نوی طبقه د غوټو چې په پخوانيو هغو نه ګډون جوړ، او دا چې د تېر طبقه د څوکې څخه څنډې راځي.

دا تخنیک د يوه پراخه-لومړی د لټون په نامه، لکه څرنګه چې هغې د کالم لپاره د لومړنيو غوټه پلټنې، اساسا پوښښ په راتلونکو. د واټن د معلومولو لپاره يوه طريقه د برابرولو سربېره، نو کولای شي په توګه يو ګټور تصوری چوکاټ چې د ګراف جوړښت او همدارنګه څنګه چې د کمپيوټر د يو ګراف جوړولو تنظيم خدمت وکړي، چې پر بنسټ له یو ثابت د پیل ټکی خپل واټن د ترسره شوي دي.

پراخه-لومړی د لټون کولای شي نه يوازې چې د ملګرو یوه شبکه، خو هم د هر ګراف استعمال شي.

کوچنۍ نړۍ

که تاسو ته د ملګري د نړیوالې شبکې بېرته پر شا تللای، تاسو وګورئ، چې د استدلال چې د تشریح تر اعظمي جز پورې رښتيا تصويب څه مطلب: يوازې لوستونکی نه دوستانو ته ددې لارې لري، سره د نړۍ د نفوس د پام وړ تناسب د هغه سره نښلوي، خو په دې لارو دي حیرانتیا لنډ .

دا مفکوره ده د "کوچنۍ نړۍ پدیده" نومیږی: د نړۍ کوچني ښکاري، که تاسو د هغه څه په اړه يو لنډ لاره هر دوه تنه سره نښلوي فکر.

د "شپږ د ترلاسه" تيوري لومړي ځل لپاره د 1960s له خوا سټنلي Milgram او د هغه ملګرو experimentally وڅیړل. پرته د ټولنیز جال د معلوماتو د هر ډول د ټاکلو، او د 680 $ بودجه، هغه پرېکړه وکړه چې د يو نامتو مفکوره وګورئ بهر. د دې لپاره، هغه وپوښتل: 296 تصادفي توګه غوره initiators هڅه وکړي تر څو د stockbroker، چې د باسټن د يو په اطرافو کې ژوند یو لیک واستوي. Initiators په موخه (په شمول د ادرس او مسلک) په اړه ځينې شخصي معلومات ورکړل شوي دي، او بايد هغوی يې هغه کس چا کوله چې پوهېدل په نوم ته یو لیک واستوي، د همدې لارښوونې، له دې امله چې دا په موخه ژر تر ژره رسیدلی. هر لیک د د دوستانو د یو شمیر په لاس له لارې تصویب او جوړه يو ځنځير د بوستون د بهر لپاره د سټاک دلالانو بندوي.

په منځ کې 64 د ځنځیر چې هدف ته رسيدلي دي، په اوسط ډول په اوږدوالي د شپږ و، د نوم د دوو لسيزو په لومړيو کې د لوبو Dzhona Gera سرليک شمېر تاييدوي.

سره سره د دغه څېړنې د ټولو نيمګړتياوو، د تجربه ښودلې زموږ د ټولنیزو شبکو تفاهم یو ډېر مهم اړخ. په راتلونکو کلونو کې چې ورپسې له هغې څخه جوړ شو پراخ پایله: ټولنیزو شبکو ميلان لري ترڅو د خلکو د خپل سر جوړو تر منځ ډېر لنډ لارو لري. او که څه هم سره د سوداګرۍ د مشرانو او سیاسي مشرانو لکه غیر مستقیم تړاو د ځان لپاره هره ورځ پيسې نه، د دا ډول لنډ لارو د شتون غږوي رسی فرصتونه کې د معلوماتو د خپرولو، د ناروغيو او په ټولنه کې د ناروغۍ د نورو ډولونو په سرعت کې زيات رول، او همدارنګه چې د ټولنیزو شبکو د خلکو سره کوي برعکس کیفیت خورا.