Графики дар илм компютерӣ: таъриф, навъ, намуна барнома. Назарияи Графики дар илм компютерӣ

Ҳисоб дар усули компютерӣ барои муносибатҳо муайян шудаанд унсурҳои омехта. Ин иншооти асосии таҳсил дар ҳастед назарияи граф.

мафҳумҳои асосии

Чӣ йхатгирии а ол дар илм компютер аст? Он як plurality объектҳои даъват гиреҳи ё vertices, баъзе ҷуфтҳои, ки аз тарафи м пайваст. Н. пушту. Масалан, графикаи дар ҷадвали (а) иборат аз чор гиреҳи, denoted A, B, C, D ва, B, ки ба ҳар як аз дигаре се vertices пушту пайваст гардида, C ва D низ пайваст аст. Ду гиреҳи шафати мебошанд, агар онҳо аз ҷониби як канори пайваст. Дар ҷадвали ба таври хос, ки чӣ тавр ба сохтани графикҳо дар илм компютерӣ нишон медиҳад. Доираҳои намояндагӣ мекунанд, ки vertices ва хатҳои пайваст ҳар як ҷуфт аз онҳо, пушту мебошанд.

Чӣ граф undirected аст, ки дар илм компютерӣ номида? Вай равобити байни ду ақсои пушту symmetrical мебошанд. Қабурғаи танҳо онҳо бо ҳамдигар мепайвандад. Дар бисёр ҳолатҳо, бо вуҷуди ин, зарур аст, то изҳори муносибати асимметричный аст, - масалан, ки нуқтаи ба $ B, вале на баръакс. Ин ҳадафи муайян намудани графикаи дар компютер аст, ки ҳанӯз ҳам иборат аст аз як маҷмӯи гиреҳи бо маҷмӯи кунҷҳои равона карда мешавад. Ҳар як канори нигаронида робитаи байни vertices, ки самт дорад, маънои аст. графикҳо равона тасвир, чунон ки дар ҷадвали (б) нишон дода шудааст, атрофи онҳо аз тарафи тирҳои қимор намояндагӣ мекунанд. Вақте, ки шумо мехоҳед, ки ба таъкид намоям, ки граф ғайридавлатӣ directional, он аст, undirected номида мешавад.

модели шабакавии

Графики дар илм компютерӣ мебошанд модели математикии сохторҳои шабакаи. Дар ҷадвали зерин нишон сохтори Интернет, он гоҳ, ки исми ARPANET, ки дар моҳи декабри соли 1970 бардошт, вақте ки ӯ танҳо 13 хол шуд. Дар гиреҳи коркарди марказҳои ва пушту пайваст кардани ду vertices therebetween feedforward. Агар шумо аҳамият нест, ки ба Иёлоти Муттаҳида харита гузошта, дигарон аз тасвири як граф 13-гиреҳ монанд ба яке аз гузашта аст. Дар ин ҳолат, вазифаи аслии vertex аст, муҳим нест. Муҳим, ки гиреҳи ба якдигар вобаста аст.

Истифодаи графикҳо дар компютер имкон медиҳад, то бингарем, ки чӣ чиз ё ҷисмонӣ ё мантиқан дар сохтори шабакаи алоқаманд. ARPANET 13-гиреҳ намунаи шабакаи алоқа, ки дар он компютер боло ё дигар дастгоҳҳои метавонед паёмҳои таҳвил аст, ва кунҷҳои намояндагӣ мекунанд пайванди бевоситаи он маълумот метавонад интиқол дода мешавад.

хатсайрҳои

Ҳарчанд графикҳо дар бисёр соҳаҳои гуногун истифода бурда мешавад, ки онҳо доранд, хусусияти умумӣ. Назарияи Графики (компютер) дар бар мегирад, шояд аз ҳама муҳим аз онҳо - идеяи, ки чизҳои бисёр вақт дар баробари кунҷҳои ҳаракат пай гузаштан аз гиреҳ ба гиреҳ, бошад, он мусофир чанд парвози ё маълумоти дар шабакаи иҷтимоӣ ба шахси гузаранда аз шахси, ё истифодабаранда компютерӣ, пайгирона боздид аз як қатор саҳифаҳои интернетӣ аз рӯи пайвандҳои.

