Grafik dina elmu komputer: harti, jenis, conto aplikasi. Téori grafik dina elmu komputer

Diitung dina metoda komputer pikeun hubungan nangtukeun digabungkeun elemen. Di handap ieu mangrupakeun obyek dasar ulikan na Téori grafik.

definisi dasar

Naon di grafik dina elmu komputer? Ieu ngawengku hiji pluralitas objék disebut titik atanapi hucu, sababaraha pasang nu dihubungkeun ku m. N. tulang rusuk. Contona, dina grafik di angka (a) diwangun ku opat titik, dilambangkeun A, B, C, sarta D, B nu disambungkeun ka unggal tilu hucu tulang rusuk lianna, sarta C jeung D nu ogé disambungkeun. Dua titik anu padeukeut lamun aranjeunna disambungkeun ku an tepi. inohong nembongkeun cara has cara ngawangun grafik dina elmu komputer. Bunderan ngawakilan hucu jeung garis nyambungkeun unggal pasangan sahijina, nu tulang rusuk.

Naon grafik undirected disebut dina elmu komputer? Anjeunna Hubungan antara dua tungtung tina tulang rusuk nu simetris. Iga saukur nyambungkeun aranjeunna saling. Dina loba kasus, kumaha, perlu pikeun nganyatakeun hubungan asimétri - contona, éta A titik ka B, tapi teu sabalikna. Tujuan ieu definisi grafik dina komputer, masih diwangun ku susunan titik kalayan susunan edges diarahkeun. Unggal ujung berorientasi mangrupa link antara hucu anu arah ngabogaan harti. grafik diarahkeun kondisi, ditémbongkeun saperti dina Gambar (b), edges maranéhanana anu digambarkeun ku panah. Lamun anjeun hoyong ngantebkeun nu grafik non-arah, mangka disebut undirected.

model jaringan

Grafik dina elmu komputer téh modél matematika tina struktur jaringan. Sosok handap mintonkeun struktur Internet, teras bore ngaran ARPANET, dina bulan Désémber 1970, nalika manéhna ukur 13 titik. Tempat ngumpulna anu ngolah puseur jeung tulang rusuk nyambungkeun dua hucu feedforward therebetween. Mun anjeun teu nengetan Amérika Serikat ditumpukeun peta, sesa gambar nyaeta titik grafik 13 titik sarupa hiji saméméhna. Dina hal ieu, anu posisi sabenerna vertex nu teu penting. Kadé nu ngumpulna disambungkeun ka unggal lianna.

Aplikasi tina grafik dina komputer ngamungkinkeun ningali kumaha hal anu boh sacara fisik atawa logis interconnected dina struktur jaringan. 13 titik ARPANET conto jaringan komunikasi nu komputer luhur atawa alat sejen bisa ngirimkeun pesen, sarta edges ngagambarkeun link langsung dina nu informasi bisa dikirimkeun.

ruteu

Sanajan éta grafik anu dipaké dina loba widang béda, maranéhna mibanda fitur umum. Téori grafik (elmu komputer) ngawengku sugan pangpentingna di antarana - gagasan anu hal sering mindahkeun sapanjang edges, sequentially pindah ti titik ka titik, jadi eta panumpang hiji sababaraha penerbangan atawa informasi dikirimkeun ti jalma ka jalma dina jaringan sosial, atawa pamaké komputer, konsistén ngadatangan sababaraha kaca wéb ku cara nuturkeun tumbu.

gagasan ieu motivates ngartikeun jalur salaku runtuyan titik disambung ku edges. Kadangkala kacida perlu mertimbangkeun jalur nu ngandung teu ngan komponén, tapi oge réntétan edges nyambungkeun aranjeunna. Contona, urutan hucu MIT, BBN, Rand, UCLA mangrupakeun jalur di grafik internét ARPANET. Petikan titik sarta edges bisa diulang. Contona, Sri, Stan, UCLA, Sri, Utah, MIT oge jalur nu. Cara nu iga teu terus-terusan, disebut ranté hiji. Lamun tempat ngumpulna teu terus-terusan, éta disebut ranté basajan.

siklus

