SHPORA.net :: PDA

[ Back ]

Graaf

G = (V, E) - graaf

V - lõplik tippude hulk

E C V x V (tipupaaride hulga alamhulk)

Kui E elemente vaadeldakse kaheelemendiliste hulkadena (tippude järjekord paaris ei ole oluline), siis nimetatakse graafi orienteerimata graafiks ning hulka E graafi servade hulgaks.



Kui E elemente vaadeldakse järjestatud tipupaaridena, siis nimetatakse graafi orienteeritud graafiks (digraph) ning hulka E graafi kaarte hulgaks.

Graafiga seotud mõisteid

Kui hulka E vaadeldakse multihulgana (element võib hulgas esineda mitmes eksemplaris), siis nimetatakse graafi multigraafiks (kordsete servade/ kaartega graafiks).

Paari (v, v) hulgast E nim. silmuseks.

Tippe u, v hulgast V nim. serva e=(u, v) otstippudeks, samuti öeldakse, et tipud u ja v on intsidentsed servaga e (orienteerimata graafis u ja v on naabertipud).

Silmuste ja kordsete servadeta orienteerimata graafi nim. lihtgraafiks.

Graafi G = (V, 0) nim. nullgraafiks (servade hulk on tühi).



Lihtgraafi

G = (V, VxV {(v, v)| v kuulub hulka V})

nim. täisgraafiks (esinevad kõik erinevate tippude vahelised servad).

Tee tipust u tippu v on paarikaupa ühiste otstippudega kaarte jada:



(u, w0), (w0, w1), ... , (wn, v) kuuluvad hulka E .



Orienteerimata graafi nim. sidusaks, (orienteeritud graafi tugevalt sidusaks) kui leidub tee mistahes tipust mistahes teise tippu.



Orienteeritud graaf on nõrgalt sidus, kui kaarte suundade ärajätmisel saadav orienteerimata graaf on sidus.



Graafi G1 = (V1, E1) nim. graafi G = (V, E) alamgraafiks, kui V1 on hulga V alamhulk ja E1 on E ühisosa hulgaga V1xV1 (NB! mitte selle ühisosa alamhulk: alamhulga korral on tegemist nn. blokiga).