Graph theory

Graph theory - ito ay isa sa mga subsection ng matematika, ang pangunahing tampok ng kung saan ay ang geometriko pamamaraan sa pag-aaral ng mga bagay. Ito ay itinuturing na ang nagtatag ng mga sikat na mathematician Euler.

Ang application ng graph theory sa huling ika-19 siglo, ay nabawasan sa ang solusyon ng mga kagiliw-giliw na mga problema at attracted mumunti pampublikong pansin. Simula sa ika-20 siglo, kapag ang mga graph theory ay nabuo bilang isang malayang disiplina matematika, ito ay nai-malawakang ginagamit sa mga patlang tulad ng kibernetika, physics, logistik, programming, biology, electronics, transportasyon at komunikasyon sistema.

Basic konsepto ng graph theory

Ang batayang ay isang graph. terminolohiya ay maaaring matagpuan tulad ng isang bagay bilang isang network kapareho ng haligi. Huling - ay non-walang laman na bilang ng mga puntos, iyon ay, mga vertex at mga segment, ibig sabihin, ang mga buto-buto, parehong dulo ng kung saan tumutugma sa isang ibinigay na bilang ng mga puntos. Graph theory ay hindi mamuhunan sa isang tiyak na punto sa mga halaga ng mga gilid at vertices. Halimbawa, mga kalsada ng lungsod at sa pagkonekta sa kanila, kung saan ang unang - ang vertices ng graph, at ang pangalawang - rib. Mas malawak na kahalagahan ay ibinibigay sa mga teorya ng mga arko. Kung ang mga gilid ay may isang direksyon, ito ay tinatawag na arc, kung ang isang graph na may Directed mga gilid, ito ay tinatawag na isang digraph.

Sa terminolohiya ng ang teorya pati na ang mga sumusunod na konsepto:

Subgraph ay ang graph, ang lahat ng mga gilid at vertices ay kabilang sa mga vertex at mga gilid.

Konektado graph - ang isa na may dalawang magkakaibang mga peaks umiiral chain sa pagkonekta sa kanila.

Tinimbang konektado graph - ang isa na i-set ang weighting function.

Tree - konektado graph na walang cycles.

Skeleton - isang subgraph kung saan ay isang tree.

Sa larawan sa graph sa eroplano tinukoy pagtatanda ay ginagamit: ang napiling vertex point ay tumutugon sa elementarya surface at kung ang mga gilid ay sa pagitan ng mga vertex, kanya-kanyang puntos ay pinagsama segment. Kung ang graph-oriented, ang mga segment na ito ay papalitan sa pamamagitan ng ang mga arrow.

Ngunit huwag ihambing ang mga graph ng imahe na kasama niya, ibig sabihin, na may isang abstract na istraktura, dahil ang isa graph maaring ibigay ng higit sa isang graphical na representasyon. Pagguhit sa eroplano ay ibinigay upang makita kung aling mga pares ng vertices united gilid, at alin ang hindi.

Kabilang sa ilan sa mga gawain ng graph theory nakikilala:

1. Ang problema ng pinakamaikling circuit (hardware kapalit, placement, ambulansya at palitan ng telepono).
2. Maximum daloy problema (pag-order kilusan sa isang dynamic na network, pamamahagi ng mga trabaho, ang mga samahan ng kapasidad).
3. Ang problema ng coatings at mga pakete (accommodation dispatch center).
4. Pangkulay sa mga haligi (memory placement sa mga electronic computer).
5. network ng komunikasyon at mga graph (paglikha ng isang network ng komunikasyon, ang pagtatasa ng mga network ng komunikasyon).

Sa kasalukuyan ito ay imposible sa programa ang karamihan ng mga gawain nang walang ang kaalaman ng graph theory. Ginagawa nitong mas madali at mas madali upang gumana sa mga computer.

Program ay gumagamit ng iba't-ibang mga istraktura at unibersal na mga pamamaraan para sa paglutas ng mga problema, at isa sa mga ito ay ang teorya ng graph. kahalagahan nito ay hindi matatawaran. Graph theory sa programming ginagawang posible upang gawing simple ang paghahanap para sa impormasyon, upang i-optimize ang software, i-convert at ipamahagi ang data. Sa pamamagitan theory algorithm arises ang posibilidad ng kanilang paggamit sa mga pagsusuri para sa mga tiyak na mga gawain upang isagawa ang pagbabago ng algorithm, nang hindi babaan ang mga antas ng pagiging maaasahan ng matematikal na may hangganan na bersyon ng programa.

Isang mahalagang ari-arian ng sistema ng control o modelo ay isang hanay ng mga binary relasyon sa mga set ng mga aksyon at mga yunit ng data. Ang mga kaayusan ay ang tanging bahagi ng programa at ang impormasyon ay transformed sa pamamagitan ng mga ito. Samakatuwid, ang mga graph ay batay sa mga disenyo para sa mga programmer.