Spésiés hal penting dina grafik komputer - eta siklus nu ngagambarkeun struktur cingcin, kayaning tina sekuen titik LINC, bisi, CARN, HARV, BBN, MIT, LINC. Ruteu kalawan sahenteuna tilu tulang rusuk, numana titik mimiti jeung panungtung anu sami, sareng sésana téh béda, ngagambarkeun grafik siklik dina elmu komputer.

Conto: siklus Sri, Stan, UCLA, Sri teh shortest, sarta Sri, Stan, UCLA, Rand, BBN, Utah, Sri considerably gede.

Ampir unggal ujung ARPANET grafik milik siklus nu. Hal éta dipigawé ngahaja, upami salah sahiji aranjeunna gagal, bakal kamungkinan transisi ti hiji titik ka nu sejen. Siklus dina komunikasi na sistim angkutan nu hadir keur redundancy - aranjeunna nyadiakeun rute alternatif pikeun jalur siklus sejen. The jaringan sosial nu sering siklus noticeable. Lamun anjeun manggihan, contona, anu hiji sobat sakola deukeut hiji misan ti pamajikan anjeun sabenerna jalan jeung lanceukna anjeun, eta mangrupakeun siklus anu diwangun ku anjeun, pamajikan anjeun, misan nya, sobat na ti sakola, pagawe na (ie. E. anjeun adi), sarta tungtungna deui.

grafik nyambung: harti (elmu komputer)

Ieu alam heran naha kasebut nyaéta dimungkinkeun tina unggal titik nepi ka sagala titik lianna. grafik disambungkeun lamun aya jalur antara unggal pasangan hucu. Contona, dina jaringan ARPANET - hubungkeun grafik. Sami tiasa nyarios ngeunaan mayoritas komunikasi jeung transportasi jaringan, saperti Tujuan maranéhanana nyaéta langsung lalulintas ti hiji titik ka nu sejen.

Di sisi séjén, taya alesan apriori kana nyangka yén rupa ieu tina grafik dina elmu komputer anu nyebar. Contona, dina jaringan sosial teu hese ngabayangkeun dua jalma anu teu patali jeung masing-masing lianna.

komponén

Mun kolom teu disambungkeun ka komputer, maranéhanana alami digolongkeun kana susunan popotongan patali, grup tina titik nu diisolasi sarta ulah motong. Contona, Gambar nembongkeun tilu bagian misalna: kahiji - A jeung B, kadua - C, D jeung E, sarta katilu ngawengku hucu sésana.

Komponen grafik ngagambarkeun sawaréh ti titik, nu:

• unggal subgroup vertex ngabogaan route ka sagala séjén;
• sawaréh henteu bagian tina susunan nu leuwih gede nu unggal titik miboga route ka sagala lianna.

Lamun grafik dina komputer dibagi kana komponén maranéhanana, éta mung pedaran awal metoda struktur maranéhanana. komponén ieu bisa jadi euyeub dina struktur internal, hal anu penting pikeun interpretasi tina jaringan. Contona, metoda formal nangtukeun hiji pentingna titik éta pikeun nangtukeun sabaraha réa patempatan bakal dibagi count, upami titik dicabut.

komponén maksimum

Aya metodeu pikeun assessment kualitatif komponén konektipitas. Contona, aya jaringan sosial dunya kalawan sambungan antara dua jalma, upami aranjeunna babaturan.

Geus eta disambungkeun? Meureun moal. Konéktipitas - sipat rada rapuh, sarta paripolah hiji titik (atawa set leutik di antarana) bisa ngurangan ka nanaon. Contona, hiji jalma tunggal kalawan euweuh babaturan nu hirup ngarupakeun salasahiji komponén nu diwangun ku hiji vertex tunggal, sarta ku kituna, golongan cacah moal nyambung. Atawa pulo tropis jauh, nu diwangun ku urang anu boga kontak jeung dunya luar, moal ogé jadi komponén leutik tina jaringan, nu confirms incoherence na.

jaringan global babaturan

Tapi aya hal sejenna. Contona, hiji maca tina buku populér boga babaturan anu geus dipelak nepi di nagara sejen, sarta ngajadikeun éta salasahiji komponén. Lamun kami tumut kana akun kolot babaturan ieu jeung para sahabat, sakabeh jalma ieu ogé dina komponén sarua, sanajan maranehna geus pernah Nu Uninga Ngeunaan maca, nyarita basa béda, sarta gigireun eta geus pernah geus. Ku kituna, sanajan jaringan global silaturahim - teu nyambung, nu maca bakal dilebetkeun komponénna téh kacida gedéna, penetrating ka sadaya bagian tina dunya, nu ngawengku jalma ti loba backgrounds béda jeung, dina kanyataanana, ngandung nyangkokkeun signifikan tina populasi dunya.

