Medis (grafų teorija)

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Kitos reikšmės – Medis (reikšmės).
Medis

Grafų teorijoje medis – jungus neorientuotas grafas, kuriame kiekviena briauna yra tiltas. Miškas – grafas, kuriame tarp bet kurių viršūnių egzistuoja daugiausiai vienas kelias.

Jungaus grafo Karkasas
tai toks medis, kurio viršūnių aibė sutampa su jungaus grafo viršūnių aibe.

[taisyti] Savybės

  • Medis – jungus grafas (tarp bet kurių viršūnių egzistuoja kelias). Iš viso N medyje briaunų yra N -1.
  • Jei grafas yra medis, jame nėra ciklų.
  • Jei iš medžio pašalinti bet kurią briauną, gausime nejungų (nerišlų) grafą.
  • Jei prie medžio pridėti briauną, gausime grafą su paprastu ciklu.
  • N Medžio viršūnių laipsnių suma lygi 2 *(N -1)


A. Cayley teorema (1889 m.)
Skirtingų medžių, jungiančių N viršūnes yra NN − 2