Информатика графиктер: анықтамасы, түрлері, қолдану мысалдары. информатика графтар теориясы

қарым-қатынас анықтау үшін компьютерлік әдісі саналады аралас элементтері болып табылады. Бұл зерттеу негізгі объектілері болып графтар теориясы.

негізгі анықтамалар

информатика диаграммада не? Ол м байланысты кейбір жұп, оның түйіндері немесе шыңдары деп аталатын объектілер көптеген қамтиды. Н. қабырғаның. Мысалы, суретте график (а) төрт тораптар тұрады, басқа да үш шыңдары қабырғаның әр қосылған, және С және D, сондай-ақ қосылған B, оның A, B, C, және D таңбалау. олар шетіне арқылы қосылған болса, екі түйіндері іргелес болып табылады. көрсеткіш информатика графиктер салу қалай типтік жолын көрсетеді. Шеңбер, шыңдары және олардың әрқайсысы жұп жалғастыратын сызықтарды білдіреді қабырғалары болып табылады.

информатика бағытталмаған қандай график деп аталады? қабырғаның екі ұшына арасындағы Ол қарым-қатынас симметриялы болып табылады. Қабырға жай бір-бірімен оларды байланыстырады. В А нүктелері деп, бірақ керісінше емес, мысалы - Көптеген жағдайларда, алайда, бұл асимметриялық қарым-қатынас білдіру қажет. Бұл объективті компьютерде Графиктің анықтау болып табылады, әлі күнге дейін бағытталған шетінен жиынтығымен түйіндерінің жинағынан тұрады. Әрбір бағдарланған Edge бағыт мағынаға ие шыңы арасындағы байланыстырушы буын болып табылады. (Б), олардың шеттері көрсеткі ұсынылған суретте көрсетілгендей бағытталған графтар, бейнелейді. Сіз бұл бағытталмаған графикті ерекше атап өткім келеді кезде, ол бағытталмаған деп аталады.

желілік модельдері

информатика графиктер математикалық моделі желілік құрылымдардың. Келесі суретте Интернет құрылымын көрсетеді, содан кейін ол тек 13 ұпай болды желтоқсан 1970 жылы, ARPANET атауын туды. түйіндері өңдеу орталықтары болып табылады және қабырғалары екі шыңдары Предуправление Санағыш қосыңыз. Америка Құрама Штаттары картасын салған үшін сіз назар аудару жоқ болса, суреттің қалған алдыңғы біріне ұқсас 13-түйіні график болып табылады. Бұл жағдайда, биіктердің нақты позиция маңызды емес. Бұл түйіндер бір-бірімен қосылған, ол үшін маңызды болып табылады.

компьютерге Графтар қолдану заттар, не физикалық немесе логикалық өзара байланысты желі құрылымында қаншалықты көруге мүмкіндік береді. 13-түйіні ARPANET жоғарғы компьютерлер немесе басқа да құрылғылар хабарларды жіберу алатын байланыс желісінің үлгісі болып табылады, және жиектер ақпарат берілуі мүмкін тікелей сілтемені білдіреді.

бағыттар

графиктер көптеген түрлі салаларда пайдаланылады да, олар ортақ ерекшеліктері бар. Графтар теориясы (информатика) олардың, бәлкім, ең маңызды қамтиды - заттар жиі дәйекті әрбір торап қозғалатын, шетіне жылжыту идеясы, бұл, ол әлеуметтік желіде адамның, немесе пайдаланушыға адамға берілетін бірнеше рейстер немесе ақпарат жолаушы болуы дәйекті сілтемелер арқылы веб-беттердің санын бару компьютер,.

Бұл идея жиектерінен қосылған торап сериясы ретінде маршруттың анықтамасын ынталандырмайды. Кейде ол компоненттер ғана емес бар маршрут, сондай-ақ оларды байланыстыратын шетінен ретін қарастыру қажет. Мысалы, биіктерге MIT, BBN, RAND, UCLA тізбегі ARPANET интернет бағанында маршрут болып табылады. тораптар мен жиектер өту қайталануы мүмкін. Мысалы, ҒЗИ, STAN, UCLA, ҒЗИ, UTAH, MIT сондай-ақ маршрут болып табылады. қабырғалары қайталанатын емес онда жолы, тізбегін деп аталатын. түйіндер қайталанатын емес болса, онда ол қарапайым тізбек деп аталады.

циклдар

