Nadharia graph

Grafu nadharia - ni moja ya vifungu vidogo ya hisabati, kipengele kuu ambayo ni njia geometric katika utafiti wa vitu. Ni kuchukuliwa kuwa mwanzilishi wa mwanahisabati maarufu Euler.

matumizi ya nadharia graph ya karne ya 19, ilipunguzwa kwa ufumbuzi wa matatizo ya kuvutia na kuvutia kutosha kwa umma. Kuanzia karne ya 20, wakati nadharia graph iliundwa kama taaluma ya kujitegemea hisabati, imekuwa sana kutumika katika maeneo kama vile Cybernetics, fizikia, vifaa, programu, biolojia, umeme, usafiri na mifumo ya mawasiliano.

dhana ya msingi ya nadharia graph

msingi ni graph. istilahi inaweza kupatikana kitu kama mtandao sawa na safu wima. Ya mwisho - ni isiyo wazi idadi ya pointi, yaani, vipeo na makundi, yaani mbavu, pande zote mbili ambazo zinalingana na idadi fulani ya pointi. Grafu nadharia haina kuwekeza hatua fulani katika thamani za pembe na vipeo. Kwa mfano, barabara ya mji na kuunganisha yao, ambapo kwanza - vipeo ya graph, na wa pili - ubavu. umuhimu mkubwa anapewa na nadharia ya Arcs. Kama kingo na mwelekeo, ni wito safu, kama graph wenye makali ilivyoagizwa, inaitwa digraph.

Katika istilahi ya nadharia kama ni dhana zifuatazo:

Subgraph ni graph, kingo zote na vipeo ni miongoni mwa vipeo na edges.

Connected graph - moja ambayo ina peaks mbili tofauti zipo mlolongo kuunganisha yao.

Mizigo uhusiano graph - ambalo kuweka Viktning kazi.

Mti - uhusiano graph bila mzunguko.

Mifupa - subgraph ambayo ni ya miti.

Kwa mfano graph katika ndege defined nukuu hutumiwa: yaliyochaguliwa kipeo uhakika inalingana na uso ya msingi na kama makali baina vipeo, pointi husika ni pamoja sehemu. Kama graph-oriented, vipande hivi ni kubadilishwa na mishale.

Lakini si kulinganisha picha graph naye, yaani na muundo dhahania, kwa sababu graph mtu anaweza kupewa zaidi ya moja ya uwakilishi graphical. Kuchora kwenye ndege anapewa ili kuona ni jozi ya vipeo umoja kingo, na ambayo siyo.

Miongoni mwa baadhi ya majukumu ya nadharia graph wanajulikana:

1. tatizo la mzunguko mfupi (vifaa uingizwaji, Kuwekwa, ambulance na kubadilishana simu).
2. mtiririko tatizo upeo (kuagiza harakati katika mtandao wa nguvu, usambazaji wa kazi, shirika la uwezo).
3. tatizo la mipako na vifurushi (vituo malazi dispatch).
4. Coloring katika safu wima (kumbukumbu nafasi kwenye kompyuta za elektroniki).
5. mitandao Communication na michoro (kujenga mtandao wa mawasiliano, uchambuzi wa mitandao mawasiliano).

Wakati huu wa sasa ni vigumu kwa mpango wengi wa kazi bila ya elimu ya nadharia graph. Hii inafanya kuwa rahisi na rahisi kufanya kazi na kompyuta.

Mpango wa matumizi ya aina ya miundo na mbinu wote kwa matatizo ya kutatua, na mmoja wao ni nadharia ya michoro. Umuhimu wake ni vigumu overestimated. Grafu nadharia katika programu inayowezesha kurahisisha kutafuta habari, kuongeza programu, kubadilisha na kusambaza data. Kwa njia ya mipangilio nadharia inatokana na uwezekano wa matumizi yao katika tathmini kwa ajili ya kazi maalum ya kufanya mabadiliko ya algorithm, bila kupunguza kiwango cha kuaminika wa hisabati finite toleo la mpango.

mali muhimu katika mfumo wa kudhibiti au mfano ni seti ya mahusiano binary na seti ya vitendo na vitengo data. miundo hii ni sehemu tu ya mpango na habari ni kubadilishwa na watu hao. Kwa hiyo, grafu ni msingi wa kipekee kwa ajili ya programu.