Ин фикри муайян намудани масири ҳамчун як қатор гиреҳи вобаста аз тарафи кунҷҳои бармеангезад. Баъзан он ба назар хатсайри, ки на танҳо дорои ҷузъҳои, балки пайдарпаии кунҷҳои пайваст онҳо зарур аст. Барои мисол, пайдарпаии vertices MIT, BBN, RAND, UCLA як масири дар граф интернет ARPANET аст. Гузариш аз гиреҳи ва кунҷҳои метавонад такрор шавад. Барои мисол, Шри, Stan, UCLA, Шри, Юта, MIT аст, низ дар як масири. Дар роҳи ки дар он пушту шудаанд такрор нест, ном як занҷир. Агар гиреҳи шудаанд такрор нест, он аст, занҷири содда номида мешавад.

давраҳои

Аз ҷумла намудҳои муҳим дар графикҳо компютерӣ - он давраҳои, ки намояндагӣ мекунанд сохтори ангуштарин, ба монанди як пайдарњамии гиреҳи LINC, парвандаи, CARN, HARV, BBN, MIT, LINC. Хатсайрҳои бо на камтар аз се пушту, ки дар он гиреҳ аввалин ва охирин айни ҳамон ҳастӣ, ва дигарон гуногун мебошанд, намояндагӣ мекунанд графикҳо cyclic дар илм компютерӣ.

Мисолҳо: давраи Шри, Stan, UCLA, Шри кӯтоҳтарин аст, ва Шри, Stan, UCLA, RAND, BBN, Юта, Шри хеле бузургтар аст.

Амалан ҳар канори ARPANET аз графикаи они ба давра. Ин дидаву дониста шуд, ки агар аз онҳо наояд, хоҳад имконияти гузариш аз як гиреҳ ба дигар. Давраҳои дар алоқа ва системаҳои нақлиётӣ барои ихтисор мазкур мебошанд - онҳо таъмин роҳҳои алтернативии роҳи давраи дигар. Дар шабакаҳои ҷамъиятӣ аксаран давраҳои намоён мебошанд. Вақте ки шумо даст ёбанд, барои мисол, то ки дӯсти мактаб наздики як ҷияни зани худ дар асл, бо бародари худ кор мекунад, дар он давра, ки иборат аст аз шумо, ки зани худ, ҷияни вай, дӯсти худ аз мактаб, корманди худ (яъне. E. аст Шумо бародар), ва дар охир ба шумо боз.

граф васлгардида: таърифи (компютер)

Табиист, ки ба фикр, ки оё он имконпазир аст, ки аз ҳар гиреҳ ба даст ба ҳама гуна гиреҳ дигар. Дар граф вобаста аст, агар як роҳи байни ҳар як ҷуфт vertices нест. Барои мисол, дар шабакаи ARPANET - пайваст граф. Дар ҳамин мумкин аст дар бораи аксари шабакаҳои алоқа ва нақлиёт, гуфт, ки мақсади онҳо аст, ки ба ҳидоят ҳаракати аз як гиреҳ ба дигар.

Аз тарафи дигар бошад, пас сабаби priori умед, ки ин намуди графикҳо дар илм компютерӣ густарда вуҷуд дорад. Барои мисол, дар шабакаи иҷтимоии душвор нест, тасаввур кунед, ду нафар, ки ба якдигар вобаста нестанд.

ҷузъҳои

Агар сутуни ба компютер пайваст кардан, онҳо табиатан ба маҷмӯи пораҳои алоқамандро ҷустуҷӯ намоед, гурӯҳҳои гиреҳи, ки ҷудо ва бархўрд нест, афтод. Масалан, нақшаи нишон се қисм чунин аст: якум - A ва B, дуюм - C, D ва E, ва сеюм иборат аз vertices боқимонда.

Унсурњои аз графикаи намояндагӣ қисми таркибии гиреҳи, ки дар он:

• њар як зергурӯҳ vertex дорад масири ки ба ҳеҷ як;
• subset аст, як қисми маҷмӯи калонтар, ки дар он ҳар гиреҳ дорад, масири ки ба ҳеҷ нест.