компьютерлік графиктер әсіресе маңызды түрлері - тораптар сияқты LINC, CASE, Carn, HARV, BBN, MIT, LINC дәйектілігі ретінде сақина құрылымын білдіреді, ол цикл. кем дегенде үш түйіні бірінші және соңғы сол болып табылатын қабырғаның, және қалған бағыттар, әр түрлі информатика циклдік графиктер білдіреді.

Мысалдар: SRI цикл, STAN, UCLA, ҒЗИ қысқа болып табылады, және ҒЗИ, STAN, UCLA, RAND, BBN, UTAH, ҒЗИ айтарлықтай үлкен.

Графиктің Іс жүзінде әрбір ARPANET Edge цикл тиесілі. Олардың кез келген, бір түйіннен екіншісіне көшу мүмкіндігі болады сәтсіз болса, бұл, әдейі жасалды. байланыс және көлік жүйелерінде циклдар резервтеу үшін бар - олар басқа цикл жолына балама бағыттарды қамтамасыз етеді. әлеуметтік желілер жиі байқалады циклдар. Егер сіз әйелі бөлесі жақын мектеп досы шын мәнінде сіздің ағасы жұмыс істейді, мысалы, тапқан кезде, ол, сіздің әйелі, оның немере ағасы, мектептен оның досы, оның қызметкері (яғни. E. сізде тұратын цикл ағасы), және, ақырында, сіз қайтадан.

Қосылған Graph: анықтамасы (информатика)

Ол кез келген басқа түйіннің жету әрбір торап болады ма білгім табиғи болып табылады. биіктерге әр жұптың арасында жолы бар болса, график қосылған. Мысалы, ARPANET желісі - қосылған Graph. олардың мақсаты бір түйіннен трафикті бағыттау болып табылады бірдей, байланыс және көлік желілерін көпшілік туралы айтуға болады.

Екінші жағынан, информатика графиктер осы түрлері кеңінен таралған деп априори себеп жоқ. Мысалы, әлеуметтік желі бір-біріне қатысы жоқ екі адам елестету қиын емес.

компоненттері

баған компьютерге қосылмаған болса, олар, әрине, оқшауланған болып табылады және қиылысатын емес, түйіндер топтар, байланысты жиынтыққа үзінділер түседі. Мысалы, сурет үш мұндай бөліктерін көрсетеді: бірінші - А және В, екінші - C, D және Е, және үшінші қалған биіктерге тұрады.

Графиктің компоненттері, онда тораптар жиынын білдіреді:

• әрбір шыңында топ кез-келген басқа бір маршрут бар;
• Ішкі жиын әрбір торап кез келген басқа бір маршрут бар, онда үлкен жиынтығы бөлігі болып табылады.

компьютерге графиктер олардың құрамдас бөлінеді кезде, ол олардың құрылымы әдісін тек бастапқы сипаттамасы болып табылады. Бұл компонент, ол желі түсіндіру үшін маңызды болып табылады, ішкі құрылымын бай болуы мүмкін. Мысалы, торап маңыздылығын анықтау ресми әдісі торап жойылған болса, санын бөлуге болады қанша бөліктері анықтау болып табылады.

Ең компонент

Жалғауға компоненттерін сапалы бағалау әдісі бар. олар достар болса, мысалы, екі адам арасындағы байланыс бар бүкіл әлемде әлеуметтік желі, бар.

ол қосылған? Мүмкін емес. Connectivity - өте нәзік, жылжымайтын мүлік, және бір түйіннің (немесе олардың шағын жиынтығы) мінез-құлқы ештеңе оны азайтуға болады. Мысалы, ешқандай тірі достарыңызбен бір адам бір биіктердің тұратын құрамдас бөлігі болып табылады, сондықтан, саны байланысты болады. Немесе сыртқы әлеммен байланыс жоқ адамдар тұратын қашықтағы тропикалық арал, сондай-ақ, оның incoherence растайды желісін, шағын компоненті болады.

достар Ғаламдық желі

Бірақ тағы бір нәрсе бар. Мысалы, танымал кітаптың оқырман басқа елдерде дейін өсті достары бар, және оларға бір компонентін құрайды. біз назарға осы достары ата-аналар мен олардың достарына алатын болсақ, барлық бұл адамдар сол компонент, сондай-ақ бар, олар оқырманға туралы ешқашан естімегенмін, бірақ, түрлі тілде сөйлейтін, және оған келесі ешқашан болған емес. Осылайша, достық жаһандық желіге дегенмен - байланысты емес, ізін оқу құрылғысы Бөлік енгізілетін болады көптеген әр түрлі ортадан шыққан адамдарды қамтитын, әлемнің барлық бөліктеріне еніп, өте үлкен болып табылады және, шын мәнінде, әлемдік халықтың елеулі бөлігін қамтиды.

