Grafai

Konspektas
 5
Microsoft Word 42 KB
3 puslapiai

Grafai - Pagrindinės sąvokos
G(n,m) – grafas, turintis n viršūnių ir m briaunų.

Aibė V vadinama grafo viršūnių aibe.
Aibės V elementų skaičius yra lygus grafo viršūnių skaičiui ir vadinamas grafo eile.
Grafas turintis tik briaunas vadinamas neorientuotu.
Grafas turintis tik lankus, vadinamas orientuotu.
Grafas, turintis ir briaunų, ir lankų vadinamas mišriuoju.

Briauna, turinti vieną viršūnę, vadinama kilpa.
Dvi briaunos yra gretimos, jei jos turi bendrą galą.
Jei turime briauną (lanką) (v1, v2), tai sakome, kad viršūnė v1 ar v2 incidentiška briaunai (lankui) (v1, v2) ir atvirkščiai.
Jei grafas turi bent vieną viršūnių porą, kuri jungiama keliomis briaunomis, tai grafas vadinamas multigrafu.
Jei kiekviena grafo viršūnė jungiama briaunomis su visomis likusiomis viršūnėmis, tai toks grafas yra pilnasis grafas. Žymima Kn.
Grafas, kurio briaunų (lankų) aibė yra tuščioji aibė, vadinamas tuščiuoju grafu. Žymimas On.

Grafas, kurio viršūnių aibę galima išskaidyti į du poaibius A ir B taip, kad kiekvienos briaunos galai priklausytų skirtingiems poaibiams, vadinamas dvidaliu grafu.
Viršūnės v laipsnis – skaičius viršūnių gretimų viršūnei v. Žymėsime r(v) arba d(v).
Orientuoto grafo atveju skiriami viršūnės įėjimo ir išėjimo puslaipsniai. Įėjimo puslaipsnis, tai skaičius lankų, įeinančių į viršūnę, o išėjimo puslaipsnis – skaičius lankų, išeinančių iš viršūnės.
Seka d(v1), d(v2), vadinama grafo viršūnių laipsnių seka.

Grafo briaunų skaičius lygus visų jo viršūnių laipsnių sumos pusei.

Pilnojo grafo visų viršūnių laipsniai yra lygūs ir lygūs (n-1). Vadinasi pilnojo grafo briaunų sk. m=n(n-1)/2.

Jei grafo visų viršūnių laipsniai yra lygūs, tai grafas vadinamas reguliariuoju grafu.

Seka briaunų (v1,v2), (v2,v3), , (vk-1,vk), t.y. gretimų briaunų seka vadinama grandine.

Grandinę galima apibrėžti viršūnių, per kurias ji eina seka. Pvz., m=(v1, v2, …, vk). Jei grandinės pirmoji ir paskutinioji viršūnės sutampa, tai tokia grandinė vadinama ciklu.

Grandinė (ciklas) vadinama paprastąja grandine...