Theori graff

theori Graff - mae'n un o is-adrannau mathemateg, y prif nodwedd sef y dull geometrig yn yr astudiaeth o wrthrychau. Mae'n cael ei ystyried fel y sylfaenydd y mathemategydd enwog Euler.

Mae cymhwyso theori graff i ddiwedd y 19eg ganrif, ei ostwng i ddatrys problemau diddorol a denu sylw cyhoeddus sylweddol. Gan ddechrau o'r 20fed ganrif, pan oedd y ddamcaniaeth graff ei ffurfio fel disgyblaeth fathemategol annibynnol, mae wedi cael ei defnyddio'n eang mewn meysydd megis seiberneteg, ffiseg, logisteg, rhaglennu, bioleg, electroneg, trafnidiaeth a systemau cyfathrebu.

cysyniadau sylfaenol theori graff

Mae'r sylfaen yn graff. Gall y derminoleg i'w gael y fath beth â rhwydwaith union i'r golofn. Diwethaf - yn rhif di-gwag o bwyntiau, hynny yw, fertigau ac segmentau, hy y asennau, ddau ben sy'n cyfateb i nifer penodol o bwyntiau. Nid yw theori graff yn buddsoddi bwynt penodol yn y gwerthoedd ymylon a'r fertigau. Er enghraifft, ffyrdd y ddinas ac yn eu cysylltu, lle y cyntaf - y fertigau y graff, a'r ail - asennau. Mwy o bwys yn cael ei roi i'r ddamcaniaeth y arcau. Os bydd yr ymylon yn cael cyfarwyddyd, gelwir hyn yn yr arc, os graff gydag ymylon gyfarwyddo, fe'i gelwir yn deugraff.

Yn y terminoleg y ddamcaniaeth ac felly hefyd y cysyniadau canlynol:

Subgraph yn y graff, pob ymylon a fertigau ymhlith y fertigau ac ymylon.

Connected graff - un sydd wedi ddau gopa gwahanol yn bodoli cadwyn yn eu cysylltu.

Bwysoli graff cysylltiedig - un sy'n gosod y swyddogaeth pwysoli.

Coed - graff cysylltiedig heb cylchoedd.

Sgerbwd - mae subgraph sydd yn goeden.

Yn y llun graff yn y plân nodiant a ddiffinnir yn cael ei defnyddio: y pwynt vertex ddewiswyd yn cyfateb i'r wyneb elfennol ac os yw'r ymyl rhwng fertigau, y pwyntiau perthnasol yn cael eu cyfuno segment. Os bydd y graff-ganolog, segmentau hyn yn cael eu disodli gan y saethau.

Ond peidiwch â cymharu ddelwedd graff gydag ef, hy gyda strwythur haniaethol, oherwydd gall un graff yn cael ei roi mwy nag un cynrychiolaeth graffigol. Gan dynnu ar yr awyren yn cael ei roi er mwyn gweld pa pâr o fertigau ymylon unedig, ac nad ydynt yn.

Ymhlith rhai o'r tasgau o theori graff nodedig:

1. Mae'r broblem o gylched byrraf (amnewid caledwedd, lleoliad, ambiwlans a'r cyfnewidfeydd ffôn).
2. problem Uchafswm llif (symudiad archebu mewn rhwydwaith deinamig, dosbarthu gwaith, trefniadaeth gallu).
3. Mae'r broblem o haenau a phecynnau (ganolfannau dosbarthu llety).
4. Lliwio mewn colofnau (lleoliadau cof ar gyfrifiaduron electronig).
5. rhwydweithiau cyfathrebu a graffiau (gan greu rhwydwaith cyfathrebu, dadansoddi rhwydweithiau cyfathrebu).

Ar hyn o bryd nid oes modd i raglennu'r rhan fwyaf o dasgau heb yn wybod theori graff. Mae hyn yn ei gwneud yn haws ac yn haws i weithio gyda chyfrifiaduron.

Rhaglen yn defnyddio amrywiaeth o strwythurau a dulliau cyffredinol ar gyfer datrys problemau, ac mae un ohonynt yn y theori o graffiau. Gall ei phwysigrwydd prin y gellid gorbwysleisio. theori graff mewn rhaglenni yn ei gwneud yn bosibl i symleiddio'r chwilio am wybodaeth, er mwyn gwneud y gorau o feddalwedd, trosi a dosbarthu data. Trwy algorithmau theori yn codi y posibilrwydd o'u defnyddio mewn gwerthusiadau ar gyfer tasgau penodol i gynnal yr addasiad o'r algorithm, heb leihau faint o ddibynadwyedd fersiwn cyfyngedig mathemategol y rhaglen.

Mae eiddo bwysig o'r system reoli neu fodel yn set o gysylltiadau deuaidd gyda'r set o gamau gweithredu ac unedau data. Mae'r strwythurau hyn yw'r unig ran o'r rhaglen a'r wybodaeth yn cael ei thrawsnewid gan iddynt. Felly, mae'r graffiau yn seiliedig ar y cynllun ar gyfer y rhaglennydd.