бірдей желілік деректер жиынымен орын - ірі, күрделі желілер жиі барлық тораптар елеулі үлесін қамтитын барынша компоненті бар. желілік максималды компоненттерін қамтиды кезде Сонымен қатар, ол әрдайым дерлік бір ғана болып табылады. Түсіну үшін, неге ол кері достық жаһандық желісінің мысалы өтіңіз және миллиондаған адамдардың қамтиды, олардың әрқайсысы екі максималды компоненттерін, болуын елестету тырысу керек. Ол бір біріктірілді максималды екі құрамдас үшін екінші бірінші компоненті кейбір бір қабырғасын болуы қажет. тек бір шетінен бастап, көп жағдайда ол құрылған жоқ деп екіталай, және, демек, нақты желілерде ең көп екі компоненттер байқалады ешқашан.

Кейбір сирек жағдайларда, нақты желісінде ұзақ уақыт бойы тең болған ең үлкен екі компоненттері, олардың одағы, күтпеген драмалық, және, сайып келгенде болды, апатты салдары болуы кезінде.

Жазатайым компонент біріктіру

Мысалы, шамамен жарты мыңжылдықтың бұрын Батыс жарты шарда өркениетіндегі Еуропалық зерттеушілердің келгеннен кейін, жаһандық тақаған болды. желі тұрғысынан, бұл көрінгенімен: жаһандық әлеуметтік желінің бес мың жыл, бәлкім, екі алып компонент тұрды - Солтүстік және Оңтүстік Америкада бір, және басқа да - Еуразиядағы. екі компоненттері, сайып келгенде, сенсорлық технология және тез және апаттық екінші етек жайды аурулар алды кезде осы себепті, технология екі құрамдас дербес дамыды, және, тіпті нашар, дамыған, сондай-ақ адам аурулары және т.б.. D. отыр.

Америкалық High School

барынша компоненті тұжырымдамасы әлдеқайда аз ауқымда желілер туралы пайымдау үшін пайдалы болып табылады. Қызықты мысал 18 ай мерзімге АҚШ жоғары мектепте тәуелділікті суреттейді бағандары болып табылады. ол аурулардың таралуына келгенде, ол барынша компоненті бар, бұл факт зерттеу мақсаты болып табылатын, жыныстық жолмен берілетін аурулар маңызды болып табылады. Оқушылар уақыт осы кезең ішінде бір ғана серіктес болды болуы мүмкін, бірақ, соған қарамастан, оны түйсіне, ең құрамдас бөлігі, және беру көптеген әлеуетті бағыттардың сондықтан, бір бөлігі болды. мұқият және өсек нысанасы болуы үшін, осы құрылымдар ұзақ аяқталды мүмкін қарым-қатынаста көрсетеді, бірақ олар тым ұзақ тізбектерді тұлғаларды жалғаңыз. Дегенмен, олар нақты болып табылады: көрінбейді, бірақ жанама macrostructures жеке медиация өнім ретінде пайда қалай әлеуметтік фактілер.

Қашықтықтан және ені-бірінші іздеу

Екі түйіндері маршрут байланысты ма туралы ақпаратқа Сонымен қатар, информатика графтар теориясы Сіз оның ұзындығы шамамен білу үшін мүмкіндік береді - Жаңалықтар мен аурулардың көлікте, байланыс немесе тарату, сондай-ақ ол бірнеше шыңдары немесе еселі арқылы өтеді ма.

Бұл әрекетті орындау үшін, яғни, басынан аяғына дейін қамтитынын қадамдар санына тең маршрут ұзындығын анықтау. E. болып ретпен шетінен санын. Мысалы, MIT, BBN, RAND, UCLA маршрут 3 ұзындығы бар және MIT, UTAH - 1. жолы ұзындығы пайдалана отырып, біз екі түйіндер бағанында орналасқан, егер екі шыңдары арасындағы бір-біріне жақын немесе алыс қашықтық ұзындығы ретінде анықталады деп айтуға болады олардың арасындағы ең қысқа жол. Мысалы, LINC мен Шри арасындағы қашықтық 3, дегенмен, бұл қамтамасыз ету үшін, ол 1 немесе 2, Санағыш тең ұзындығы жоқтығын тексеру үшін қажет.