Sami lumangsung dina susunan data jaringan - ageung, jaringan kompléks mindeng boga komponén maksimum nu ngawengku nu saimbang signifikan sadaya titik. Leuwih ti éta, lamun jaringan nu ngawengku komponén maksimum, nya éta ampir sok ngan hiji. Ngartos naha, perlu balik ka conto jaringan global silaturahim jeung nyoba ngabayangkeun ayana dua komponen maksimum, nu masing-masing ngalibatkeun jutaan jalma. Ieu perlu boga iga tunggal on sababaraha komponén kahiji jeung kadua pikeun maksimum dua komponen dihijikeun kana hiji. Kusabab ngan hiji ujung, di hal nu ilahar ieu pimanaeun nu eta teu kabentuk, sarta ku kituna maksimum dua komponén di jaringan nyata anu pernah ditalungtik.

Dina sababaraha kasus langka, nalika dua komponen teh maksimum ko-eksis keur lila dina jaringan nyata, rugbi maranéhanana éta teu kaduga, dramatis, sareng, pamustunganana, boga konsekuensi catastrophic.

Kacilakaan komponén ngahiji

Contona, sanggeus datangna penjelajah Éropa dina peradaban Hémisfér Kulon ngeunaan satengah milénium katukang, aya cataclysm global. Ti sudut pandang jaringan, nu katingali jiga kieu: lima rebu taun jaringan sosial global, meureun diwangun ti dua komponén raksasa - hiji di Sulawesi Utara jeung Amerika Kidul, sarta séjén - di Eurasia. Ku sabab kitu, téhnologi nu geus mekar mandiri dina dua komponén, sarta, sanajan goréng, sakumaha dikembangkeun sarta panyakit manusa, jeung saterusna. D. Sabot dua komponen tungtungna ngagaduhan dina téhnologi toél jeung panyakit gancang sarta disastrously overflowed kadua.

Sakola Luhur Amérika

Konsep komponén maksimum nyaéta mangpaat keur nalar ngeunaan jaringan dina skala anu leuwih leutik. Hiji conto metot nyaeta titik grafik illustrating hubungan dina SMA AS pikeun période 18-bulan. Kanyataan yén éta ngandung komponén maksimum penting lamun datang ka sumebarna panyakit, panyakit dikirimkeun séksual, nu tujuan pangajaran anu. Murid bisa geus miboga ngan hiji pasangan dina mangsa éta periode waktu, tapi, Tapi, tanpa merealisasikan dinya, geus bagian tina komponen maksimum, sarta ku kituna, hiji bagian tina loba ruteu potensi transmisi. struktur ieu ngagambarkeun hubungan éta bisa geus lila lekasan tapi aranjeunna nyambung individu dina ranté panjang teuing, janten subyek scrutiny sengit sarta gosip. Tapi, aranjeunna nyata: kumaha fakta sosial anu siluman, tapi macrostructures consequential mecenghul salaku produk tina mediasi individu.

Jarak jeung breadth-hareup pilarian

Sajaba informasi ngeunaan naha dua titik disambungkeun jalur, tiori grafik dina elmu komputer ngidinan Anjeun pikeun ngalenyepan panjang anak - dina angkutan, komunikasi atanapi sosialisasi ngeunaan warta sarta panyakit, kitu ogé naha éta mana ngaliwatan sababaraha puncak atawa sababaraha.

Jang ngalampahkeun ieu, nangtukeun hiji panjangna jalur sarua jeung Jumlah léngkah anu ngandung ti mimiti nepi ka tungtung, nyaéta. E. Jumlah edges dina sekuen nu mangrupa. Contona, MIT, BBN, Rand, UCLA jalur boga panjang 3, sarta MIT, Utah - 1. Make panjang lintasan, urang bisa disebutkeun yen lamun dua titik nu disusun dina kolom deukeut unggal jarak séjén atanapi tebih antara dua puncak diartikeun panjang jalur shortest antara aranjeunna. Contona, jarak antara LINC sarta Sri nyaéta 3, sanajan, pikeun mastikeun ieu, perlu pariksa henteuna panjangna sarua jeung 1 atawa 2, therebetween.