Вақте, ки дар компютери графикҳо ба ҷузъҳои онҳо ҳам ҷудо шавад, он танҳо тасвири аввалаи усули сохтори худ мебошад. Ин ќисмати метавонад, ки сарватдор дар сохтори дохилӣ, он барои ба таъбири ин шабака муҳим аст. Масалан, усули расмии муайян аҳамияти гиреҳ барои муайян кардани чанд қисмҳо ҷудо карда мешавад ҳисоб, агар ки гиреҳ хориҷ карда мешавад.

Максимум ҷузъи

аст, ки усули арзёбии сифатии таркиби пайвастшавӣ нест. Масалан, дар як шабакаи иҷтимоӣ дар саросари ҷаҳон бо алоқаҳои байни ду нафар бошад, агар ки онҳо дӯстони мебошанд.

Оё пайваст? Эҳтимол не. Пайвастшавӣ - амволе, на шикананда ва рафтори як гиреҳ (ё маҷмӯи ками онҳо) метавонанд аз он чизе кам кунад. Масалан, як шахс бо нест кардани дӯстоне зиндагӣ ҷузъи иборат аз vertex ягона аст, ва аз ин рӯ, ба ҳисоб хоҳад пайваст карда намешавад. Ё як ҷазираи тропикӣ дурдаст, иборат аз мардуме, ки надоранд, алоқа бо ҷаҳони берунӣ, низ як ҷузъи хурди шабака, ки incoherence он тасдиқ шавад.

шабакаи глобалии дӯстон

Аммо чизи дигаре нест. Масалан, як хонандаи китоби машҳур дорад, дӯстоне, ки дар кишварҳои дигар парвариш, ва онҳоро як ҷузъи. Агар мо ба инобат мегирад волидони ин дӯстон ва дӯстони онҳо, ҳамаи ин мардум низ дар ќисмати баробаранд, гарчанде онҳо ҳеҷ гоҳ дар бораи ба хонанда шунида буданд, ба забони гуногун сухан ронанд, ва оянда ба он ҳеҷ вақт. Ҳамин тариқ, гарчанде ки шабакаи ҷаҳонии дӯстӣ - вобаста набошад, хонанда хоҳад шуд, дар ќисмати дохил хеле калон, дар вуҷудашон ба ҳамаи қисматҳои ҷаҳон, ки бар мегирад одамони гуногун ва, дар асл, бар мегирад, як қисми зиёди аҳолии ҷаҳон.

Дар ҳамин дар маҷмӯи маълумоти шабака рух - калон, шабакаҳои мураккаб аксаран ҳадди ҷузъи, ки дар бар мегирад, ки қисми зиёди тамоми гиреҳи доранд. Гузашта аз ин, вақте ки шабака дар бар мегирад, ҳадди ҷузъи, он аст, қариб ҳамеша як. Барои фаҳмидани ин, зарур аст, ки ба баргаштан ба мисоли шабакаи ҷаҳонии дӯстӣ ва кӯшиш кунед, ки ба мавҷудияти ду ҳадди ҷузъҳои, ҳар як аз он мегирад, миллионҳо одамон. Он бояд ба як қабурғаи ягона оид ба баъзе аз ќисмати аввал ба дуюм ба ҳадди ду қисмати ҳамроҳ шуд ба як. Азбаски танҳо як муосир, дар аксари ҳолатҳо ба он эҳтимол дур аст, ки дар он буд, ташкил нест, ва аз ин рӯ ҳадди ду қисмати дар шабакаҳои воқеӣ ҳеҷ гоҳ ба мушоҳида мерасад.

Дар баъзе ҳолатҳо нодир, вақте ки ду қисмати ниҳоии-муштарак вуҷуд барои муддати дароз дар шабакаи воқеӣ, иттифоқи онҳо ғайричашмдошт, драмавӣ буд, ва, ниҳоят, доранд маҳбусон.

якҷояшавии компоненти садама

