Teòiridh Graf

Is e teòiridh grafa aon de na fo-roinnean de matamataig, is e am feart comharrachaidh as motha an dòigh geoimeatrach ann a bhith a 'sgrùdadh nithean. Thathar a 'beachdachadh air a bhith a stèidhich an t-matamataig ainmeil Euler.

Chaidh cur an gnìomh teòiridh nan grafaichean gu deireadh an 19mh linn a lughdachadh gus fuasgladh fhaighinn air duilgheadasan fèisteas agus cha tug iad aire choitcheann gu mòr. Bho 20mh linn, nuair a tha teòiridh nan grafaichean air fàs gu bhith na smachd matamataigeach neo-eisimeileach, tha e air iarrtas farsaing fhaighinn ann an raointean saidheans mar chibernetics, fiosaig, logistics, prògramadh, bith-eòlas, dealanach, siostaman còmhdhail agus conaltraidh.

Bunaitean bunasach de theòiridh grafa

Is e an graf am fear bunaiteach. Ann am briathrachas, faodaidh neach a bhith a 'tighinn tarsainn air leithid de cho-bheachd mar lìonra co-ionann ri graf. Is e àireamh de phuingean nach eil falamh a th 'anns an dàrna fear, is e sin, vertices, agus earrannan, is e sin, oirean, an dà cheann a tha a' freagairt ri àireamh sònraichte de phuingean. Chan eil teòiridh an graf a 'dèanamh ciall chinnteach ann an luachan oirean agus verticean. Mar eisimpleir, bailtean-mòra agus na rathaidean a 'ceangal riutha, far a bheil a' chiad fheadhainn air mullach a 'ghraf, agus an dàrna fear - na h-oirean. Tha e nas cudromaiche ann an teòiridh a bhith air a thoirt do ghunnaichean. Ma tha treòrachadh aig an oir, tha ainm arc ann, ma tha an graf le oirean a tha air a stiùireadh, canar ris an digraph.

Ann am briathrachas an teòiridh, tha na bun-bheachdan a leanas a 'seasamh a-mach:

Is e graf a th 'ann am fo-sgrìobhadh, agus tha na h-oirean is na h-earrainnean aca am measg verticean agus oirean.

Is e graf co-cheangailte a th 'ann agus tha sreath ann a tha gan ceangal airson dà dhìreach eadar-dhealaichte.

Is e graf co-cheangailte le cuideam aon a tha a 'toirt cuideam cuideam.

Is e craobh ceangailte a th 'ann an craobh gun chuairt.

Is e fo-sgrìobhadh a th 'anns a' chnàimh a tha na chraoibh.

Nuair a thèid graf a tharraing air a 'phlèana, thèid nota sònraichte a chleachdadh: tha an t-òrd a tha air a thaghadh a' freagairt ri puing air an uachdar as sìmplidh, agus ma tha iomall eadar na vertices, bidh na puingean co-fhreagarrach air an ceangal le earrann. Ma tha an graf air a stiùireadh, thèid na roinnean seo a chur nan àite le saigheadan.

Ach na dèan coimeas eadar ìomhaigh a 'ghraf leis, is e sin, le structar eas-chruthach, oir faodar barrachd ghraf a thoirt dha aon riochdachadh grafaigeach. Tha tarraing air a 'phlèana air a thoirt seachad gus faicinn dè na paidhrichean de dhruimichean a tha a' ceangal ri oir agus nach eil.

Am measg cuid de dhuilgheadasan a thaobh teòiridh grafa, tha:

1. Obair na slabhraidh as giorra (cuir an àite uidheam, suidheachadh ionadan-eiridinn agus stèiseanan fòn).
2. An duilgheadas a th 'aig an t-sruth as àirde (òrdachadh trafaic ann an lìonra fiùghantach, sgaoileadh obair, eagrachadh comas).
3. Obair a 'bhualadh agus a' phacaid (cur àite air puingean sgaoilidh).
4. A 'dathteachadh ann an grafaichean (cuir cuimhne air coimpiutairean dealanach).
5. Conaltradh lìonraidhean agus ghrafaichean (cruthachadh lìonra conaltraidh, sgrùdadh air lìonraidhean conaltraidh).

Aig an àm seo, tha e do-dhèanta a 'mhòr-chuid de na duilgheadasan a chlàradh gun a bhith a' tuigsinn teòiridh nan grafaichean. Tha seo ga dhèanamh nas fhasa agus nas fhasa a bhith ag obair le coimpiutair.

Bidh prògramadh a 'cleachdadh tòrr structaran agus dòighean coitcheann airson fuasgladh fhaighinn air duilgheadasan, agus aon dhiubh sin teòiridh grafa. Tha an luach aige doirbh a bhith a 'toirt tuairmse air. Tha teòiridh an graf ann am prògraman ga dhèanamh furasta fiosrachadh fhaighinn, prògraman a dhèanamh nas fheàrr, dàta a thionndadh agus a sgaoileadh. Mòran taing do algorithms an teòiridh, tha e comasach an cleachdadh agus an luachadh a chleachdadh airson fuasgladh fhaighinn air duilgheadasan sònraichte, gus an algorithm atharrachadh, gun a bhith a 'lughdachadh ìre dearbhachd matamataigeach de dhreach deireannach a' phrògraim.

An cudromach seilbh an siostam smachd no modal tha seata de Binary dàimh ris an seata de ghnìomhan agus dàta aonadan. Is e na structaran sin na h-aon phàirtean de na prògraman agus am fiosrachadh a tha iad ag atharrachadh. Mar sin, tha grafaichean mar bhunait airson togail don neach-clàraidh.