Ені-бірінші іздеу алгоритмі

екі тораптары арасындағы шағын график қашықтыққа оңай есептеу. Бірақ күрделі үшін қашықтыққа анықтау жүйелі әдісі үшін қажеттілік бар.

сондықтан, ең тиімді (мысалы, достар жаһандық желі) мынадай ең табиғи Мұны істеу тәсілі мен:

• Барлық достар 1 қашықтықта орналасқан жарияланды.
• (Қазірдің өзінде аталған есептемегенде) достар Барлық достар қашықтықта 2 жарияланады.
• Барлық олардың достары (қайта, таңбаланған адам есептемегенде) қашықтан қашықтықта 3 жариялады.

Осы жолмен жалғастыра, іздеу әрқайсысы, кейіннен қабаттарының жүзеге асырылады - алдыңғы бірінде құрылғыдағы. Әрбір жаңа қабаты алдыңғы қатысқан жоқ, ескертулерінен құралған, және алдыңғы қабатының шыңында осы күзде Edge отыр.

ол бастапқы түйіннің жүзеге бағанда іздейді ретінде Бұл техника, ең алдымен, келесі қамтитын, ені-бірінші іздеу деп аталады. қашықтыққа анықтау тәсілі қамтамасыз қатар, бұл тіркелген нүктесі олардың қашықтықта негізделген шыңдарды бар, компьютер графигін салу қаншалықты, сондай-ақ график құрылымын ұйымдастыру үшін пайдалы тұжырымдамалық негізі ретінде қызмет ете алады.

Ені-бірінші іздеу достар желіге, сонымен қатар кез-келген графиктің ғана емес қолданылуы мүмкін.

шағын әлемдік

Әлемдік халықтың едәуір бөлігінің оған байланыстыратын, ғана емес, оқырман достар бағыттарды бар, бірақ осы бағыттар таңқаларлық қысқа: Егер қайтадан достар жаһандық желісіне барып, онда сіз барынша компоненті тиесілі түсіндіреді дәлел шынымен көп нәрсе бекітеді көруге болады, бұл .

Бұл идея «шағын әлемдік құбылыс» деп аталады: сіз қысқа маршрут кез келген екі адам қосылады не туралы ойлануға, егер әлемдік, шағын көрінеді.

«Алты қол алысу» теориясы бірінші эксперименттік 1960 жылы Стэнли Milgram және оның әріптестері зерттелді. әлеуметтік желі деректердің кез келген жиынтығын қажетінсіз, және $ 680 бюджетпен, ол танымал идеясын тексеруді шештік. Осы мақсатта ол 296 кездейсоқ таңдалған бастамашылары Бостон қаласының шетінде өмір сүрген биржалық маклердің, хат жіберуге тырысамыз сұрады. ол мүмкіндігінше тез мақсатына жетті, сондықтан бастаушылары, (мекен-жайы және мамандық қоса алғанда) мақсаты туралы кейбір жеке ақпаратты ескере отырып, сондай-ақ олар сол нұсқауларға, олар аты бойынша білген адамға хат жолдау болды. Әрбір әріп достар бірқатар қолына арқылы өтіп және Бостон тыс биржалық брокерлер үшін тізбекті жабылады қалыптасты.

мақсатты жетті 64 тізбектерінің арасында орташа ұзындығы бұрын ойын Dzhona Гера атауында атындағы екі онжылдықта санын растайтын, алты болды.

Осы зерттеудің барлық кемшіліктеріне қарамастан, эксперимент әлеуметтік желілерде біздің түсіну маңызды аспектілерінің бірі көрсетті. әлеуметтік желілер адамдардың еркін жұп арасындағы өте қысқа маршруттарды бар бейім: оған еріп жылдары кең қорытынды жасалды. бизнес көшбасшыларының және саяси көшбасшылармен осындай жанама байланыстары күн сайын өздері үшін төлеуге емес, тіпті, егер мен, осындай қысқа бағыттар болуы әлеуметтік желі адамдарды қамтамасыз мүмкіндіктері үлкен ақпараттық тарату жылдамдығын рөлін, ауру және жұқтыру басқа түрлерін қоғамдастықта, сондай-ақ қол атқарады керісінше қасиеттер.