Масалан, баъд аз омадани explorers Аврупо дар тамаддуни нимкураи ғарбӣ, дар бораи ним ҳазорсолаи пеш, буд cataclysm ҷаҳонӣ вуҷуд доранд. Аз нуќтаи назари шабака, он мисли ин назар: панҷ ҳазор сол аз шабакаи иҷтимоии ҷаҳон, шояд аз ду ҷузъи бузург иборат - як Шимолӣ ва Амрикои Ҷанубӣ, ва дигар - дар Евразия. Аз ин сабаб, технология дорад, мустақилона дар ду қисмати падидомада, ва, ҳатто бадтар, ки таҳия ва бемории инсон ва ғайра. D. Ҳангоме ки он ду қисмати ниҳоят дар технологияи сенсорӣ ва бемории гирифта зуд ва disastrously ҷӯшид дуюм.

Мактаби олии Амрико

Консепсияи ҳадди компоненти барои мулоҳиза дар бораи шабака дар миқёси хеле камтар аст, муфид аст. Як мисоли ҷолиб як граф illustrating муносибати дар як мактаби амрикоӣ дар давраи 18-моҳ аст. Далели он, ки он дорои ҳадди ҷузъи муҳим аст, он гоҳ ки ба паҳншавии бемориҳо, бемориҳои бо роҳи ҷинсӣ аст, ки бо мақсади омӯзиш меояд. Донишҷӯён шояд танҳо як шарик дар давоми он давраи вақт нафаҳмида буданд, вале, ба ҳар ҳол, ки қисми таркибии ҳадди шудааст, ва аз ин рӯ, қисми зиёди роҳҳои эҳтимолии интиқоли. Ин сохторҳои инъикос муносибатҳои, ки метавонад дароз ба поён расид, вале онҳо пайваст воқеӣ дар занҷир ҳам дароз, ба мавзўи дақиқ сахт ва ғайбат. Бо вуҷуди ин, онҳо воқеӣ мебошанд: чӣ тавр далелҳои иҷтимоии ноаён, вале дар натиҷаи macrostructures ҳамчун маҳсулоти миёнаравї инфиродӣ ба миён омад.

Фосилавӣ ва фароҳӣ аввал Ҷустуҷӯи

Илова бар ин ба маълумоти дар бораи ки оё ин ду гиреҳи шудаанд хатсайри пайваст, назарияи граф дар илм компютерӣ ба шумо имкон медиҳад, ки дар бораи дарозии он ёд - дар нақлиёт, алоқа ё паҳн намудани ахбор ва касалиҳо, инчунин ки оё он ба воситаи якчанд қуллаҳои ё якчанд меравад.

Барои ин кор, муайян дарозии хатсайри ба миқдори қадамҳои, ки он аз аввал то ба охири дорои, яъне баробар. E. Шумораи кунҷҳои дар навбат аст, ки. Барои мисол, MIT, BBN, RAND, масири UCLA дорад дарозии 3, ва MIT, Юта - 1. Истифодаи дарозии роҳи, мо гуфта метавонем, ки агар ду нафар гиреҳи дар сутуни наздик ба якдигар дар масофаи дигар аст ё дур байни ду қуллаҳои ташкил ҳамчун дарозии муайян кӯтоҳтарин роҳи миёни он дӯст. Масалан, дар масофаи байни LINC ва Шри 3 аст, ҳарчанд, ки ба таъмини ин, зарур тафтиши набудани дарозии баробар ба 1 ё 2, therebetween аст.

алгоритми Ҷустуҷӯи арзи аввал

Зеро фосилаи граф хурд байни ду гиреҳи ба осонӣ њисоб. Аммо барои мураккаб, зарур аст, ки барои як усули системавии муайян намудани масофа дорад.

Дар роҳи табиӣ аз ҳама ба ин кор ва, бинобар ин, самаранок зерин (масалан, шабакаи глобалии дӯстони) аст:

• Ҳамаи дӯстони шудаанд эълон воқеъ дар масофаи 1.
• Ҳамаи дӯстони дӯстони (ҳисоб, на аллакай зикр) доранд, дар масофаи 2 эълон кард.
• Ҳамаи дӯстони худ (аз нав, мардуми нишонгузорӣ ҳисоб нест) оид ба масофаи дурдаст 3 эълон кард.

