Graph teoriya

Graph teoriya - kini mao ang usa sa mga Subsections sa matematika, ang nag-unang bahin sa nga mao ang geometric nga paagi sa pagtuon sa mga butang. Kini giisip nga ang magtutukod sa mga bantog nga matematiko Euler.

Ang paggamit sa graph teoriya sa ulahing bahin sa ika-19 nga siglo, ang mikunhod ngadto sa sa solusyon sa makapaikag nga mga problema ug nadani dakong publiko pagtagad. Sugod gikan sa ika-20 nga siglo, sa dihang ang graph teoriya naporma nga ingon sa usa ka independenteng disiplina sa matematika, kini nga kaylap nga gigamit sa kaumahan sama sa cybernetics, pisika, logistics, programming, biology, electronics, transportasyon ug komunikasyon nga sistema sa.

Basic konsepto sa graph teoriya

base mao ang usa ka graph. terminolohiya makita sa maong butang sama sa usa ka network susama sa kolum. Last - ang non-walay sulod nga gidaghanon sa mga puntos, nga mao, noene ug mga bahin, ie mga gusok, duha ka tumoy sa nga katumbas sa usa ka gihatag nga gidaghanon sa mga puntos. Graph teoriya wala mamuhunan sa usa ka punto sa mga mithi sa mga ngilit ug mga noene. Pananglitan, mga dalan sa siyudad ug sa sumpay kanila, diin ang unang - sa mga noene sa graph, ug ang ikaduha - gusok. Labaw ka Mahinungdanon nga importansya ang gihatag ngadto sa mga teoriya sa mga arcs. Kon ang sulab adunay usa ka direksyon, kini mao ang gitawag nga arko, kon ang usa ka graph sa mimando sulab, kini gitawag nga usa ka digraph.

Sa terminolohiya sa teoriya nga ingon sa ang mga mosunod nga mga konsepto:

Subgraph mao ang graph, ang tanan nga mga ngilit ug mga noene anaa sa taliwala sa mga noene ug mga ngilit.

Konektado graph - usa nga adunay duha ka mga lain-laing mga mga taluktok anaa kadena nga nagdugtong kanila.

Weighted konektado graph - usa nga gibutang ang kabug-aton function.

Kahoy - konektado grapika nga walay siklo.

Kabhang - sa usa ka subgraph nga mao ang usa ka kahoy.

Sa larawan graph sa eroplano gihubit nota gigamit: ang pinili nga vertex punto katumbas sa elementarya nawong ug kon ang sulab mao ang tali sa noene, ang tagsa-tagsa nga mga punto nga hiniusa nga bahin. Kon ang graph-oriented, kini nga mga bahin sa mga gipulihan sa mga udyong.

Apan ayaw itandi ang graph larawan uban kaniya, ie uban sa usa ka abstract nga gambalay, tungod kay sa usa ka graph nga gihatag sa labaw pa kay sa usa ka tan-awon nga representasyon. Naggamit sa eroplano gihatag aron sa pagtan-aw nga parisan sa noene nahiusa sulab, ug nga dili.

Lakip sa pipila sa mga buluhaton sa graph teoriya mailhan:

1. Ang problema sa labing mubo nga sirkito nga (hardware puli, placement, ambulansya ug sa telepono panagsukliay).
2. Maximum dagan problema (pagsunodsunod kalihukan sa usa ka dinamikong network, apod-apod sa trabaho, sa organisasyon sa kapasidad).
3. Ang problema sa mga coatings ug packages (accommodation dispatch centers).
4. Sa pagkolor sa mga haligi (panumdoman placement sa electronic computer).
5. networks komunikasyon ug kan (pagmugna sa usa ka komunikasyon network, ang pagtuki sa mga network sa komunikasyon).

Sa karon nga panahon nga kini mao ang imposible sa programa ang kadaghanan sa mga buluhaton sa gawas sa kahibalo sa graph teoriya. Kini naghimo niini nga mas sayon ug mas sayon sa pagtrabaho uban sa computer.

Program gigamit sa usa ka lainlaing matang sa mga istruktura ug universal mga pamaagi alang sa pagsulbad sa mga problema, ug ang usa kanila mao ang teoriya sa kan. kamahinungdanon niini mahimo halos dili konektado. Graph teoriya sa programa kini nga posible nga sa simple sa search alang sa impormasyon, sa optimize sa software, kinabig ug-apod-apod data. Pinaagi sa teoriya algorithms motungha sa posibilidad sa ilang paggamit sa ebalwasyon alang sa piho nga mga buluhaton aron sa pagdala sa mga modification sa algorithm, sa walay pagkunhod sa matang sa pagkakasaligan sa matematika nga may kinutuban nga bersyon sa programa.

Usa ka importante nga kabtangan sa sistema sa pagpugong o modelo mao ang usa ka hugpong sa duha nga relasyon uban sa hugpong sa mga buhat ug mga yunit sa data. Kini nga mga istruktura mao ang mga lamang nga bahin sa mga programa ug sa mga impormasyon nga mausab pinaagi kanila. Busa, ang mga kan gibase sa disenyo alang sa programmer.