Grafų teorija: Medžiai

Įvadas. Tikslas - apžvelgti populiarią grafų teorijos sritį – medžių teoriją. Medžiai. Medžių savybės. Įrodymas. G – jungusis ir neturi ciklų. G – jungusis ir m=n–1. G – neturi ciklų ir m=n–1. G – neturi ciklų, tačiau įvedus naują briauną, jungiančią bet kokias dvi negretimas medžio viršūnes, atsiranda vienintelis ciklas. G – yra jungusis, tačiau praranda šią savybę, pašalinus bet kurią briauną. Bet kuri viršūnių pora, sujungta grandine yra tiktai viena. Uždaviniai. Jei grafas G jungus, tai bc - (G) – medis. Grafas bc (G) vadinamas dviryšio grafo G – bc medžiu. Visame 3 – jungiamajame grafe G yra tokia briauna uv, jog grafas Guv neturi sąlyčio taškų.