Graff (mathemateg)

Oddi ar Wicipedia
Neidio i: llywio, chwilio
Graff wedi'i labelu, gyda chwech fertig a saith ymyl
Mae'r erthygl hon yn sôn am set o fertigau wedi'u cysylltu gyda'u hochrau. Am "Graff" (darlun i gynrychioli ffwythiant neu gasgliad o rifau, graff (ffwythgiant).

Y diffiniad ffurfiol o graff ym mathemateg yw:

Pâr trefniedig G := (V, E) sy'n bodlonni'r amodau canlynol yw graff :

  • Mae V yn set feidraidd, fe'i gelwir yn set o fertigau,
  • Mae E yn set o barau (heb drefn) o fertigau an-hafal, fe'i gelwir yn set o ymylon.

Fe gelwir y dau fertig sydd wedi eu cynnwys mewn ymyl yn ddiweddbwyntiau'r ymyl hwnnw.

Cywair graff yw |V|, nifer y fertigau. Maint graff yw |E|, nifer yr ymylon. Gradd fertig yw nifer y fertigau eraill a gysylltwyd iddo gan fertigau.