Module Information

I gyflwyno rhai testunau mewn damcaniaeth graff clasurol. I ddisgrifio algorithmau rhwydwaith fel y rhai i ddarganfod llwybrau o hyd optimaidd, coed rhychwantol pwysau optimwm a llifoedd macsimwm, ac i’w egluro trwy gymwysiadau i achosion syml.

Datblygwyd damcaniaeth graff trwy ymchwilio nifer o broblemau clasurol – Problem Pontydd Konigsberg Euler, Problem Rhwydwaith Trydanol Kirchoff, Rhifiad Cayley o Graffiau Cemegol a’r Broblem Pedwar Lliw ar gyfer Mapiau Plân. Darganfyddir datrysiad llawn i Broblem Euler ac astudir problem Hamilton perthynol. Rhoddir algorithmau llwybr byrraf a hiraf gyda chymwysiadau, er enghraifft, i amserlennu gorchwyl (PERT). Disgrifir algorithmau i ddarganfod coed rhychwantol pwys optimwm mewn graffiau pwysol. Gellir eu defnyddio, er enghraifft, i ddarganfod rhwydweithiau cludiant cysylltiedig cost leiaf. Amlinellir y damcaniaethau o lifoedd mewn rhwydweithiau cludiant, yn arbennig theorem y toriad-lleiaf-llif-mwyaf. Mae yna gymwysiadau i lifoedd cludiant a damcaniaeth cydweddu.