Theory ea Graph

Tlhaloso ea litšoantšo ke e 'ngoe ea likarolo tsa lipalo, e leng karolo e ka sehloohong e khetholloang ke mokhoa oa geometric ho ithuta lintho. Mothehi oa eona o nkoa e le setsebi se tummeng sa lipalo L. Euler.

Ho sebelisoa ha khopolo ea lifilimi ho fihlela bofelong ba lekholo la bo19 la lilemo ho fokotsoe ho rarolla mathata a thabisang 'me ha hoa ka ha lebisa tlhokomelo e kholo ka kakaretso. Ho tloha lekholong la bo20 la lilemo, ha khopolo ea lifilimi e hlahisitsoe e le thuto ea lipalo e ikemetseng, e fumanoe haholo litabeng tsa saense tse kang cybernetics, fisiks, lisebelisuoa, mananeo, biology, lisebelisoa tsa elektronike, tsamaiso ea lipalangoang le tsa puisano.

Lintlha tsa motheo tsa khopolo ea litšoantšo

Graf ke eona ea motheo. Ka lentsoe la mantsoe, motho a ka fumana khopolo e joalo e le marang-rang a tšoanang le graph. Sepheo sa eona ke palo e se nang letho ea lintlha, ke hore, lihlopha, le likarolo, ke hore, likarolo, bobeli ba tsona tse lumellanang le palo e fanoeng ea lintlha. Tlhaloso ea graph ha e etse moelelo o tobileng ka litekanyetso tsa metse le lihlopha. Ka mohlala, metse le litsela li li hokahanya, moo lihlooho tsa pele e leng litlhōrō tsa graph, 'me ea bobeli - metseng. Ntho ea bohlokoa haholoanyane khopolong e fanoa ho arcs. Haeba moeli o e-na le tataiso, joale e na le lebitso la arc, haeba graph e na le lihlopha tse sekametseng, e bitsoa digraph.

Tlhahisoleseding ea mantsoe, mantsoe a latelang a boetse a totobetse:

Setšoantšo se senyenyane ke graph, likarolo tsohle le lihlopha tsa eona tse leng lipakeng le lihlopha.

Graph e kopantsoeng ke e nang le ketane e li kopanya bakeng sa lihlopha tse peli tse fapaneng.

Setšoantšo se nang le moelelo o boima ke oo boima ba oona bo sebetsang.

Sefate ke graph e kopantsoeng ntle le ho potoloha.

Masapo ke serafate sefate.

Ha graph e huloa ka sefofaneng, ho na le letoto le itseng le sebelisitsoeng: vertex e khethiloeng e lumellana le ntlha e hlakileng ka holimo, 'me haeba ho na le moeli pakeng tsa lintlheng, lintlha tse tsamaisanang li kenngoa ka karolo. Haeba graph e sekametse, likarolo tsena li nkeloa sebaka ke metsu.

Empa u se ke ua bapisa setšoantšo sa graph le eona, ke hore, ka sebopeho se sa tsejoeng, hobane graph e le 'ngoe e ka fuoa makhetlo a fetang a le mong. Setšoantšo sefofaneng se fanoa e le hore se bone hore na ke lipi tse peli tsa lintlheng tse kopantsoeng le lihlopha le tse ling.

Har'a mathata a mang a khopolo-taba, ho na le:

1. Mosebetsi oa ho kenya lintho tse khutšoanyane (ho nkeloa ha thepa, ho behoa ha ambulense le litheipi tsa thelefono).
2. Bothata ba ho phalla ho hoholo (taolo ea sephethephethe moeteng o matla, kabo ea mosebetsi, tlhophiso ea bokhoni).
3. Mosebetsi oa ho apara le ho kenya liaparo (ho behoa ha lintlha tse romellanang).
4. Ho khabisa lirafshoa (ho behoa ha mohopolo ka lik'homphieutha tsa elektronike).
5. Ho buisana ka marang-rang le lipapali (ho thehoa marang-rang a puisano, ho hlahloba mananeo a puisano).

Hona joale, ho ke ke ha khoneha ho hlophisa boholo ba mathata ntle le ho tseba khopolo ea lirafu. Sena se etsa hore ho be bonolo le ho le bonolo ho sebetsa le khomphuta.

Lenaneo le sebelisa mekhoa e mengata le mekhoa ea bokahohle ea ho rarolla mathata, 'me e' ngoe ea tsona ke khopolo ea litšoantšo. Bohloko ba eona bo thata ho feta. Tlhaloso ea graph ka lenaneo e etsa hore ho be bonolo ho fumana boitsebiso, ho ntlafatsa mananeo, ho fetola le ho aba data. Ka lebaka la mekhoa e tloaelehileng ea khopolo ena, hoa khoneha ho e sebelisa le ho e hlahloba ha e sebelisoa ho rarolla mathata a itseng, ho fetola algorithm ntle le ho fokotsa tekanyo ea lipalo tsa tikoloho ea phetoho ea ho qetela ea lenaneo.

Thepa ea bohlokoa ea tsamaiso ea motlakase kapa ea mohlala ke sete sa likamano tse nyenyane tse bokellaneng ea liketso le li-data unit. Mehaho ena ke eona feela likarolo tsa mananeo le boitsebiso boo ba bo fetolang. Ka hona, lirafate ke motheo oa kaho bakeng sa moqapi.