дар шӯъбаи аз як гузашта - идома дар ин роҳ, Ҷустуҷӯи аст, ки дар қабатҳои минбаъда гузаронида мешавад, ҳар як аз он. Ҳар як қабати нав аз гиреҳи, ки дар шахсони гузашта иштирок накардаанд, иборат, ки фурӯ дами аз vertex аз қабати гузашта.

Ин Техникаи номида ҷустуҷӯи васеъияш-аввал, чун ӯ барои сутуни ҷустуҷӯ берун аз гиреҳ ибтидоӣ, пеш аз ҳама фаро оянда. Илова ба таъмини усули муайян масофа, он метавонад ҳамчун консепсияи умумии муфид барои ташкили сохтори граф, инчунин чӣ тавр сохтани граф компютер хизмат, ки қуллаҳои дар асоси масофаи аз нуќтаи ибтидої муайян.

Ҷустуҷӯи васеъияш-аввал метавонад, на танҳо ба шабакаи дӯстон, балки инчунин ба њама гуна граф истифода бурда мешавад.

ҷаҳон хурд

Агар шумо баргаштан ба шабакаи ҷаҳонии кардани дӯстоне, ки шумо мебинед, ки ба далели он, ки тавзеҳ тааллуқ доштан ба ин ҳадди ҷузъи дар ҳақиқат чизе бештар тасдиқ: на танҳо ба хонанда дорад хатсайрҳои ба дӯстоне, мепайвандад ӯро бо қисми зиёди аҳолии ҷаҳон, балки ин масир тааҷуб кӯтоҳ .

Ин фикри номида мешавад "падидаи хурд ҷаҳон»: ҷаҳон хурд ба назар мерасад, ки агар шумо дар бораи кадом як масири кӯтоҳ ҳар ду пайваст фикр кунед.

Дар назарияи "шаш handshakes» аввалин озмоиш аз ҷониби Стэнли Milgram ва ҳамкорони ӯ дар солҳои 1960 тафтиш карда шуд. Бе доштани ягон маҷмӯи маълумоти шабакаи иҷтимоӣ, ва бо буҷаи 680 $, ки ӯ қарор ба тафтиш аз фикри машҳур. Аз ин лиҳоз, ӯ пурсид: 296 ташаббускорони таври тасодуфӣ интихоб кӯшиш ба фиристодани нома ба stockbroker, ки дар дар назди шаҳр Бостон зиндагӣ мекард. Ташаббускорони баъзе маълумоти шахсӣ дар бораи мақсади (аз ҷумла суроғаи ҷойгиршавӣ ва касб) дода шудаанд, ва онҳо буд, ба фиристодани нома ба шахсе, ки онҳо ном медонистанд, ки бо дастури ҳамин, ба тавре ки он ҳадафи ҳарчӣ зудтар расид. Ҳар як нома дод, ба василаи дасти як қатор дӯстони гузашт ва ташкил занҷири пӯшида барои брокерҳои саҳҳомӣ берун аз Бостон.

Дар байни 64 занҷир, ки ҳадаф расида, дарозии миёнаи шаш буд, тасдиқ мекунад, шумораи ду даҳсола ба номи пештар дар бозӣ унвони Dzhona Gera.

Сарфи назар аз тамоми камбудиҳои ин тадқиқот, аз таҷрибаи яке аз самтҳои муҳимтарини фаҳмиши мо аз шабакаҳои иҷтимоӣ нишон дод. Дар солҳои минбаъда, аз он хулосаи васеътар шудааст: шабакаҳои иҷтимоӣ майл дошта роҳҳои хеле кӯтоҳ дар байни ҷуфтҳои худсарона одамон. Ва ҳатто агар ин гуна пайвастшавиҳо, ғайримустақим, бо пешвоёни бизнес ва пешвоёни сиёсӣ кор барои худ як рӯз пардохт накардааст, мавҷудияти чунин роҳҳои кӯтоҳ нақши калон дар суръати паҳнкунии маълумот, беморӣ ва дигар намуди сирояти дар ҷомеа, инчунин дастрасӣ аз имкониятҳое, ки шабакаҳои иҷтимоӣ таъмин бо мебозад хеле хислатҳои муқобил.