Cydran gysylltiedig

Mewn damcaniaeth graffiau, cydran gysylltiedig (weithiau ond cydran sydd angen), yw is-graff o graff anghyfeiriedig neu graff cyfeiriedig. Mae'r diffiniad yn wahanol yn y ddau achos.

Graffiau anghyfeiriedig

Graff gyda thair cydran gysylltiedig.

Mewn graff anghyfeiriedig, cydran gysylltiedig yw is-graff mwyafsymaidd lle mae pob fertig wedi ei gysylltu i bob fertig eraill trwy lwybrau anghyfeiriedig. Er enghraifft, mae gan y graff a ddangosir yn y darlun tair cydran gysylltiedig. Mae fertig sengl sydd heb unrhyw ymylon yn cyfri fel cydran gysylltiedig. Os yw graff ond yn cynnwys un gydran gysylltiedig, yna fe'i helwir yn graff cysylltiedig.

Ffordd arall i ddiffinio cydrannau cysylltiedig yw diffinio dosbarthau cywerthedd o'r berthynas cywerthedd a ddiffinnir ar fertigau'r graff. Mewn graff anghyfeiriedig mae fertig v yn gyraeddadwy o fertig u os oes llwybr o u i v. Yn yr achos hwn mae un fertig sengl yn cyfri fel llwybr o hyd sero, a gall yr un fertig ymddangos mwy nag unwaith o fewn llwybr. Mae cyrraeddadwyedd yn berthynas cywerthedd, gan ei fod yn:

• Ymatblyg: Mae llwybr distadl o hyd sero o unrhyw fertig i'w hun.
• Cymesur: Os oes llwybr o u i v, yna mae llwybr o v i u.
• Trosaidd: Os oes llwybr o u i v, a llwybr o v i w, yna gellir cydgadwyno'r llwybrau i ffurfio llwybr o u i w.

Y cydrannau felly yw'r is-graffiau a ffurfir gan gymryd fertigau'r dosbarthau cywerthedd y perthynas hwn.

Graffiau cyfeiriedig

Mae graffiau cyfeiriedig yn wahanol, oherwydd bod gan bob ymyl cyfeiriad, ac felly mae gan bob llwybr cyfeiriad. Felly, mae dau fersiwn gwahanol o gydrannau cysylltiedig ar gyfer graffiau cyfeiriedig: cydrannau cysylltiedig cryf, a chydrannau cysylltiedig gwan.

Cydran gysylltiedig gryf

Graff gyda thair cydran gysylltiedig gryf.

Mewn graff cyfeiriedig, cydran gysylltiedig gryf yw is-graff mwyafsymaidd lle pob fertig wedi ei gysylltu i bob fertig arall trwy lwybrau cyfeiriedig yn y ddau gyfeiriad. Hynny yw bodoler llwybr cyfeiriedig o'r fertig gyntaf yn y pâr i'r ail fertig, ac mae llwybr o'r ail fertig i'r un cyntaf. Dywedir fod dau fertig wedi'i gysylltu'n gryf os oes llwybr rhyngddynt yn y ddau cyfeiriad. Os yw graff ond yn cynnwys un gydran gysylltiedig gryf, a does dim fertig nad yw yn y gydran hynny, yna fe'i helwir yn graff cysylltiedig cryf.

Mae'r perthynas deuaidd o fod yn gysylltiedig cryf yn berthynas cywerthedd. Felly, gellir diffinio cydrannau cysylltiedig cryf fel yr is-graffiau a chrëir trwy gymryd fertigau'r dosbarthau cywerthedd y perthynas hwn.

Cydran gysylltiedig wan

Mewn graff cyfeiriedig, cydran gysylltiedig gwan yw is-graff mwyafsymaidd graff cyfeiriedig lle mae pob fertig wedi ei gysylltu i bob fertig eraill trwy lwybrau os anwybyddir cyfeiriad yr ymylon. Er bod y diffiniad hwn yn cyfateb â diffiniad cydran gysylltiedig ar raffiau anghyfeiriedig, mae cydrannau cysylltiedig gwan wedi diffinio ar raffiau cyfeiriedig yn unig. Mae is-graffiau graff cyfeiriedig hefyd yn raffiau cyfeiriedig: felly mae gan gydran gysylltiedig gwan ymylon cyfeiriedig.

• 
  Graff cyfeiriedig gyda thair cydran gysylltiedig wan.
• 
  Yr un graff cyfeiriedig gydag ond dwy gydran gysylltiedig gryf.