Algoritma pilarian Breadth-heula

Pikeun jarak grafik leutik antara dua titik ngitung gampang. Tapi keur kompleks aya anu peryogi kanggo metoda sistimatis pikeun nangtukeun jarak.

Cara paling alam pikeun ngalakukeun ieu jeung, ku kituna, nu paling mujarab téh di handap (contona, jaringan global babaturan):

• Kabéh babaturan anu nyatakeun ayana di jarak 1.
• Kabéh babaturan babaturan (teu cacah nu geus disebutkeun) anu ngumumkeun dina jarak 2.
• Sadaya para sahabat (deui, teu cacah rahayat dilabélan) ngumumkeun dina jarak jauh 3.

Nuluykeun di jalan ieu, pilarian nu dilumangsungkeun dina lapisan saterusna, nu masing-masing - dina unit dina hiji saméméhna. Unggal lapisan anyar diwangun ku titik nu teu milu dina leuwih saméméhna, sarta anu digolongkeun ujung ti vertex tina lapisan saméméhna.

Téhnik ieu disebut pilarian breadth-heula, sakumaha manehna maluruh kolom kaluar tina titik awal, utamana ngawengku salajengna. Salian nyadiakeun metoda pikeun nangtukeun jarak, éta bisa ngawula salaku kerangka konseptual mangpaat pikeun ngatur struktur grafik ogé kumaha carana ngawangun grafik komputer, ngabogaan puncak dumasar kana jarak maranéhanana ti titik awal maneuh.

pilarian Breadth-hareup bisa dilarapkeun teu ukur keur jaringan babaturan, tapi ogé nepi ka grafik nanaon.

dunya leutik

Lamun balik ka jaringan global babaturan, anjeun tiasa ningali yén argumen anu ngécéskeun milik komponén maksimum bener approves hal langkung: teu ngan maca ngabogaan ruteu ka babaturan, linking anjeunna ku saimbang signifikan tina populasi dunya, tapi ieu ruteu anu heran pondok .

gagasan ieu disebut "fenomena dunya leutik": dunya sigana leutik, lamun mikir ngeunaan naon a jalur pondok nyambungkeun wae dua jalma.

Teori "genep handshakes" munggaran sacara ékspériméntal ditalungtik ku Stanley Milgram sareng kolega Anjeun di taun 1960-an. Tanpa ngabogaan sagala set data jaringan sosial, sarta ku anggaran $ 680, anjeunna mutuskeun pikeun pariksa kaluar hiji gagasan populér. Ka tungtung ieu, manehna nanya 296 initiators dipilih acak coba pikeun ngirim surat ka stockbroker, anu cicing di hiji suburb of Boston. Initiators dibere sababaraha émbaran pribadi ngeunaan Tujuan (kaasup alamat na profési), sarta aranjeunna kapaksa ngirim surat ka jalma saha maranéhna terang ku ngaran, kalawan parentah anu sarua, meh bisa ngahontal tujuan gancang-gancang. Unggal aksara geus dialirkeun leungeun sababaraha babaturan na dibentuk ranté hiji nutup keur calo stock luar tina Boston.

Diantara 64 ranté anu ngahontal udagan, dina panjang rata-rata éta genep, confirming jumlah ngaranna dua puluh tadi dina antrian Dzhona gera judul.

Sanajan sagala shortcomings ulikan ieu, percobaan nunjukkeun salah sahiji aspék pangpentingna of understanding kami tina jaringan sosial. Dina taun éta dituturkeun ti eta dijieun kacindekan lega: jaringan sosial condong mibanda ruteu pisan pondok antara pasang sawenang urang. Komo lamun sambungan langsung misalna kalawan inohong bisnis jeung inohong pulitik teu mayar sorangan dina dasar poean, ayana ruteu pondok sapertos muterkeun hiji peran badag dina laju sosialisasi informasi, kasakit jeung tipe séjén inféksi di masarakat, kitu ogé aksés kasempetan nu jejaring sosial nyadiakeun jalma kalawan rada qualities sabalikna.