Graffiau a Rhwydweithiau

Module Identifier
MT32410
Module Title
Graffiau a Rhwydweithiau
Academic Year
2026/2027
Semester
Semester 2
Co-ordinator
Dr Gwion Evans
Reading List
View on Aspire
Exclusive (Any Acad Year)
MA32410
Other Staff
Dr Gwion Evans

Assessment

Assessment Type

Assessment details

Proportion
Semester Exam Arholiad Ysgrifenedig: 2 Hours 2 Awr 100%
Supplementary Exam Arholiad Ysgrifenedig: 2 Hours 2 Awr 100%

Learning Outcomes

On successful completion of this module students should be able to:

  1. Ymchwilio priodweddau elfennol graffiau;
  2. Perfformio lluniadau graff syml;
  3. Cynrychioli graffiau haniaethol fel diagramau;
  4. Penderfynu os yw graff yn bodloni amryw o feini prawf;
  5. Cymhwyso algorithmau ar gyfer darganfod cydrannau;
  6. Disgrifio algorithmau Dijkstra a Floyd, a’u cymhwyso mewn achosion syml;
  7. Cymhwyso dadansoddiad llwybr critigol i brosiectau syml;
  8. Cymhwyso naill ai algorithm Prim neu Kruskal ar gyfer darganfod coed rhychwantol pwys optimwm;
  9. Cymhwyso algorithm Ford-Fulkerson i rwydwaith cludiant i ddarganfod llif macsimwm.

Brief description

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.

Aims

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.

Content

1. Damcaniaeth graff elfennol. Graffiau arbennig. Cymwysiadau syml. Matricsau cysylltiol. Teithiau a chysylltedd. Graffiau Euleraidd a Hamiltonaidd. Coed.
2. Llwybrau a chydrannau mewn graff. Algorithm i bennu cydrannau. Algorithmau llwybrau byrraf (Dijkstra) a hiraf. Algorithm Floyd.
3. Trefniad topolegol. Dadansoddiad Llwybr Critigol.
4. Coed rhychwantol. Algorithmau Prim a Kruskal i ddarganfod coed rhychwantol pwysau optimwm.
5. Rhwydweithiau cludiant. Llifoedd, toriadau. Theorem y toriad-lleiaf-llif-mwyaf. Algorithm Ford-Fulkerson.
6. Cymwysiadau.

Module skills

Skills type

Skills details
Adaptability and resilience Disgwylir i fyfyrwyr ddatblygu eu ffordd eu hunain o reoli amser ac i ddefnyddio'r adborth ar waith sy'n cael ei farcio er mwyn cefnogi eu dysgu.
Co-ordinating with others Anogir myfyrwyr i weithio mewn grwpiau er mwyn datrys problemau.
Creative Problem Solving Bydd yr aseiniadau'n cynnig cyfleoedd i fyfyrwyr i ddangos eu creadigrwydd er mwyn darganfod datrysiadau a datblygu eu sgiliau datrys problemau.
Digital capability Bydd defnydd o'r rhyngrwyd, Blackboard, a phecynnau mathemategol yn cael ei argymell er mwyn hybu dealltwriaeth o gynnwys y modiwl ac o'r enghreifftiau o gymwysiadau.
Professional communication Disgwylir i fyfyrwyr gyflwyno datrysiadau i ymarferion gosodedig sydd wedi'u hysgrifennu yn glir.
Subject Specific Skills Mae'r modiwl yn datguddio myfyrwyr i bynciau mwy eang mewn mathemateg yn ogystal â chymwysiadau nad ydynt wedi dod ar eu traws o’r blaen.

Notes

This module is at CQFW Level 6