Arutelu:Graaf

Allikas: Vikipeedia

Alguses olev definitsioon on küll mitteformaalne, kuid siiski peaks arvestama, et

1) graaf on abstraktne objekt, mitte joonis (ka näiteks kolmnurga joonis ei ole kolmnurk, vaid kolmnurga joonis)

2) tipud ja servad defineeritakse graafi mõiste kaudu, mitte ümberpöördult

3) ühendamise mõiste jääb ähmaseks (kas näiteks serv võib tippu ühendada iseendaga ja kas orienteeritud graaf on graaf?). Andres 24. juuli 2007, kell 07:52 (UTC)

Formaalne definitsioon teeb asja selgemaks (tuleks ka selgitada seost formaalse ja mitteformaalse definitsiooni vahel).

See definitsioon annab üldise graafimõistega võrreldes kitsama määratluse.

Esiteks, üldjuhul võib tippude hulk olla tühi. (Teisest küljest, tavaliselt võetakse see lõplik hulk).

Teiseks, üldjuhul võivad graafil olla ka silmused (servad, mis ühendavad tippu iseendaga). Neid ei saa kirjeldada kaheelemendiliste alamhulkade abil.

Kolmandaks, üldjuhul võivad graafil olla kordsed servad (etteantud kahe tipu vahel on mitu serva). Ka neid ei saa kirjeldada kaheelemendiliste alamhulkade abil. Mõnikord nimetatakse kordsete servadega graafi multigraafiks ning kordsete servade ja silmustega graafi pseudograafiks.

Neljandaks, praegu on defineeritud orienteerimata graaf. Orienteeritud graafil on servsde asemel kaared, mida vaadeldakse järjestatud paaridena. Üldjuhul on graafil nii servad kui ka kaared. Andres 24. juuli 2007, kell 08:05 (UTC)